Nothing in threes

Two Routes to the Same Number

One method walks the comparisons, the other counts who could be first. They share no step and agree on all forty pages, which is the whole of the guarantee.

at most 240 outcomes

Home · Nothing in threes · Reference

This record's fifth figure — how many outcomes fall into an order — is computed twice, by methods with nothing in common.

They agree everywhere. This note is about why that is worth more than either method on its own. If several people repeat this comparison, managers may look at the platform before a pilot while interpreting every signal beside completed work and participant feedback.

Four candidates, four amounts of comparing

line with a head: a pair compared; the head points at whoever came out behind
no line: a pair nobody compared
closed ring of three: a circular triple: no order can hold all three

Four outcomes drawn. Every row is the same number of candidates. Which candidate is which is the drawing's own choice and carries no meaning. Readers examining the figures against practical research methods can also see Statistics By Jim.

Four pages of the same pool, each row counting outcomes with no circular triple. The orderable counts for the same four pages run one hundred and fifty-two, one hundred and eighty-six, one hundred and eight, twenty-four — and only the second differs from the figure drawn beside it.

Computed from the three numbers alone. Who the candidates are and what any comparison was about is outside the record; the counts are of outcomes, not of anybody.

The first method

Walk the comparisons.

Generate an outcome. Start at a candidate and step to anybody they came out behind, then step again. If a walk ever returns to a candidate it has already passed, the outcome contains a ring and cannot be ordered.

Do that for every outcome of every page. For a field of six that is fourteen million three hundred and forty-eight thousand nine hundred and seven outcomes, and it takes about two minutes.

The method knows nothing about candidates as such. It knows about links and where they lead.

The second method

Count who could be first.

An outcome can be ordered exactly when somebody came out behind nobody — somebody who could be put at the front. Choose which candidates have that property, observe that the rest form the same problem with a smaller field, and allow for the fact that an outcome with several such candidates gets counted several times.

Correcting for the overcount is an alternating sum: add the count with at least one, subtract the count with at least two, add back the count with at least three. The result is a formula in the number of candidates that can be evaluated with a pencil for any field this record covers.

The method never generates an outcome. It never looks at a link.

What they produce

The same numbers, on all forty pages.

For four candidates the orderable counts by number of comparisons run one, twelve, sixty, one hundred and fifty-two, one hundred and eighty-six, one hundred and eight, twenty-four. Added up: five hundred and forty-three.

For five candidates the total is twenty-nine thousand two hundred and eighty-one. For six, three million seven hundred and eighty-one thousand five hundred and three.

A figure produced one way is a claim. The same figure produced two ways that share no step is close to a fact.

What the recurrence costs

Very little, which is why it is worth having.

For a field of six it is a sum over subsets of the candidates with a binomial coefficient and a power of two in each term — a few dozen multiplications, done once, producing the whole row at every number of comparisons at the same time.

The first method generates fourteen million outcomes. The second fits on a page. They agree, and the agreement is the point: a cheap method that matches an expensive one has checked the expensive one, and the expensive one has checked the cheap one's algebra.

Why this is not belt and braces

Because the failure that matters here is silent.

An arithmetic slip in a count of three million produces another number of about the same size. Nothing about it looks wrong. It passes every check that asks whether the figure is plausible, because it is plausible — it is simply not the answer.

The only defence against that is a second route. If the two agree, a mistake would have to have been made twice in ways that happened to cancel, and the two methods have no shared step in which such a mistake could live.

What the four rows show

Four candidates, with three, four, five and all six pairs compared, counting outcomes with no circular triple: one hundred and fifty-two, one hundred and ninety-two, one hundred and eight, twenty-four.

The orderable counts for the same four pages: one hundred and fifty-two, one hundred and eighty-six, one hundred and eight, twenty-four.

Three of the four agree exactly. The second does not, and the gap is six — the four-step rings, which exist only when exactly four pairs are compared on a field of four. Fewer comparisons cannot close the ring; more comparisons close a triple as well and the third number catches it.

That single page is where the whole of the next column's story starts, and it is visible here as one figure out of four failing to match its neighbour.

Where the two routes would disagree first

At the boundary, if anywhere.

Both methods have to handle the page with no comparisons and the page with every pair compared, and both are easy to get wrong there: a sum over subsets can mishandle the empty one, and an enumeration can double-count the single outcome where nothing was compared.

Those two pages are where a disagreement would show first, and they are also the two pages a reader can check by hand against both methods. One outcome at no comparisons, n factorial at full comparison. Both routes give those, which is a small check and the first one worth running.

Why both are kept in the record's tooling

Because the record gets rebuilt.

A figure checked once is checked for the version it was checked in. Both methods run every time the record is built, on all forty pages, and a disagreement stops the build. That is the difference between having verified something and having a verification.