Draws that repeat each other

The field that priced a rerandomisation test’s reference distribution ends on two statements. Hunting for admissible assignments costs 1,465 evaluations per thousand draws at one constraint and 9,878 at six. And a p-value from a thousand admissible assignments resolves to multiples of 9.99·10⁻⁴ and cannot return anything between them — which is a refusal in that field’s library, because quoting a p-value finer than the grid its draws put it on is quoting precision that is not there.

Both statements assume the draws are independent. A walk’s are not, and neither statement survives.

The unit both costs have to be in #

Comparing a hunt with a walk means picking a unit, and there is only one honest choice: assignments evaluated per usable draw.

A hunt evaluates 1/p assignments and produces one draw that is independent of every other. A walk evaluates one assignment per step and produces a draw every step — but its draws are correlated, so B of them are worth B/τ independent ones, where τ = 1 + 2Σγ_k is the integrated autocorrelation of whatever the reference distribution is a distribution of.

So the two costs are 1/p and τ, and they cross where p = 1/τ. Nothing else in the comparison matters asymptotically: the walk’s start-up hunt is 1/p paid once, which vanishes over a long run.

At two hundred units with three constraints, the numbers are these:

The crossing is at a tolerance of 0.194 standard deviations, where about one assignment in four hundred is admissible.

That is far tighter than any trial is designed at. A rerandomisation tolerance is chosen to remove most of the imbalance without leaving the assignment nearly deterministic; the tolerances people actually use sit between half a standard deviation and one, and at both of those the hunt is cheaper by more than an order of magnitude.

It is worth reading the table’s left-hand end, because it is where the intuition is most wrong. At a tolerance of 1.2 standard deviations — a loose rule, admitting nearly half of all assignments — a hunt costs two evaluations per draw and a walk costs 136. The walk is sixty-one times dearer in the regime where it looks most obviously sensible, and it is dearer there for a reason that has nothing to do with rejection: it accepts nearly every proposal and each accepted proposal moves almost nowhere.

The two constructions fail in opposite regimes and neither failure is about the other’s mechanism. A hunt is expensive when the set is small. A walk is expensive when the set is large, because a large set takes a long time to cross two units at a time.

Why the walk is so correlated #

The autocorrelation time is between one and two hundred for a two-hundred-unit trial, and the reason is arithmetic rather than pathology.

A step swaps two units of two hundred. Whatever statistic the reference distribution is about — an imbalance in a function the rule was not handed, a treatment-effect estimate under a sharp null — is a sum over units, and a swap changes two terms of it. So the statistic moves by an amount of order 1/√n of its own spread per step, and it takes of order n steps to travel across its own distribution.

Two consequences follow and neither is fixable by tuning the tolerance.

The acceptance rate is not the problem. At a tolerance of 1.2 the walk accepts 89% of its proposals and still has τ = 136. Almost every step is taken and almost every step is tiny. Making the walk accept more would not help; it already does.

A larger trial is worse. τ grows with n while 1/p does not depend on n at all — the acceptance rate of an orthonormal-basis rule at a stated tolerance approaches (2Φ(a) − 1)^k, which contains no n, which is a result the neighbouring field measures directly. So the comparison moves against the walk as the trial grows, which is the opposite of what a scaling argument would suggest.

The obvious repair is a bigger step — swap several pairs at once — and it is not free: a proposal that moves more units is a proposal that is more often outside the tolerance, so the acceptance falls as the step size rises, and the product of the two has its own optimum. That is a real construction and it is not measured here.

The hunt has a hidden advantage the accounting keeps #

There is a asymmetry in the two constructions that the cost table already contains and that is worth naming, because it is the reason the crossing is where it is rather than somewhere looser.

A hunt’s draws are independent of each other and of everything else. There is no burn-in, no diagnostic to run, no question about whether the sampler has found the whole set, and no statistic whose autocorrelation has to be measured before the output means anything. The 1/p is the entire cost and it is known in advance from the tolerance and the number of constraints.

A walk’s τ is none of those things. It has to be estimated from the run, it differs between statistics computed on the same run, and estimating it well needs a run several times longer than the autocorrelation itself — which is a chicken-and-egg problem every practitioner of these methods knows and none of them solves cleanly. A run of four thousand steps at τ = 180 contains about twenty-two effective draws, and estimating an autocorrelation time from twenty-two effective draws is not a measurement.

So the honest comparison is worse for the walk than the table says. The table prices τ as though it were known; in practice a run has to be long enough to establish it, and that run is the cost. The numbers here come from runs of fifteen thousand steps, several designs each, which is more than anybody would spend to compute one p-value.

The p-value’s grid, and what replaces it #

The refusal about granularity has to be restated for a walk, and it gets worse rather than better.

For B independent admissible draws a p-value lives on the grid of multiples of 1/(B + 1), and its Monte Carlo standard error near 0.05 is √(p(1 − p)/B). For B chain draws the grid is still 1/(B + 1) — that is a property of counting, not of independence — but the standard error is √(p(1 − p)/ESS) with ESS = B/τ, which is larger by √τ.

At a tolerance of 0.6 on two hundred units the walk’s autocorrelation time is around a hundred and eighty, so twenty thousand steps buy about a hundred and ten effective draws. A p-value reported to three decimal places from twenty thousand chain draws is reporting a grid it has, and an accuracy it does not: its standard error near 0.05 is about 0.021, where twenty thousand independent draws would give 0.0015.

The grid and the accuracy coming apart is the specific hazard, because the grid is what a practitioner sees. A p-value of 0.0374 from twenty thousand draws looks like a number with four significant figures in it. Three of them are the arithmetic of a ratio and none of them is information.

So the honest statement for a chain has two numbers in it: the p-value, and the effective number of draws behind it. And the second is not a property of the algorithm alone — it depends on the statistic, since a statistic that mixes fast and one that mixes slowly on the same chain have different τ.

What the closed acceptance rate is doing in the table #

One column of the table above is worth a note, because it is the same result the neighbouring field warns about arriving in a new place.

The acceptance rate for an orthonormal basis of k functions at a tolerance of a standard deviations approaches (2Φ(a) − 1)^k, which contains no trial size. At a = 0.9 that closed form gives 0.25229 and the counted rate is 0.24341; at a = 0.5, 0.05615 against 0.05390; at a = 0.18, 0.00291 against 0.00252.

The closed form is high by three to four per cent through most of the range and by fifteen per cent at the tightest tolerance measured. That is the limit arriving late, which is a fact about the tail of the imbalance distribution rather than about the size of the trial — the same finding the field that measured the rate reached from the other side.

For the cost comparison it matters in the direction that flatters the walk: using the closed rate makes the hunt look cheaper than it is, so the crossing computed from the closed form is at a slightly looser tolerance than the crossing computed from counts. Both are reported and the counted one is the one above.

Two quantities with the same name #

The phrase effective sample size appears twice in this round and means two different things, and this is the good one.

In the other field it is n(1 − ρ)/(1 + ρ): how many independent observations a dependent sample is worth. That quantity turns out to be a property of the sample and of one estimator, and applying it outside that estimator is what an entire essay is about refusing.

Here it is B/(1 + 2Σγ_k): how many independent draws a dependent sampler is worth. And here the substitution is correct, because what a Monte Carlo estimate is doing genuinely is an average with equal weights over the draws — that is what a p-value from a reference distribution is, a proportion — and the inflation factor is exactly right for an equally weighted average.

The arithmetic is identical and the warrant is not. One is a statement about what a design matrix can extract from correlated rows, which depends on the design matrix; the other is a statement about what an average can extract from correlated draws, which does not depend on anything else. The second is why the number above can be quoted without a qualifier and the first cannot.

One cost moves and the other barely does #

The crossing exists because the two costs respond to the tolerance at wildly different rates, and the table says by how much.

Across the whole sweep, from a tolerance of 1.2 down to 0.14, the hunt’s cost rises from 2.2 evaluations per draw to 662 — a factor of 296. Over the same range the walk’s autocorrelation time rises from 136 to 360, a factor of 2.65. The ratio between them therefore moves by a factor of 112, and it is that movement, almost entirely one-sided, that produces a crossing at all.

Read as rates against the tolerance a, the hunt’s cost behaves like a⁻²·⁶ and the walk’s like a⁻⁰·⁵ — the hunt paying for the tail of a k-dimensional normal being cut off, the walk paying only for the admissible set being slightly harder to move around in. Extrapolating the ratio from the loosest tolerance in the table under that description puts the crossing at a ≈ 0.19, which is the 0.194 counted directly. The crossing is bracketed by the measurements rather than reached by the extrapolation, and the agreement is what says the two rates are the whole story.

So the walk’s cost is nearly a constant of the trial and the hunt’s is nearly all tolerance. That is the useful form for an experimenter, because it says which quantity to look up. A hunt’s cost can be computed from the tolerance and the number of constraints before anything is run — the closed rate in the table is what the field that measures it supplies. A walk’s cost cannot be computed from anything; it has to be measured, on the statistic in hand, from a run long enough to measure it.

How many digits a chain’s p-value has #

The √τ inflation is a statement about a standard error, and converting it into digits is what makes it actionable.

To match B independent draws a chain needs Bτ steps. At the τ ≈ 180 of a tolerance of 0.6 on two hundred units, a p-value as accurate as one from twenty thousand independent draws would take three and a half million steps. Nobody runs that, so the practical question is the reverse one: given a run of B steps, how much of the number should be written down.

The answer is one over the root of the effective count. Twenty thousand steps at τ = 180 give about a hundred and ten effective draws, so the standard error is 0.021 near p = 0.05 and about 0.048 near p = 0.5. Two decimal places is the most such a p-value has, and the second of them is uncertain. A run would need τ times as many steps to add each further digit-and-a-half, which at τ = 180 means a hundredfold for one more decimal.

Reporting it as p = 0.04 from 110 effective draws is therefore both shorter and more informative than p = 0.0374 from 20,000 draws, and it is the reporting convention this whole accounting argues for. The count that belongs beside a chain’s p-value is the effective one, in the sense the sampler’s version of that quantity shares its arithmetic with and not its warrant — and it is the only number in the output that says how much of the grid is real.

What the walk is for, given all that #

The comparison is against the walk and it does not settle the question, because cost is not the only axis.

Where the hunt cannot start at all. At six constraints on two hundred units the acceptance rate falls below one in ten thousand, and the admissible set still contains an astronomical number of assignments — the count is the rate times a binomial coefficient with sixty digits in it. There is nothing wrong with the set; there is no cheap way into it. A walk’s cost per step is unaffected.

Where the tolerance is genuinely tight by design. A trial with many covariates and a strict balancing requirement is exactly the regime the crossing sits in, and it is not a hypothetical: the tolerance falls as the constraints multiply if the joint requirement is held fixed.

Where the set’s shape matters. A walk produces the degree distribution of the admissible set as a by-product, and a hunt never sees two admissible assignments next to each other.

None of those is the walk is cheaper, and the reason to be careful about the claim is that it is the claim the construction is usually introduced with.

What is claimed here, and what is not #

This essay takes what a walk over the admissible set costs against a hunt for members of it, and the claims are that the two costs are 1/p and τ in the same unit, that they cross at a tolerance of 0.194 standard deviations where about one assignment in four hundred is admissible, that the walk’s autocorrelation time is between 136 and 360 across the sweep and is not caused by rejection since the acceptance rate reaches 89%, and that a p-value from B chain draws carries a standard error larger by √τ than one from B independent draws.

What stays out and is named as a decision: a multi-swap proposal, which would mix faster and accept less and has an optimum nobody here has found; importance sampling, which removes the correlation and introduces a weight; and any variance-reduction on the chain, since a construction that has not been proved uniform is not worth accelerating.

The boundary against the essay that built the walk is that it is about correctness and this one about cost, and the order matters: a chain that samples by degree is cheap and useless.

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

Two claims are gated in this field’s library. The walk’s draws are required to be autocorrelated — τ above 1.5 and an effective count below four fifths of the step count — which is the fact the whole accounting turns on. And the cost ratio is required to cross: below one at the loosest tolerance measured and above one at the tightest, so that the crossing is bracketed rather than extrapolated to.

The refusal for this essay is a chain’s p-value quoted at one over its number of draws. The grid really is 1/(B + 1) and the accuracy is not, and the two coming apart is what makes a four-figure p-value from a walk look like a measurement.