A test rather than a survey

The walk that cannot cross establishes something a chain cannot report on itself. At fourteen units with four balancing functions and a tight tolerance, the 116 admissible assignments fall into two components of 58 under single swaps, and every one of them has its complement in the other component. A walk started anywhere is uniform on its own half for ever, and every diagnostic passes: detailed balance holds, the stationary vector is uniform, the acceptance rate is ordinary.

That was found by enumerating all 3,432 equal splits of fourteen units. At twenty-two units there are 705,432 of them and at two hundred there are more than the number of atoms in anything. A defect demonstrated where it can be enumerated and mattering where it cannot is a defect nobody can act on.

How fast the enumeration goes out of reach #

The three sizes named span the whole of the difficulty, and the numbers are worth having exactly because the growth is not the kind a faster machine addresses.

Fourteen units give $\binom{14}{7} = 3{,}432$ equal splits — a loop. Twenty-two give 705,432, which is a few seconds. Two hundred give

$$\binom{200}{100} \approx 9 \times 10^{58},$$

against roughly $10^{50}$ atoms in the Earth.

Between the second and the third there is no engineering. Every two units multiply the count by very nearly four, so each additional pair of subjects costs as much as the previous twenty-two units cost in total, and a thousandfold faster computer buys about five more units.

That is why the defect has to be turned into a test rather than a survey. A survey asks what the admissible set looks like, and the answer is a list nobody can hold. A test asks a yes-or-no question about it, and a yes-or-no question can be answered by two chains that never enumerate anything.

The construction #

Every balancing rule in this collection constrains the absolute imbalance in a list of functions, and both the box rule and the ellipsoid do. So the rules are symmetric under the joint sign flip: the imbalance of −z is minus the imbalance of z, and a vector is admitted exactly when its negative is. The admissible set is closed under complementation, whether or not the walk can reach across it.

That gives a test with no enumeration in it.

Run one chain from an admissible assignment. Run a second from its complement. Compare them on a statistic that changes sign under the complement — the signed imbalance in a function the rule was not handed. If the walk reaches the whole set, the two chains are two runs of one chain and the difference is noise. If the set is the mirror pair, the two chains report mirror images of one distribution and the difference is twice a mean.

The mirror structure is what makes the test possible and it is not assumed. On the fourteen-unit set the two components carry means of +0.0840 and −0.0840 with standard deviations agreeing to four decimal places, and the whole set’s mean is zero — which is the symmetry, visible.

There is a second thing the closure buys and it is worth naming, because it is what makes the two chains comparable at all. A chain started at an admissible assignment has to be started somewhere, and the only way to find such a point without the chain is to hunt for one by rejection. The complement of whatever the hunt returns is admissible for free — no second hunt, no second cost — so the two starting points are as independent of each other as any pair of points in the set can be while being mirror images. Nothing about the test’s arrangement gives one chain an easier region than the other.

What it agrees with #

Eight tolerances, from a box at 1.4 down to one at 0.7, leaving admissible sets of 1534, 886, 304, 158, 126, 116, 102 and 84 assignments. The enumeration says the first five are in one piece and the last three are not.

The test — twenty thousand steps of each chain, and no enumeration anywhere in it — reports −0.03, 1.15, 0.82, −0.61 and 1.96 on the connected sets and −9.54, −13.25 and −14.58 on the split ones. Zero misses and zero false alarms, with the boundary between them falling exactly where the enumeration puts it: between a tolerance of 0.85 and one of 0.80.

That is the check the whole field rests on. A diagnostic that agrees with the truth wherever the truth is computable is a diagnostic that can be pointed at a place where it is not.

The boundary’s location is itself worth a sentence. Between a tolerance of 0.85 and one of 0.80 the admissible set falls from 126 assignments to 116 — a drop of ten, or eight per cent — and the set goes from one piece to two. Connectivity is not a gradual property. It has a threshold, and on this design the threshold sits between two tolerances a practitioner would consider interchangeable.

That is the practical case for having an instrument rather than a rule of thumb. There is no tolerance below which a set is unsafe and above which it is fine; there is a design, a basis and a tolerance, and whether the three of them together leave a connected set is a question about the particular units drawn.

Why the signal grows and the noise does not #

The statistic is a difference of two means divided by their standard errors, so what it does with a longer run is the whole of its behaviour.

On a set in two pieces the two chains estimate two different means and the difference does not shrink; the standard errors do, like one over the square root of the effective draws. So the statistic grows: from 4.70 at a thousand steps to 11.56 at thirty-two thousand.

That is a factor of 2.46 over a factor of thirty-two in length, and square-root growth predicts 5.66. The shortfall is in the denominator of the ratio rather than in the growth. The reading at a thousand steps is the least trustworthy number in the sweep, because the effective sample size it divides by is itself estimated from a chain that has not mixed: across five seeds that estimate comes out anywhere between 42 and 83, and the thousand-step statistic moves with it — 4.70, 2.28, 0.81, 1.95 and 2.17, with the sweep drawn above holding the largest of the five. The thirty-two-thousand reading barely moves at all, from 11.56 to 13.27, because by then the chain has mixed and the effective size is a real measurement. Take the ratio on each seed separately and the median is 5.50 against the 5.66 predicted. The growth is square-root growth; one sweep’s growth factor is one short chain’s luck, and it is the same quantity that fails later in this field at two hundred units.

On a connected set the two chains estimate the same mean, the difference shrinks at the same rate as the standard errors, and the statistic is a standard normal at every length: 0.54, 0.46, 1.29, 0.55, 0.95 and 1.71 across the same sweep.

A number that grows with the run and a number that does not is what separates a fact about the set from a fact about the sample, and it is why the sweep is here rather than a single reading.

What the sets look like as they thin #

The eight tolerances are worth reading as a ladder rather than as a list, because the shape of the thinning is what the whole field is about.

At a box of 1.4 the rule admits 1,534 of the 3,432 equal splits — nearly half — and the swap graph is dense. At 1.0 it admits 304, at 0.9 it admits 158, and at 0.85 it admits 126 and is still in one piece. At 0.8 it admits 116 and is in two. Below that the components stay two until, at a tolerance of 0.6, the set has 34 assignments in four pieces with two of them isolated — a single assignment with no admissible neighbour at all, from which the walk cannot move.

The number of assignments falls smoothly and the number of pieces does not. A rule of thumb about how thin is too thin would have to be a rule about the swap graph rather than about the count, and the swap graph is the thing nobody can look at.

The standard error is not the obvious one #

The comparison has to be made on the effective number of draws rather than on the number taken, and that is not a refinement.

Consecutive states of the walk differ by one swap out of seven pairs, so the signed imbalance moves by a little each step and the sequence is strongly autocorrelated. At fourteen units the integrated autocorrelation time of this statistic is about eighteen, so twenty thousand steps are worth about eleven hundred independent ones. A standard error computed from twenty thousand would be more than four times too small, and the test would report a split on every run of a perfectly ergodic chain.

That correction is the same one a chain’s own p-value needs, and it is the reason a chain-based reference distribution resolves less than its draw count suggests. Here it is load bearing rather than a caveat: the test is a comparison of two means, and a comparison of two means is exactly as good as the standard errors under it.

What the chain’s own diagnostics say #

It is worth being explicit about why a new instrument was needed rather than a better use of the old ones.

On the fourteen-unit set with 116 admissible assignments in two components, the acceptance rate is 16.47%, which is ordinary. The stationary distribution of the chain is uniform to 5.2 × 10⁻¹⁸, which is what the construction promises. The transition matrix is exactly symmetric, so detailed balance holds to machine zero. All three are computed on the chain’s exact transition matrix rather than simulated, so none of them is a run that could have been unlucky.

Every one of the three is computed from where the chain goes. A diagnostic built from a chain’s own states cannot report on the states it never visits, and that is not a flaw in those three checks — it is what they are.

What the test costs #

Three chains rather than one, and a run long enough for the autocorrelation time. At fourteen units that is seconds; the cost is worth stating because the alternative is not expensive either at that size, and the whole point is the sizes where the alternative does not exist.

The third chain is the control, started at the same assignment as the first on a different stream. Two chains far apart on a signed statistic have two explanations — they are in mirror components and cannot reach each other, or they simply have not mixed — and the third chain separates them, because two chains started at the same point cannot be separated by any structural fact about the set.

Without it the test is a coin at the sizes it was built for, which is the finding the essay at two hundred units reports.

At fourteen units the control never fires: across all eight tolerances the replicate comparison stays inside 2.7 standard errors, and so does the comparison on the statistic’s absolute value. Both are quiet on the split sets as well as on the connected ones, which is the pair of readings that makes the verdict a verdict rather than a single number — the signed comparison fires and the other two do not, and that combination has exactly one explanation.

What it is for #

The reason to want this instrument is not curiosity about graph connectivity. It is that a randomisation test’s p-value is a share of a reference distribution, and a walk that reaches half of one is computing a share of the wrong thing.

What the split costs depends entirely on which reading is taken. The difference in means changes sign under the complement, so the two components carry mirror images of one distribution: a one-sided critical value read off a single component is 0.4170 where the whole set gives 0.7749, and a two-sided one is 0.9344 against 0.9434. The defect is invisible to the test most trials run and inverts the test some of them run.

So the question the instrument answers is a question with a consequence attached, and the consequence is asymmetric in a way nothing about the chain would suggest. A practitioner running a two-sided randomisation test on an unreachable half is fine. A practitioner running a one-sided one is reporting a critical value that is nearly half of the right one, with every diagnostic green.

That asymmetry is also why the test is built on a signed statistic rather than on the obvious magnitude: the property being detected is exactly the property a two-sided reading cannot see, so an instrument built the two-sided way would be blind to the thing it was pointed at. That is the statistic’s own essay, and it is where the third chain comes from.

What is claimed here, and what is not #

This essay takes a diagnostic for a walk’s unreachable half that does not enumerate the set. The claims are that every rule in this collection admits a vector exactly when it admits the negative, so the admissible set is closed under complementation; that the two components of a split set carry mirror images of one distribution, measured at +0.0840 and −0.0840 with matching spreads; that a comparison of two chains started at an assignment and its complement, on a signed statistic and at effective standard errors, agrees with the enumerated truth at all eight tolerances checked, with no misses and no false alarms; and that the statistic grows with the length of the run on a split set at a median factor of 5.50 over thirty-two-fold against the 5.66 square-root growth predicts — a median across seeds rather than any one sweep’s factor, since the shortest reading is the one that cannot be trusted — and stays at a standard normal on a connected one.

What stays out, and is named as a decision: a proof. Nothing here shows that a large statistic implies a disconnection, and how large a defect has to be before the statistic can see it is measured separately. What it shows is that the statistic is large exactly where a disconnection is, on every case where the answer can be checked — which is evidence of the same kind, and the only kind available at sizes where the answer cannot.

Also out: rules that are not symmetric. A balancing rule constraining a signed imbalance rather than its magnitude would break the closure the whole construction rests on, and the assertion below refuses one. No such rule appears anywhere in this collection, and that is a fact about the collection rather than about trials.

The boundary against the essay that found the split is that it enumerates and this one does not, and the two are checked against each other for exactly that reason.

The checks, and the refusals that make them mean something #

Three claims are gated. The admissible set is required to be closed under complementation, checked on the enumerated set rather than argued from the algebra, because a rule with an asymmetric constraint would break it quietly. The signed statistic is required to be exactly antisymmetric under the complement and its absolute value exactly symmetric, which is the design of the test and of its control at once. And the test’s verdict is required to match the enumeration at every tolerance in the sweep, in both directions — no missed split and no false alarm — because a test that fired everywhere would agree on the split cells and be useless.

The refusal is the instrument this one replaces. A chain’s own diagnostics are refused as evidence of reachability, with the acceptance rate, the uniformity of the stationary vector and the exact symmetry of the transition matrix printed beside the number of components the set actually has.