Walking the admissible set

A rerandomisation test needs draws from the set of assignments its own design rule would have accepted. The standard way to get them is a hunt: draw an assignment at random, compute its imbalance, keep it if the imbalance is inside the tolerance and discard it otherwise. At two hundred units with three constraints and a tolerance of half a standard deviation that costs about nineteen assignments per draw, and the cost is 1/p — so at a tolerance tight enough for the design to be worth having, it is hundreds.

The alternative that suggests itself is a walk. Start somewhere admissible, propose swapping one treated unit with one control, take the step if the result is still admissible, and repeat. It never throws an assignment away.

The construction is one line and one of the lines has a trap in it.

The line that is load-bearing #

Stand still when the proposal fails.

That is the step that looks like waste, and it is what makes the walk correct. The proposal — pick a treated unit uniformly, pick a control uniformly, swap them — is symmetric: the chance of proposing B from A equals the chance of proposing A from B. A symmetric proposal with rejection as a self-loop satisfies detailed balance against the uniform distribution on the admissible set, which is exactly what a rerandomisation test needs.

The optimisation that suggests itself is to keep proposing until a proposal lands, so that no evaluation is wasted. That is a different chain. Its transition probability out of a state is one over that state’s number of admissible neighbours, which is not symmetric unless every state has the same number, and its stationary distribution is proportional to the degree.

The degree is not constant. Enumerating every equal split of twelve units under a two-constraint rule leaves 410 admissible assignments of 924, and their degrees run from 14 to 28 out of the thirty-six possible swaps. So the retrying chain visits the best-balanced assignments 1.32 times as often as uniform and the worst-balanced 0.66 times as often — a factor of two between the two ends, in a construction whose entire purpose is to draw uniformly from a stated set.

The consequence is not subtle. A rerandomisation test’s reference distribution is the distribution of the statistic over the admissible set; drawing from it with weights proportional to degree gives the distribution over a different set, one that over-represents the assignments closest to the middle of the tolerance. Every quantile is wrong and nothing about the output says so.

It is worth seeing why the degree varies, because it says something about the object rather than about the algorithm. An admissible assignment near the middle of the tolerance region can be perturbed in many directions and stay inside it; one pressed against the boundary can be perturbed in few. So the degree is a measure of how far inside the region a state sits, and a chain that samples proportionally to it is over-sampling the interior — which is to say, over-sampling the most balanced assignments, which is precisely the direction that makes a rerandomisation test look better calibrated than it is. The bias flatters the design.

That is the general hazard with a chain whose stationary distribution has not been checked: the failure is not random, it is aligned with whatever made the state acceptable in the first place, and it is therefore aligned with whatever the test is about.

The two ratios agree on a number neither of them states #

The retrying chain’s stationary distribution is proportional to the degree, so the ratio to uniform at each end is that end’s degree divided by the mean degree. Both ratios can be solved for it:

$$\frac{28}{1.32} = 21.2, \qquad \frac{14}{0.66} = 21.2 .$$

The same answer from both ends, which is the check that the distribution really is proportional to degree rather than merely correlated with it — a chain whose weights went as some other increasing function of the degree would give two different answers here.

And the mean degree is worth having for its own sake. 21.2 admissible neighbours out of 36 possible swaps is an acceptance rate of 58.9% for the correct chain, which is what the k-swap family measures directly at 58.8% on this same design. Two constructions, two purposes, one number to a tenth of a point.

Which direction the bias runs #

A factor of two between the ends is a statement about weights, and what matters for a test is which assignments are being over-weighted.

The retrying chain visits the best-balanced assignments 1.32 times as often as it should, because well-balanced assignments have more admissible neighbours. A well-balanced assignment produces a small value of whatever imbalance statistic the test is reading.

So the reference distribution the chain builds is shifted towards small values and is narrower than the true one. An observed statistic compared against it looks more extreme than it is, and the p-value comes out too small.

The optimisation that wastes no evaluations makes a rerandomisation test anti-conservative, which is the one direction an error in a reference distribution must not run. A chain biased towards the badly balanced end would have produced a conservative test and cost only power.

What standing still costs, priced against that #

The waste the correct chain accepts can now be quoted exactly: it stands still on 1 − 0.589 = 41.1% of steps.

Set against a factor of two in the sampling weights and a test that rejects too often, that is a straightforward trade and not a close one. Forty-one per cent of evaluations buys uniformity; the alternative saves them and returns draws from the wrong distribution.

It also puts the walk’s whole value in perspective. At twelve units, plain rejection sampling costs 924/410 = 2.25 draws per usable assignment — cheaper than the walk’s autocorrelation time — so nothing here is worth doing at this size. At two hundred units the same quantity is about nineteen, and at a tolerance tight enough for the design to be worth having it is in the hundreds. The walk earns its correctness argument only where 1/p has run away, and the twelve-unit enumeration is a place to prove things rather than a place to use them.

Proving it rather than measuring it #

The check is worth describing because it is a different kind of check from most on this site.

At twelve units the assignment space is small enough to walk completely: 924 equal splits, of which 410 are admissible under the rule used here. So the transition matrix of each chain can be built — 410 by 410, every entry from the construction — and its stationary vector read off by power iteration.

The standing-still chain’s stationary vector is uniform to within a billionth at every state. The retrying chain’s is proportional to the degree to within a billionth at every state. Neither of those is a simulation result; they are properties of the two matrices, and no number of runs would establish them as sharply.

That matters because the defect is a bias of about a third, and a bias of about a third in a reference distribution’s tail is not something a simulation of a test’s size would reliably catch. It would show up as a rejection rate a point or two off nominal, which is the sort of thing that gets attributed to the number of replicates.

Why detailed balance is the right thing to check #

There is a shorter argument for the standing-still chain that is worth setting beside the matrix, because it is the one that generalises and the matrix is the one that convinces.

A chain has the uniform distribution as its stationary distribution if its transition matrix is symmetric — if the chance of going from A to B equals the chance of going from B to A — because then the uniform vector is left unchanged by it. The swap proposal is symmetric by construction: there are the same number of ways to propose B from A as A from B, since both are pick one treated, pick one control. Admissibility is a property of the destination, so a proposal is accepted from A to B exactly when it would be accepted from B to A: both require B to be admissible, and A already is. So the off-diagonal entries are symmetric, and the diagonal absorbs whatever is left.

Re-proposing breaks the symmetry in one place and one place only: the amount of probability that has to be redistributed out of a state depends on how many admissible neighbours it has, and states differ in that. So the off-diagonal entry from A to B becomes 1/deg(A) rather than 1/36, and 1/deg(A) is not 1/deg(B).

The whole defect is one division by a state-dependent quantity, which is the reason it is so easy to introduce and so hard to notice: the code for it is shorter than the code for the correct version.

The cost the walk does not remove #

The walk has to start somewhere admissible. There is no way to find such a point except to hunt for one — which is a rejection sampler, run once.

At a tolerance of 0.18 standard deviations, where about one assignment in four hundred is admissible, the hunt takes 496 draws before the walk can begin. At 0.14 it takes 909. Those are not small numbers and they are exactly the numbers the walk was supposed to avoid.

The walk does not remove the acceptance cost. It pays it once and amortises it over the run. That is a real improvement — 1/p once rather than 1/p per draw — and it is a different claim from the one the construction is usually sold with, and the difference matters for a short run. A test using two hundred draws at a tolerance where the acceptance rate is one in four hundred pays 496 for its start and then two hundred steps; a rejection sampler pays eighty thousand. A test using two hundred draws at a tolerance where the acceptance rate is one in five pays five for its start and then two hundred steps, against a thousand — and by then the walk’s draws are so correlated that the comparison goes the other way, which is the next essay.

How long it has to be given #

A walk started somewhere is not uniform until it has forgotten where it started, and how long is a question that usually gets answered by convention. Here it can be answered exactly.

The walk is started at the least balanced admissible assignment — the state whose imbalance vector is longest, which is the state a rejection sampler is least likely to have handed it and the one a burn-in has to cover. The distance from uniform is then computed at each step by multiplying a distribution by a matrix, with no sampling anywhere.

It is 0.9976 at the start, 0.5024 after five steps, 0.1955 after twelve, 0.0849 after twenty, 0.0309 after thirty, 0.0069 after forty-five and 0.0001 after ninety.

So a burn-in of twenty steps on twelve units leaves an eleventh of the distribution in the wrong place, and ninety steps leaves a ten-thousandth. Both of those are cheap. The point is not that the burn-in is expensive; it is that it is not zero, and that a construction whose selling point is that no evaluation is wasted spends its first several dozen evaluations producing draws that are not from the distribution it claims.

The scaling is the part that does not transfer. Twelve units have thirty-six possible swaps and a diameter of six; two hundred units have ten thousand swaps and a diameter of a hundred, and the walk’s relaxation time grows with the trial. What can be computed exactly at twelve has to be estimated at two hundred, which is exactly the situation the essay on estimating an admissible count runs into from the other direction.

What the exact calculation is not #

Twelve units is not a trial. It is an object small enough to have every question about it answered exactly, and the point of answering them there is that the answers are qualitative rather than numerical.

Qualitative and transferable: standing still gives uniformity; re-proposing gives the degree; the degree is not constant; a burn-in is needed. Each of those is a statement about the construction and none of them depends on the size — the detailed-balance argument is the same at two hundred units, and so is the observation that a state near the boundary has fewer admissible neighbours.

Numerical and not transferable: twenty steps, ninety steps, 410 of 924, a factor of two between the extreme degrees. Every one of those grows or shrinks with the trial, and the direction is the uncomfortable one — a larger trial has a larger diameter and a slower walk, so the burn-in that is cheap here is not cheap there.

The awkwardness is that the exact calculation is available exactly where it is not needed. At twelve units nobody needs a walk; the whole set can be enumerated and the test computed without any sampling at all. At two hundred units the walk is the only option and none of these quantities can be computed — they have to be estimated from the walk itself, which is the situation every diagnostic for this class of algorithm exists to handle and none of them handles well.

So the exact answer is a warrant for the construction rather than for any run of it, and that is worth being explicit about rather than letting a reader assume the twenty steps transfers.

What the walk is actually for #

Two things it does that a hunt cannot, and they are worth separating from the cost argument.

It reaches sets a hunt cannot. At six constraints on two hundred units the acceptance rate falls below one in ten thousand, and a rejection sampler’s cost per draw becomes prohibitive before the admissible set becomes small — the set still contains an astronomical number of assignments, and there is simply no cheap way to sample one. The walk’s cost per step does not depend on the acceptance rate at all; only its correlation does.

It gives a handle on the set’s shape. The degree distribution — how many admissible neighbours each admissible assignment has — is a description of the set that a hunt never produces, because a hunt never looks at two admissible assignments next to each other. That the degrees here run from 14 to 28 is a fact about how ragged the boundary of the tolerance region is, and it is the fact that makes the retrying chain wrong.

Neither of those is the reason the construction is usually reached for. The reason is cost, and cost is where it turns out to be worse than a hunt at every tolerance a trial is actually designed at.

What is claimed here, and what is not #

This essay takes a walk over the admissible set in place of a hunt for members of it, and the claims are that standing still on a failed proposal makes the walk exactly uniform, that re-proposing instead makes it exactly proportional to the degree, that the degree runs from 14 to 28 over the 410 admissible assignments of twelve units so the two chains differ by a factor of two between the extreme states, and that a burn-in from the worst starting point is 0.0849 away from uniform after twenty steps and 0.0001 after ninety.

What stays out and is named as a decision: importance sampling, which is the other way of avoiding a hunt and which trades a correlation for a weight; any proposal other than a single swap, which would mix faster and is a different chain to prove things about; and the whole cost accounting, which is the next essay.

The boundary against the essay on estimating an admissible count is that it is about a number — how many assignments survive a rule — where this one is about drawing from them. The count is the quantity a hunt estimates badly at small acceptance rates, and a walk does not estimate it at all.

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

Three claims are gated in this field’s library, and all three are read off a transition matrix rather than from runs. The standing-still chain’s stationary distribution is required to be uniform to within a billionth. The degrees are required to differ, since two chains that agreed would make the distinction pedantry. And the burn-in is required to start above 0.9 and fall monotonically below 0.05, which is a claim that the chain both needs time and is given enough of it.

The refusal for this essay is a chain that re-proposes instead of standing still. It is proved rather than measured: its stationary vector matches the degree to a billionth, and the degree is not constant, so the reference distribution it produces is a distribution over a set nobody specified.