The walk that cannot cross

The walk over an admissible set is exactly uniform, and the proof is one line: the proposal is symmetric, a refused proposal is a step in place, so detailed balance holds against the uniform distribution. This collection checks it by building the transition matrix on twelve units and reading its stationary vector, which is as direct as a check gets.

The proof is correct and it proves the wrong thing. Uniform on what is the question, and the answer is not always the admissible set.

A thin set comes apart #

Take fourteen units, four balancing functions and a tolerance of 0.8. Of the 3,432 equal splits, 116 are admissible — 3.4%, a perfectly ordinary rerandomisation.

Under single swaps that set of 116 falls into two pieces of exactly 58, and the pieces are not fragments around an edge. Every one of the 116 assignments has its complement in the other piece, all 116 of them, so what the walk cannot do is get from an assignment to the one that swaps every unit’s arm.

It is not one bad setting. Two constraints at a tolerance of 0.5 leave 376 admissible assignments in two pieces of 188; at 0.35, 198 in two pieces of 99; at 0.2, 84 in four pieces. One constraint at 0.2 leaves 522 in three pieces — one of 520 and two single assignments with no admissible neighbour at all, which are each other’s complements.

A walk started anywhere in one of those sets is uniform on its own piece and blind to the rest, for ever. It does not fail to converge; it converges, to the wrong distribution.

The count of pieces is not the whole of the damage either, because the pieces are the same size. Two components of 58 means the walk samples exactly half the reference set, so the draws it produces are a valid sample of a distribution that is not the one the test is about.

And the diagnostics all pass #

Every check this collection makes of that walk passes on a disconnected set.

The chain is still exactly uniform on what it can reach, so detailed balance holds. The stationary vector is still uniform — restricted to a component, which is the vector a power iteration started inside that component returns. The acceptance rate is normal. The autocorrelation time is normal. The draws look like admissible assignments because they are admissible assignments.

This is the same shape as the chain that preserves the uniform distribution and never approaches it, arriving from the other side. There the proposal was pathological and the set was fine; here the proposal is the ordinary one and the set has come apart. In both cases the property that is checked — stationarity — is genuinely there, and the property that matters — reaching the whole set — is not implied by it.

The check that finds it is a different one: enumerate the set and count its connected components under the moves the walk can make. That is affordable only where the set is enumerable, which is exactly where a walk is not needed, and it is the reason this is stated as a hazard rather than as a test a trial can run.

What half a reference set costs #

The damage depends entirely on what is being read off the reference distribution, and the two ordinary readings differ completely.

A randomisation test holds the observed outcomes fixed and recomputes the statistic under each hypothetical assignment. Swapping the arms of a fixed outcome vector negates a difference in means, exactly — so the two components, being complement pairs, carry mirror images of one distribution.

The upper 5% point is 0.9344 on one component and 0.4170 on the other, against 0.7749 over the whole set. A one-sided test run on the component the walk happened to start in uses a critical value 21% too large or 46% too small, depending on which half that was, and nothing in the run says which.

The two-sided reading is untouched. The 95% point of the absolute difference is 0.9344 on either component against 0.9434 over the set — a gap of nine thousandths, which is the difference between a quantile of 58 numbers and one of 116. A mirror image has the same absolute values, so a test that reads them is reading the same distribution either way.

That is an unusually clean division. The defect is invisible to the test most trials run and inverts the test some of them run, and no amount of looking at the chain distinguishes the two cases.

The repair is a bigger proposal #

The obvious repair is to propose swapping more than one unit from each arm, and it works.

Four of the six disconnected sets in the table become connected under two-swap proposals: the 116 assignments that were two pieces of 58 are one piece of 116, and the same for 522, 376 and 198. Two swaps can cross where one cannot, because the intermediate assignment a single swap would have to pass through is inadmissible and a double swap does not have to pass through it.

The two that stay in pieces are the thinnest — 84 admissible assignments and 14 — where a two-unit move rarely lands anywhere admissible either, and the repair would need a larger proposal still. So the repair is real and it is not a guarantee: it moves the boundary rather than removing it.

That is worth putting beside what a bigger proposal was measured to be worth: a factor of six in mixing speed where the walk-against-hunt comparison is not close, and nothing at all where it is. On mixing speed the answer was the dial is in the wrong place. On ergodicity it is a different kind of answer: a single-swap walk on a thin set can be wrong, and a two-swap walk is not, and no amount of running the first one longer repairs it.

The repair is not free and it is not universal. Larger proposals are refused more often, and on a set of ten admissible assignments of twelve units a three-swap walk fragments into four pieces of one, because a move that large almost never lands anywhere admissible. So the proposal size has to be large enough to cross and small enough to be accepted, and both ends of that are properties of the particular set rather than of the method.

Why the split is the complement pairing #

The two halves are not two arbitrary halves, and the structure says something about where the wall is.

An admissible set is closed under complement: the imbalance of the complementary assignment is the negative of the original’s, and a box constraint |z| ≤ a is symmetric, so an assignment is admissible exactly when its mirror image is. Every set in this table has that property and it is checked rather than assumed.

Getting from an assignment to its complement means swapping every unit, which is seven single swaps at fourteen units. Each of the six intermediate assignments has to be admissible, and in a thin set they are not — the path crosses a region of large imbalance, because an assignment half way between one arrangement and its mirror is not close to either.

It is worth being clear about what this is not. It is not a sign rule: both components contain assignments with positive and negative imbalance on every one of the four functions, and their ranges overlap on every one. The two halves are interleaved in imbalance space and separated in the swap graph, which is why nothing computed from the imbalances would reveal it.

Equal halves is the signature #

The complement pairing has a consequence that makes it identifiable from the counts alone, before any structure is examined.

If every assignment’s complement lies in the other piece, the complement map is a bijection between the two, so the two pieces must be exactly equal in size. 116 splits into 58 and 58; 376 splits into 188 and 188.

That is a check anybody can run. A set falling into two pieces of unequal size is falling apart for some other reason — a genuinely disconnected corner, a region the swaps cannot reach for reasons of geometry rather than of symmetry — and would need a different diagnosis and a different repair.

Seven swaps, and every one of them has to land #

The obstruction is a distance rather than a shortage of edges, and the distance is worth counting.

A single swap moves two units. Reaching an assignment’s complement means moving all fourteen, so the shortest possible route is seven swaps — and every one of the six intermediate assignments has to be admissible, since the walk cannot pass through an inadmissible state.

With 3.4% of splits admissible, six independent intermediate landings would happen about $10^{-9}$ of the time. Admissibility is clustered rather than independent, so the true chance is far higher than that, and the enumeration says the answer is nevertheless exactly zero: on this set no admissible seven-swap path exists at all.

Which is why the degree of the graph says nothing about the problem. An assignment here has plenty of admissible neighbours; what it does not have is an admissible corridor seven steps long leading to its own mirror image, and no local count can see a corridor.

The isolated assignment, which is worse #

The two-component split is the common case and the other one in the table is stranger. One constraint at a tolerance of 0.2 leaves 522 admissible assignments, of which 520 form one piece and two are alone — each admissible, with no admissible single-swap neighbour, and each other’s complement.

A walk started at one of those never moves. Not slowly: never. Every proposal is refused, the chain stands still by design, and it reports the same assignment for as many draws as are asked of it.

The reference distribution that comes back is a point mass. Any statistic computed from it has zero spread, so a one-sided p-value is either 1/(B + 1) or 1, and the interval it implies is a point. Nothing about that output looks like a converged chain, which is the one mercy in it — unlike the two-component case, where the output looks entirely normal.

Both failures are the same failure at different scales, and both are invisible to a check that reads the chain’s own behaviour. A chain cannot report on a region it cannot reach, which is the sentence this whole essay is a demonstration of.

What it means for a trial #

Three things follow, and the first is the awkward one.

The hazard is not detectable where it matters. Counting components needs the set enumerated, and a trial that can enumerate its admissible set has no reason to walk it. At two hundred units nothing here says whether the set is connected, and the mechanism — an assignment separated from its complement by a wall of inadmissible intermediates — has no reason to disappear with size.

Use a proposal that moves more than one unit. It costs a little mixing efficiency at loose tolerances and it removes an entire failure mode, and the failure mode is one whose symptom is a wrong answer rather than a slow one.

And prefer the two-sided reading, or check the one-sided one against a hunt — which is the method the cost comparison already prefers across most of the range. The hunt does not have this problem at all: it draws from the whole assignment space and keeps what is admissible, so it reaches every component by construction. Where the two methods are close in cost — which is most of the range — that is a reason to prefer the hunt that has nothing to do with cost.

How thin is thin enough, and it is not a share #

The obvious next question is where the boundary is, and the table’s answer is that there is no boundary in the one dial that everything else in this field depends on.

Sorted by how much of the assignment space they admit, of the sets enumerated here: 15.2% admitted and three components; 11.0% and two; 9.9% and one; 5.8% and two; 3.4% and two. A set admitting one assignment in nine is connected and one admitting one in six-and-a-half is not.

That is the sharpest contrast this field has to offer. The cost comparison collapses onto thinness — five dictionaries, eight tolerances, one curve — and connectivity does not collapse onto it at all. How expensive a walk is depends on how thin the set is; whether a walk is correct depends on the set’s shape, and two sets of the same size have different shapes.

Which means the reassurance a practitioner would reach for is not available. There is no acceptance rate above which the walk is safe, and the quantity that decides it cannot be measured without enumerating the set. What the table does support is the negative statement, which is the useful one: an admissible set of a few per cent is quite likely not to be connected, and nothing about the chain will say so.

What a hunt does instead #

The comparison with rejection sampling is worth making explicitly, because it is the only method here that has none of this.

A hunt draws an assignment uniformly from all equal splits and keeps it if it is admissible. Every admissible assignment is reachable on every draw, at exactly the same probability, whatever the set’s shape — there is no graph, no path, and nothing to be disconnected. The draws are also independent, so the granularity of a p-value from B of them is 1/(B + 1) rather than something that has to be discounted for autocorrelation.

What it costs is 1/p attempts per draw, which is the whole of the trade this field has measured. The honest summary of the two essays together is: a hunt is more expensive and cannot be wrong; a walk is cheaper past a certain thinness and can be silently wrong before that thinness is reached.

That asymmetry is not usually how the choice is presented. It is presented as a cost comparison with two methods that are both correct, and one of them is only correct when a property nobody checks happens to hold.

What is claimed here, and what is not #

This essay takes whether a walk over an admissible set reaches all of it. The claims are that at fourteen units a set of 116 admissible assignments splits into two components of 58 under single swaps, with every assignment’s complement in the other component; that the same happens at 376, 198 and 84 admissible assignments under other settings, and that one setting leaves two assignments with no admissible neighbour at all; that a one-sided randomisation critical value computed on one component is 0.4170 against the whole set’s 0.7749 while the two-sided one is 0.9344 against 0.9434; and that two-swap proposals reconnect four of the six disconnected sets here and leave the two thinnest in pieces.

What stays out and is named as a decision: whether this happens at a useful trial size. Everything above is enumerated at twelve and fourteen units, because a component count cannot be sampled — a walk that cannot reach a component reports nothing about it, which is the whole problem. Whether a two-hundred-unit set with a rich dictionary is connected is unknown here, and the honest position is that the mechanism does not obviously depend on size while the measurement cannot be made.

Also out: other proposals. A swap is not the only admissible move — a rule could propose a permutation, or move a random number of units — and the ergodicity of those is a question with the same shape and no measurement here.

The checks #

Two claims are gated. A thin admissible set is required to be disconnected under single swaps and no worse under double ones, which is the pair that makes the repair a repair rather than a coincidence — stated as no worse rather than as connected, because on the two thinnest sets it is not connected and a gate written to the headline would have been a gate about the cases that suit it. And the components are required to be exactly the complement pairs — every assignment’s mirror image in the other piece — because a split into two arbitrary halves would be a different phenomenon with a different fix.