Stationary is not convergent

The check a Markov chain sampler is usually validated by is that its stationary distribution is the one wanted. The essay that built this collection’s walk makes exactly that check: the transition matrix is written down, its stationary vector is read off, and it is uniform on the admissible set to 6·10⁻¹⁷. The variant that re-proposes rather than standing still fails the same check — its stationary distribution is proportional to the degree — and is refused.

The family of k-swap proposals contains a chain that passes that check and is useless, and the two facts are not in tension. It is worth setting out because the check is the one everybody makes and the property it establishes is weaker than it sounds.

The chain that never moves again #

Twelve units, six in each arm. Exchanging all six is one proposal — swap everything — and it turns an assignment into its own complement.

The admissible set is closed under complement: reversing every assignment reverses the sign of every imbalance, and a tolerance that is symmetric about zero admits one exactly when it admits the other. So the proposal is always accepted, and the walk goes x → x̄ → x → x̄ for ever.

Its transition matrix is doubly stochastic — every row and every column sums to one — so the uniform distribution is stationary for it. Feed the uniform distribution in and the uniform distribution comes out. That is a true statement about the matrix and it says nothing whatever about where the chain goes.

Every doubly stochastic matrix preserves the uniform distribution. The identity matrix does. A permutation matrix does. Stationarity is invariance, and invariance is not attraction.

What the check actually establishes #

The three properties usually run together are separable, and this chain separates them.

Stationarity. πP = π. Here π is uniform and it holds. This is what the usual check tests, and it is a statement about one distribution being fixed.

Irreducibility. Every state is reachable from every other. Here it fails: from a given assignment the chain can reach exactly one other, and the set of 410 splits into 205 disjoint pairs.

Aperiodicity. The chain does not cycle. Here it fails too: the period is exactly two.

A chain converges to its stationary distribution from any start when the second and third hold; without them the first is a fact about a fixed point that the chain has no way of reaching. The distinction is standard, and the reason it is worth a measurement is that it is invisible in the output. A stationary vector read off a matrix looks identical whether the chain is irreducible or not, because the power iteration that computes it is started at the uniform distribution — which is already the answer.

The check was being started at its own conclusion. Started anywhere else, this chain never approaches it.

Where 0.9976 comes from #

The number in the caption is not an approximation to one; it is exact, and what it is exactly says how degenerate the chain is.

Total variation distance from the uniform distribution on 410 states, for a distribution concentrated entirely on one of them, is

$$1 - \frac{1}{410} = 0.997561 .$$

0.9976. So the walk’s distribution at each step is a point mass — not nearly a point mass, not concentrated with a little leakage. The chain is deterministic: at every even step it is at the assignment it started from and at every odd step at that assignment’s complement, with probability one.

That is worth stating because it rules out the reading a reader might reach for, which is that the chain mixes very slowly. A slowly mixing chain has a distribution that spreads, and its distance from uniform falls, however gradually. This one’s distance does not fall at all, ever, because the support never grows past two states.

The identity matrix reads the same #

The essay’s argument is that stationarity is invariance rather than attraction, and the diagnostic can be made to say so in one line.

A chain that never moves at all — the identity matrix — is doubly stochastic, preserves the uniform distribution, and sits at a distance of $1 - 1/410$ from it for ever.

That is the same 0.9976. On this measurement the six-swap walk and a chain that does nothing whatsoever are indistinguishable, and both pass the stationarity check the family is usually validated by.

What the second eigenvalue would have said #

The property the check misses has a name and a number, and the family’s other chains supply the scale.

For a reversible chain whose autocorrelation decays geometrically, the integrated autocorrelation time and the second-largest eigenvalue are related by $\tau \approx (1+\lambda)/(1-\lambda)$. The one-swap chain’s τ of 7.30 puts its λ near 0.76; the three-swap chain’s 3.97 puts it near 0.60.

The six-swap chain’s second eigenvalue is exactly −1, in modulus exactly one, and a chain whose second eigenvalue has modulus one has an infinite relaxation time by construction.

So the family runs 0.76, something smaller, 0.60 — and then jumps to 1 at the last member. It is not a gradual deterioration that a coarse diagnostic might miss; it is a discontinuity at the end of a parameter range, and the check everybody runs looks only at the eigenvector belonging to the eigenvalue that is plus one.

Measured rather than argued #

The convergence is computed exactly at every step, which is what makes it a measurement rather than a remark.

Put all the mass on one assignment — the least balanced admissible one, which is the state a rejection sampler is least likely to have handed the chain and the one a burn-in has to cover — and iterate the matrix. The total variation distance from uniform is a sum over 410 states and needs no simulation.

At one swap: 0.7686 after two steps, 0.0849 after twenty, 0.0114 after forty, 0.0002 after eighty. At three swaps: 0.0002 after twenty. At six: 0.9976 at every step there is, and the number of states with any mass on them is one, because after an even number of steps the chain is exactly back where it started.

The 0.9976 is not close to 1 by accident: it is 1 − 2/410, which is the total variation distance between a point mass and a uniform distribution on 410 states. The chain is as far from uniform as it is possible to be while having any mass at all in the right place.

Two more chains in the family that are fine and read oddly #

Between the useful range and the degenerate case sit k = 4 and k = 5, and they are worth a paragraph because they are correct chains whose numbers mislead.

Exchanging five of six from each arm is the complement of exchanging one: the proposal set has the same 36 members, and the acceptance rate is the same 58.8%. So the k = 5 chain is the ordinary one-swap chain with a complement flip applied at every step. It is irreducible and aperiodic, it converges — 0.0029 from uniform after twenty steps — and it is a perfectly usable sampler.

Its autocorrelation time for a symmetric statistic reads 1.43 against the one-swap chain’s 7.30, which would say it mixes five times better. It does not mix better at all: it is the same chain, and its relaxation time — the summary that is a property of the chain rather than of a statistic — is 4.33 against the one-swap chain’s 10.63, which is the honest factor. What the flip does is make successive draws negatively correlated, because the statistic being tracked is odd and the complement reverses its sign, so consecutive draws are an antithetic pair.

That is a genuine variance reduction — antithetic sampling is a real technique and this is one — and it is not mixing. The distinction matters if the chain is used for anything other than averaging an odd statistic: a quantity that is even under complement gains nothing at all from the flip, and would show the k = 5 chain’s true autocorrelation, which is the one-swap chain’s.

Why this is not a curiosity #

Three reasons, in increasing order of how much they should worry a practitioner.

The fold is not exotic. Exchanging k of six is the complement of exchanging six − k, so a chain at k = 5 is the one-swap chain composed with a complement flip, and at k = 4 it is the two-swap chain composed with one. Those are not degenerate — they are irreducible and they converge — but their behaviour is not what a naive reading of bigger steps mix faster predicts, and the antithetic sign flip makes one summary of mixing report a number several times better than the chain deserves.

A tolerance that is not symmetric would hide it. The whole degeneracy exists because the admissible set is closed under complement, which follows from the tolerance being symmetric about zero. A rule with an asymmetric constraint — a minimum number of treated units in a stratum, say — would make the all-swap chain reducible in a messier way, with some states having a complement in the set and some not, and the stationary distribution would still be uniform.

The same failure at trial scale is undetectable. At twelve units the admissible set can be enumerated and the degeneracy is obvious. At two hundred it cannot, the matrix cannot be written down, and the only evidence available is the chain’s own output — which for a periodic chain looks like a series that oscillates, and for a reducible one looks like a series that has settled. A practitioner who has been told to check that the stationary distribution is right has been told to check the one property this failure preserves.

The same distinction, elsewhere in this collection #

It is worth naming the shape, because this is not the first time a check has established a weaker property than the one it was being read for.

A p-value quoted at one over its draw count is right about the grid the statistic can land on and silent about the accuracy, which is √τ worse. An interval’s own scale estimate is right in exactly two cases and looks right in all of them, because the quantity that would show the difference is not the one being reported. An assertion that has never rejected anything passes whatever the code does.

In every case the check is sound and the inference from it is not, and in every case the repair is the same: name the property being used, and find a measurement that fails when it is absent. Here the property being used is convergence from an arbitrary start, and the measurement is a distance from an arbitrary start.

There is a second lesson specific to this one. The power iteration that computes a stationary vector converges to the component of the start along the leading eigenvector, which for a doubly stochastic matrix is uniform. Start it at uniform and it terminates immediately, having confirmed nothing; start it anywhere else and, for a periodic chain, it does not converge at all. The routine that reads a stationary distribution off a matrix and the routine that tests whether the chain reaches it are the same code with a different initial vector, and only one of them is usually run.

What to check instead #

The measurement that would have caught it is the one drawn above: start the chain somewhere specific and watch the distance from the target fall. Started at a point mass it is exactly computable at small sizes and estimable at large ones, and a chain that is not converging says so in the first few steps.

At trial scale the cheap version is to run several chains from very different starting assignments and compare what they report. Two chains started at complementary assignments under an all-swap proposal produce statistics that are exact negatives of each other for ever, which no amount of averaging conceals. That is the ordinary advice about multiple chains, and this is a case where it is the only diagnostic that works: the stationary distribution is right, the acceptance rate is 100%, and the chain has never left a pair of states.

What the check would have to be, and why nobody runs it #

The validation that misses this is not a bad check. It is the right check for a question nobody asked.

Reading a stationary vector off a transition matrix answers does the chain preserve the target. That is invariance, it is genuinely necessary, and for most samplers it is the thing that could plausibly be wrong — the Metropolis correction misapplied, a proposal density asymmetric where the acceptance ratio assumed symmetry, a constraint enforced on one move and not its reverse. When invariance is the fragile property, testing invariance is the informative test.

Here it is not fragile. Every proposal in this family is an exchange of k units between arms, and the reverse exchange is another proposal of exactly the same kind with exactly the same probability. The matrix is doubly stochastic by construction, so uniform is stationary for it, and it is stationary for the all-swap chain in precisely the same way it is stationary for the identity matrix. Invariance was never in question and testing it returns yes for reasons that have nothing to do with whether the sampler works.

The mechanism of the false pass is worth stating on its own, because it generalises past Markov chains: the power iteration that computes a stationary vector is started at the uniform distribution, and the uniform distribution is a fixed point of any doubly stochastic matrix. The iteration therefore returns its own input, at step one, exactly, for a chain that visits one assignment of 410 for ever. It is not that the test is insufficiently sensitive. It is that the test was handed the answer and asked to confirm it.

The diagnostic that does see it costs nothing extra. It is the same code with a different initial vector: put all the mass on one admissible assignment and iterate. A chain that works falls to 0.0002 from uniform inside twenty steps; the all-swap chain sits at 0.9976 and stays there. Total variation from a specific start is the measurement, and the specificity is the whole content — the only thing changed is the one input that was previously chosen to be the thing being verified.

That is the form worth carrying out of this essay and away from samplers altogether. A validation whose input is the expected answer establishes nothing, however elaborate the machinery downstream of it, and it will pass loudly and without qualification on an object that does not work at all.

What is claimed here, and what is not #

This essay takes the difference between a stationary distribution and a limit. The claims are that the all-swap walk on twelve units is doubly stochastic and so preserves the uniform distribution exactly; that it is reducible and periodic, so it visits two assignments for ever and sits 0.9976 from uniform at every step; that the usual validation — read the stationary vector off the matrix — cannot see this, because the power iteration that computes it is started at the answer; and that the diagnostic which does see it is the distance from a specific start, which is exactly computable here and falls to 0.0002 in twenty steps for the three-swap chain.

What stays out and is named as a decision: rules whose admissible set is not closed under complement. The degeneracy here follows from a symmetric tolerance, and an asymmetric constraint would produce a partially reducible chain whose failure is messier and harder to characterise. Nothing here measures one.

The boundary against the essay that built the walk is that it refuses a chain whose stationary distribution is wrong, and this one is about a chain whose stationary distribution is right.

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

One claim is gated in both halves at once. The all-swap chain is required to be exactly uniform in its stationary vector and to be 0.9976 from uniform after a hundred and sixty steps having reached one state of 410, while the three-swap chain is required to be within a thousandth of uniform after the same number. A check that established only the first would pass on both chains, which is the whole point.

The refusal in this field is the proposal chosen from its acceptance rate, and it applies here in its sharpest form: the all-swap chain accepts 100% of its proposals and is the only chain in the family that does not work.