A proposal that moves more than two units

The essay that built the walk ends on a sentence that sounds like a technicality and is not: the chain’s autocorrelation time is a fact about the step size and not about the acceptance rate, which reaches 89% at a loose tolerance. A walk that accepts nine proposals in ten and moves two units at a time is correlated because it barely moves, not because it is refused.

The obvious response is to move more units. Exchange k treated units for k control units instead of one for one: the chain takes bigger steps, and it is refused more often because a bigger step is more likely to land outside the admissible set. Something is gained and something is paid, the product has an optimum, and nothing said which side wins.

At twelve units it can be settled without simulating anything at all.

Six matrices, and no chain run #

Twelve units, two balancing functions, a tolerance of one standard deviation on each: 410 of the 924 equal splits are admissible. That is small enough to write down the transition matrix of every k-swap chain and read its properties off directly.

Each chain proposes uniformly among the (6 choose k)² ways of exchanging k units from each arm, takes the proposal if the result is admissible and stands still otherwise. The proposal is symmetric in the two states it connects — drawing k of A and k of B and swapping them is as likely in one direction as the other — so the transition matrix is symmetric, its stationary distribution is uniform, and its eigenvalues are real.

The number that decides everything is the integrated autocorrelation time τ of a statistic the balancing rule was never handed — here the imbalance in the cube of the covariate, which is what a randomisation test’s reference distribution is a distribution of. It is computed as 1 + 2Σρ(t) with ρ(t) = ⟨f, Pᵗf⟩/⟨f, f⟩, evaluated by iterating the matrix on the statistic until the terms vanish. No seed, no draws, no truncation rule.

A chain evaluates one proposed assignment per step whatever k is, so τ is the cost of one usable draw in the same unit a rejection sampler’s 1/p is in. At three swaps the walk costs 3.97 evaluations per usable draw against one swap’s 7.30 — nearly twice as cheap, on a chain that is refused a third more often.

Which makes acceptance the wrong dial #

The instinct a Metropolis rule brings is to tune the proposal until the acceptance rate sits near some target, because in a continuous sampler a rejection is a wasted evaluation of an expensive density. Here it is neither expensive nor wasted in the same sense: evaluating a proposed assignment costs an imbalance update on a handful of columns, and a rejection leaves the chain exactly where it was.

So the ranking comes out backwards. Ranked by acceptance the best proposal is k = 1 at 58.8%; ranked by cost it is k = 3 at 3.97. The two orderings are reverses of each other over the range where the proposal genuinely grows, and a rule tuned on the first would pick the worst of the three.

The relaxation time says the same thing from the spectrum. The second eigenvalue falls from 0.9059 at one swap to 0.6787 at three, so the time to forget a starting point falls from 10.63 steps to 3.11. Two different summaries of mixing, computed from the same matrix in two different ways, both saying the bigger proposal wins.

The fold at half an arm #

The family does not keep growing, and the reason is a structural fact about an equal split rather than anything about balance.

Exchanging k of six from each arm is the complement of exchanging six − k: choosing which five treated units to move is choosing which one to leave. So k = 5 has the same 36 proposals as k = 1, and k = 6 has exactly one — swap everything, which turns an assignment into its own complement.

That means the useful range at twelve units is k = 1, 2, 3, and the counts confirm it: 36, 225 and 400 proposals. Beyond three the family folds back on itself, and at the fold it stops being a chain at all — which is the subject of the next essay.

The fold is a fact about this trial size. At two hundred units the arm has a hundred, the complement is at k = 100, and every proposal size a practitioner would consider is far below the fold.

What a step actually costs, which is not obvious #

The cost accounting deserves a paragraph, because a k-swap step sounds more expensive than a one-swap step and is not.

The imbalance in each balancing column is carried along the chain and updated rather than recomputed. A one-swap proposal changes each column’s total by 2(c_j − c_i) — two multiplications per column. A k-swap proposal changes it by twice the sum of k such differences — 2k multiplications per column. So a k-swap step costs k times as much arithmetic as a one-swap step, and at k = 3 the walk is doing three times the arithmetic per step to buy a factor of 1.84 in steps.

Counted in multiplications, the larger proposal is therefore worse. Counted in assignments evaluated, which is the unit a rejection sampler’s cost is naturally in, it is better. The two units disagree because a hunt’s expensive part is generating and testing a whole assignment — n log n for the shuffle plus nk for the imbalance — where a chain’s step is an update.

This essay counts assignments evaluated, for the reason the field before it gives: it is the only unit in which a walk and a hunt can be compared at all, and the comparison is what the machinery is for. A reader whose bottleneck is arithmetic rather than assignments should read the same table with k as a multiplier on every row, and would then find the one-swap chain ahead — which is a different conclusion honestly reached from the same numbers.

Two routes to the autocorrelation time #

An exact answer read off a matrix is worth nothing if the matrix does not describe the chain somebody would actually run, so the chain is also run.

Forty thousand steps of a walk written from the rule — propose, check the imbalance, accept or stand still — with the statistic recorded at each step and the autocorrelation time estimated by the initial-positive-sequence rule. The two routes are independent: one iterates a 410 × 410 matrix and the other draws random numbers, and neither knows about the other.

They agree. At one swap the run reports 7.00 against the matrix’s 7.30; at two, 4.91 against 4.92; at three, 4.39 against 3.97; at four, 2.88 against 2.74. The worst departure is a tenth of the exact value, which is about what forty thousand correlated steps can resolve.

The counted acceptance rates match to a tenth of a point — 58.5%, 45.0%, 40.9%, 44.7% against 58.8%, 45.0%, 40.8%, 45.0% — and the fourth of those is the fold arriving in the simulation as well.

What the two summaries of mixing are, and why both are reported #

The matrix supplies two numbers that are often used interchangeably and answer different questions, and the difference is visible in the fold.

The relaxation time 1/(1 − λ₂) is how long the chain takes to forget where it started. It is a property of the chain alone and it governs the burn-in.

The integrated autocorrelation time τ is how many steps one usable draw costs, for a particular statistic. It depends on which function is being tracked: a statistic that happens to be nearly orthogonal to the slow eigenvector mixes faster than the chain does.

Over k = 1, 2, 3 the two move together — relaxation 10.63, 4.46, 3.11 against τ 7.30, 4.92, 3.97 — because the statistic being tracked has a healthy component along the slowest mode. At the fold they come apart entirely, and that is where the second summary starts lying: at k = 5 the chain has the same 36 proposals as k = 1 and its relaxation time is back up at 4.33, while τ reads 1.43 — because the complement move flips the sign of the statistic, so successive draws are negatively correlated and an antithetic pair is worth more than two independent ones.

That is a real variance reduction and it is a fact about a symmetric statistic on a set closed under complement, not about mixing. Reporting τ alone across the whole family would say the largest proposals are the best; reporting the relaxation time alone would miss a genuine gain. Both are computed here because each is misleading where the other is not.

The dial that does work is acceptance times step #

If acceptance is the wrong dial, the right one is worth naming, and the two chains that were computed pin it down.

Multiply each proposal’s acceptance rate by the number of units it exchanges, giving the expected units moved per step: 0.588 at one swap and 0.408 × 3 = 1.224 at three. That is a factor of 2.08.

The autocorrelation time falls by a factor of 1.84 over the same range. Multiply the two together and τ × (units moved per step) is 4.29 at one swap and 4.86 at three — within thirteen per cent across a range where each factor separately moves by about a factor of two.

So the cost of a usable draw is very nearly inversely proportional to how far the chain actually travels, which is acceptance and step size together. Tuning either alone tunes half of a product, and the half a Metropolis instinct reaches for is the half that moves the wrong way.

It also predicts the middle chain without reading its matrix. A two-swap proposal accepting somewhere near half the time would move about one unit per step, putting its τ near 4.5 — between the two measured values and much closer to the three-swap chain’s.

What the walk costs against not walking #

There is a comparison at twelve units that puts all of this in proportion, and it is not flattering to the chain.

410 of the 924 equal splits are admissible, which is 44.4%. So a rejection sampler — draw a split uniformly, keep it if it is admissible — costs 1 / 0.444 = 2.25 evaluations per usable draw, in exactly the unit τ is measured in.

The best of the six chains costs 3.97. The worst costs 7.30.

At twelve units the walk loses to plain rejection sampling by a factor of about two, and it loses to it on the very quantity this field measures chains by. That is not an argument against the chain; it is the reason the chain exists. The rejection sampler’s cost is 1/p and p collapses as the trial grows — at fourteen units and a tolerance of 0.8 the admissible share is already 3.4% — while a chain’s τ is a property of the local geometry and does not follow the share down.

The single-swap chain’s acceptance rate is worth one more line for the same reason. At 58.8% it sits fourteen points above the 44.4% a uniform draw would be admitted at, which is the admissible set’s clustering measured directly: a neighbour of an admissible split is more likely to be admissible than a stranger is. That clustering is what a walk trades on and what a rejection sampler cannot use, and it is also why the three-swap chain’s acceptance falls below the uniform share — three swaps is far enough to have left the neighbourhood.

Where this is worth anything #

The exact answer at twelve units is a demonstration rather than an application: at that size the admissible set can be enumerated, a rejection sampler costs 924/410 = 2.25 evaluations per draw, and no walk is competitive with that.

What it establishes is the mechanism, and the mechanism carries. A larger proposal mixes faster and is refused more often; the cost is τ and not 1/acceptance; the ranking by acceptance is not the ranking by cost. Whether the gain survives at trial scale, and whether it survives at the tolerances where a walk is worth using at all, is a separate measurement with an unwelcome answer.

Why acceptance got to be the dial in the first place #

It is worth asking why the wrong summary is the one everybody reaches for, because the answer is not that anybody was careless. The acceptance rate is free. It is a running tally of a decision the sampler has already made, it needs no model of the chain, no eigenvector, no windowing choice, and it is available after a hundred steps. The integrated autocorrelation time is none of those things: read exactly it needs the transition matrix, which exists here only because twelve units have 410 admissible assignments and can be enumerated, and read empirically it needs a long run and a decision about where to truncate the autocorrelation sum — a decision with the same shape as the window a whitening has to choose, and with the same property that the automatic answer is derived for a different quantity.

So the dial that gets turned is the dial that can be read, and it can be read precisely because it does not require knowing the thing the reader is trying to find out. That is the general form, and it is worth stating plainly: a diagnostic that costs nothing usually costs nothing because it is not a measurement of the quantity in question. The acceptance rate answers how often does this proposal get refused. Nobody wants to know that. What they want to know is how many steps does one usable draw cost, and the two are related only through a mechanism — the step size — that neither of them reports.

The two rankings coming out reversed here is therefore not a curiosity about this particular admissible set. It is what happens whenever a cheap proxy is monotone in the wrong argument. A larger exchange moves further, so it decorrelates faster, and it is further from the balanced region, so it is refused more often. Both effects follow from the same fact about the proposal, and they push acceptance and cost in opposite directions. Any family of proposals indexed by how far they move will do this. The reversal is guaranteed by the mechanism, not discovered in the numbers — which is why it is worth writing down once rather than re-measuring on every design.

And the reversal is only visible because both numbers came off the same matrix. Had τ been estimated from a run and acceptance counted from the same run, the comparison would have carried a shared source of noise and the question would have been whether a gap of that size means anything. Here it does not arise: the matrix is the chain, and 7.30 against 3.97 is arithmetic.

What is claimed here, and what is not #

This essay takes what a larger proposal does to a walk over the admissible set. The claims are that every k-swap walk that stands still on a rejection is exactly uniform on the admissible set, read off six transition matrices; that the acceptance rate falls monotonically in k over the range where the proposal grows while the autocorrelation time falls with it, from 7.30 to 3.97; that the ranking by acceptance is therefore the reverse of the ranking by cost; and that the exact times agree with a forty-thousand-step run to within a tenth.

What stays out and is named as a decision: a proposal that is not uniform over its swaps. Every chain here draws its k units uniformly from each arm, which is what makes the proposal symmetric and the stationary distribution uniform without a Metropolis ratio. A proposal that preferred to move units whose covariates are extreme would mix differently and would need an acceptance ratio to stay uniform; nothing here measures it.

The boundary against the essay that built the walk is that it is about whether a walk is uniform and what it costs at one swap, and this one is about the step size. What the same walk’s draws are finally read for is measured further along the field: a weighting that changes between blocks, and the bias that lands in a slope.

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

Two claims are gated. Every proposal size is required to be exactly uniform on the admissible set, to a billionth, at all six — which is not obvious for k > 1 and is the property the whole construction rests on. And the exact autocorrelation times are required to agree with a run’s, at four proposal sizes, to within fifteen per cent: one route iterates a matrix and the other draws random numbers, and neither can confirm itself.

The refusal is the instinct the essay is written against. A proposal size chosen from its acceptance rate is rejected, because the two rankings are reverses of each other: a rejection here costs one evaluation and no movement, so the acceptance rate is not the price of anything.