The set a dictionary leaves

There are two ways to draw an assignment from a rerandomisation’s admissible set. Hunt: draw at random and throw away everything inadmissible, at a cost of 1/p attempts per draw when a share p is admissible. Walk: start somewhere admissible, propose swapping a treated unit with a control, take the step if the result is still admissible and stand still if it is not.

The walk is exactly uniform, needs a burn-in, and is dearer than the hunt until the set is very thin. Where the two cross was measured at a tolerance of about 0.19, on one dictionary — and a tolerance is not the only dial. A rule constrained on six functions has a much thinner set than one constrained on three at the same tolerance, so the obvious question is whether the crossing is a fact about the tolerance or about the thinness.

It is the thinness #

The curves lie nearly on top of one another. Measured as the tolerance, the crossing runs from 0.187 at three constraints to 0.355 at four and 0.645 at six — a factor of 3.4, so a rule holding six functions crosses over at a tolerance the three-function rule would call loose. Measured as the share of assignments admitted, the same three crossings are one in 268, one in 217 and one in 176 — a factor of 1.5, and in the opposite order.

So the answer is thinness, and the practical form of it is short. An experimenter deciding how to sample does not need to know what the dictionary is. They need the acceptance rate, which is measurable in a few thousand draws before anything is committed to, and the rule is: below about one admissible assignment in two hundred, walk; above it, hunt.

How much more stable the share is, and how much is left over #

The two readings of the same three crossings are worth putting side by side as ratios, because that is what “the curves lie nearly on top of one another” comes to.

Across three, four and six constraints the crossing tolerance runs 0.187 → 0.355 → 0.645, a factor of 3.45. The crossing share runs one in 268 → one in 217 → one in 176, a factor of 1.52.

So converting from a tolerance to a share removes about 2.3 of the 3.45, and leaves a factor of a half. The share is much the better description and it is not the whole description, which is worth saying plainly: a third of the variation across dictionaries survives the conversion.

And the direction of what is left #

The residual runs the way that is worth noticing.

Since the crossing sits where $1/p = \tau$, the three crossing shares are three readings of the walk’s own cost: 268, 217 and 176 evaluations per usable draw at three, four and six constraints.

The walk gets cheaper as the rule gets stricter — by a third across this range — rather than dearer, which is the opposite of what a thinner set suggests. A tighter admissible set is a smaller graph, and a smaller graph would ordinarily be harder to move around in.

Nothing here explains it, and the size of it is worth recording for whatever does: a rule holding six functions has a walk whose autocorrelation time is 34% below that of a rule holding three, measured at each one’s own crossing tolerance. It is the one part of the collapse the conversion to a share does not account for, and it is the part that would decide whether a single number can be quoted for the crossing at all.

Because the walk’s cost is nearly a constant #

The mechanism is visible in the two costs separately rather than in their ratio.

A hunt’s cost is exactly 1/p, by construction, and across the forty settings measured here it runs from 1.2 attempts per draw to twenty thousand — four orders of magnitude.

A walk’s cost per usable draw runs from 82 to 394, with a mean of 179. Four orders of magnitude against a factor of five.

That is why the crossing is at a thinness rather than at a tolerance: one side of the comparison barely moves, so the crossing is wherever the other side reaches it. The number the crossing sits at — about one in two hundred — is not a constant of nature. It is the walk’s own cost per usable draw, and it would move if the walk were made cheaper.

Why a walk’s cost does not move much #

The walk’s cost per usable draw is the integrated autocorrelation time of whatever statistic is being read along the chain, and two things pull on it in opposite directions as the set gets thinner.

The acceptance rate falls: at three constraints and a loose tolerance the walk takes 93% of its proposals, and at the tight end 19%. A chain that stands still four times in five is a chain that moves slowly.

But the set it is moving over is smaller, so there is less of it to cross. An autocorrelation time is a statement about how long the chain takes to forget where it is, and a thin set has fewer places to be.

The two effects are close enough to cancel that the cost stays inside a factor of five over a range where the alternative changes by ten thousand. That is not an identity and it is not exact — the walk’s cost does rise at the thinnest settings, from about 130 evaluations per usable draw at the loose end to about 300 at the tight one — but against 1/p it is a constant.

How closely the curves actually collapse #

Nearly on top of one another is doing some work in that sentence and it is worth measuring rather than waving at.

Over the band from one admissible assignment in fifty to one in eighty — a region every dictionary but the smallest passes through — the cost ratio reads 0.31 at two constraints, 0.39 at three, 0.31 at four and 0.47 at six. That is a spread of about half, on a quantity that varies by four orders of magnitude across the table.

So the collapse is not exact, and the direction of the residual is worth naming: at a fixed thinness a larger dictionary favours the walk slightly, because the walk’s own cost is a little lower there. A set thinned by many constraints is thin in many directions at once, and a chain moving through it decorrelates in fewer steps than one moving through a set that is thin in one direction and wide in the others.

Half a factor is not nothing and it is not the difference between two methods that differ by ten thousand. The honest statement is that thinness predicts the crossing to within a factor of two on either side, and that no other single number in this problem predicts it at all.

The start the walk still has to pay for #

There is a cost the ratio above leaves out, and at the crossing it is exactly one draw.

A walk has to begin somewhere admissible, and finding somewhere admissible is a hunt. So a walk’s total cost is 1/p once, plus its own per-draw cost times however many draws are wanted. At the crossing — one admissible assignment in about two hundred — the starting point costs two hundred evaluations, which is a little more than one usable draw’s worth of walking.

For a reference distribution of a thousand draws that is a tenth of one per cent and can be ignored. For the ten or twenty draws somebody might take while exploring, it is most of the cost, and the walk has no advantage at all. The crossing is a statement about the marginal draw, and a method whose fixed cost is a hunt cannot beat a hunt on a handful of draws whatever the marginal costs are.

What a practitioner measures instead #

The result turns into an instruction that needs no closed form and no dictionary.

Draw a few thousand assignments at random and count how many are admissible. That is p, it costs a few thousand evaluations, and it is the same measurement the hunt would be doing anyway.

If p is above about one in two hundred, hunt: the expected cost is 1/p per draw and it is under two hundred evaluations. If p is below it, walk — and spend one hunt’s worth of effort finding a starting point, plus a burn-in, before counting any draw as usable.

The number two hundred is this design’s walk cost and not a universal constant. What is transferable is the form: measure the walk’s cost per usable draw once, and the crossing is at the thinness where 1/p reaches it. Both quantities are measurable before any reference distribution is built.

What it does not say #

Two dials produce the same thinness and the sampling comparison cannot tell them apart. That does not make them the same dial, and the rest of this field is about the ways they differ.

They differ in what the rule protects against, which is decided by the parities in the dictionary and not by the tolerance at all: tightening the tolerance on an all-odd dictionary leaves its worst case at exactly zero however thin the set becomes.

They differ in what the set looks like from inside. A set thinned by constraints and a set thinned by tolerance can have the same size and a different shape, and the shape is what a walk moves through — which is the subject of the next essay, where the difference turns out to be a correctness question rather than a cost one.

And they differ in what a randomisation test can resolve. The number of admissible assignments is the number of answers the test can give, and at two hundred units it is astronomically large in every setting here — the share falling from a half to one in twenty thousand takes the count from 2^196 to 2^182, which is not a change any trial notices. Thinness costs sampling effort and nothing else at this size, which is exactly why the sampling comparison is the whole of the cost.

What the acceptance rate hides #

The acceptance rate along the chain and the share admitted in the population are two different numbers, and the gap between them is a fact about the set’s shape rather than its size.

At three constraints and the tightest tolerance measured, one assignment in a thousand is admissible and the chain still takes 19% of its proposals. A chain sitting inside the admissible set is proposing small moves from an admissible starting point, and a small move from somewhere admissible lands somewhere admissible far more often than a fresh draw does — by a factor of nearly two hundred here.

That gap is the whole reason a walk is ever worth running, and it is also what makes the acceptance rate the wrong dial to tune on: it is high wherever the chain is barely moving. The proposal-size measurement makes the same point from the other direction — ranking proposals by acceptance gives the reverse of ranking them by cost — and the two readings are the same statement about the same quantity.

So neither number alone answers the question. The share admitted decides which method to use; the acceptance rate decides nothing, and is the number a chain reports.

Two dictionaries that never cross #

The two smallest dictionaries in the table do not cross over at any tolerance measured. With one constraint the tightest tolerance tried still admits 9.5% of assignments and the hunt costs eleven attempts per draw, against a walk’s three hundred; with two constraints the tightest admits 0.88% and the hunt costs 114 against a walk’s 288.

They would cross eventually — the ratio is rising and the arithmetic does not stop — but the tolerances required are ones nobody would set. Extrapolating the two-constraint curve puts its crossing near one admissible assignment in five hundred, which needs a tolerance below 0.05: a rule that admits an assignment only if its imbalance on two functions is under a twentieth of a standard deviation. A rule constrained on one function at a tolerance of 0.01 is a rule that has thrown away almost all of its randomisation to balance one number, and the reason to reach for a walk is that the set is thin, not that the analyst has tightened one constraint past all reason.

That is the practical shape of the result. A walk is the method for a rule with a rich dictionary at an ordinary tolerance, not for a rule with a poor dictionary at an extraordinary one, and the two look identical from the acceptance rate alone.

The same question at a size that can be enumerated #

Everything above is at two hundred units, where the admissible set has more members than anything can list and every statement about it is sampled. The same two dials can be turned at fourteen units, where every equal split can be walked through and the set is a list.

There the thinness runs out much faster. Four constraints at a tolerance of 0.8 leave 116 admissible assignments of 3,432 — 3.4% — and four constraints at 0.5 leave none at all. Three constraints at 0.5 leave fourteen. A rule that would be ordinary at two hundred units is infeasible at fourteen, which is the small-trial version of the same trade and is not a surprise.

What is a surprise is what those sets look like from inside, and it is not visible at two hundred units because nothing there can be enumerated. That is the subject of the next essay, and it is the reason this one stops at cost: at fourteen units the walk over a thin set is not merely expensive, it is not sampling the set at all.

What is claimed here, and what is not #

This essay takes whether the choice between walking and hunting is decided by the tolerance or by the thinness. The claims are that at two hundred units the crossing sits at one admissible assignment in 268, 217 and 176 for dictionaries of three, four and six functions, against tolerances of 0.187, 0.355 and 0.645; that the walk’s cost per usable draw stays between 82 and 394 evaluations across forty settings while the hunt’s spans 1.2 to twenty thousand; and that the crossing is therefore at whatever thinness makes 1/p equal to a number that does not move.

What stays out and is named as a decision: one proposal size and one statistic. The walk here swaps one unit from each arm, and a proposal that moves more is a different chain with a different cost — measured elsewhere and found to be worth a great deal where the comparison is not decided and nothing where it is. The autocorrelation time is read on one probe statistic that the rule was not handed; a different statistic has a different time, and the constancy claimed above is a claim about this one.

Also out: the number of units. Everything is at two hundred, where the admissible count is astronomical and the only cost of thinness is sampling. At fourteen units the set can be enumerated, the count is a few hundred, and thinness costs something else entirely. The crossing itself should be expected to move with the size — a walk’s autocorrelation time is a statement about how far one swap moves an assignment of n units, and one swap of fourteen is a larger step than one swap of two hundred — and nothing here measures that.

The checks #

Two claims are gated, and one of them is about the shape of the answer rather than about a number in it: the crossing has to be bracketed by the sweep rather than extrapolated past its end, so a dictionary whose curve never reaches the line contributes nothing to the claim. Two of the five here are in that position and are reported as not crossing rather than as crossing somewhere off the chart.

Two claims are gated. The crossing is required to move by more than a factor of two in the tolerance and by less than a factor of two in the share admitted, which is the comparison the essay is named for stated as a test rather than as a reading. And the walk’s cost per usable draw is required to stay inside a factor of eight across the whole table, which is what makes the crossing a statement about the hunt.