What a reference distribution costs to sample

A randomisation test conditions on the rule that produced the assignment. Whatever the rule was, the reference distribution is the statistic over the assignments the rule could have produced — and for a rerandomisation, that is the admissible set: the assignments whose imbalances are inside the tolerance.

At sixteen units the admissible set can be walked, so the reference distribution is exact and the p-value is a ratio of two integers. At two hundred units it cannot be, and the admissible set is not small — about 2^194 of them — so the difficulty is not that there are too few. It is that finding them is a search, and everything about the test’s cost and its resolution follows from the price of that search.

The price of one admissible draw #

Rejection sampling: draw an assignment at random, keep it if it is admissible, otherwise draw again. The expected number of attempts per kept draw is 1/p, and p is the acceptance rate, which does not depend on the size of the trial and falls geometrically in the number of constraints.

At a tolerance of one coin-spread, collecting a thousand admissible assignments costs about 1,465 attempts at one constraint, 2,146 at two, 3,143 at three, 4,604 at four, 6,743 at five and 9,878 at six.

Those are small numbers, and that is the point. Ten thousand random assignments of two hundred units is a fraction of a second. The cost of a rerandomisation test at a real trial size is not a barrier, and the field before this one is what says why: the acceptance rate does not fall with n, so the price per draw is the same at two hundred units as at twenty thousand.

Where it does become a barrier is in the exponent. Ten constraints at the same tolerance costs about 9·10⁴ attempts per thousand draws; twenty costs about 10⁹; and a tolerance of a tenth rather than one multiplies the base by a factor of twelve, so four tight constraints cost more than twenty loose ones. The budget is geometric in the constraints and geometric in the tolerance, and neither of those is a quantity anybody has intuition about.

A p-value made of a thousand pieces #

The second cost has nothing to do with computation and is the one that gets misreported.

A reference distribution built from B admissible draws returns a p-value that is a multiple of 1/(B + 1). At B = 1,000 the resolution is 9.99·10⁻⁴. There is nothing between the multiples — not a value the test declines to report, but a value the test cannot produce — and a p-value written to four decimal places is claiming 10 times the resolution the draws contain.

That is not a rounding convention. It is the arithmetic of the estimator, and it composes badly with everything downstream. A Bonferroni correction over twenty comparisons wants a threshold of 0.0025, which a thousand draws resolves to two or three of its own steps; a claim of p < 0.001 is a claim about a quantity the procedure cannot distinguish from p = 0.001.

And buying the digits is linear. Resolving p to 10⁻⁴ needs about ten thousand draws, which at six constraints is about a hundred thousand attempts; resolving to 10⁻⁵ needs a hundred thousand draws and a million attempts. That is affordable, and it is affordable only because the acceptance rate does not fall with the trial size — which makes the previous essay’s finding the reason this essay’s costs are manageable rather than a separate result.

There is a second error term underneath the granularity and it is larger, and it needs care because the test itself is exact. The sampled p-value is a valid test statistic in its own right — that is the next section — but as an estimate of the p-value the full enumeration would have given, it is a binomial proportion: a true value of 0.05 estimated on a thousand draws has a standard error of about 0.0069, seven times the granularity.

Those are two different questions and both get asked of the same number. Is my test valid? — yes, exactly. Would a different seed have given a materially different number? — yes, by about seven steps of the grid. Anybody comparing two analyses of the same trial, or reproducing somebody else’s, is asking the second, and the resolution is not the accuracy: a p-value reported to the granularity is being reported an order of magnitude more precisely than a rerun of the same procedure would reproduce it.

Where the budget actually goes #

It is worth laying the two costs side by side, because they trade and the trade is not the obvious one.

A test costs B/p attempts. B sets the resolution and p is fixed by the design. So for a stated computational budget the analyst chooses B, and every extra digit of resolution costs a factor of ten.

The instinct is that a tight tolerance is expensive. It is, and it is expensive in a way that buys something: a tighter tolerance means better balance, which means a more precise estimate. The balancing field prices that side.

The instinct that is wrong is that more constraints are expensive because they leave fewer assignments. They do not leave fewer in any sense that matters — six constraints at two hundred units leave about 2^192 — they leave a lower rate, which is a computational cost and nothing else. So the honest budgeting question is not whether the interactions can be afforded, it is whether (2Φ(a) − 1)⁻ᵏ attempts per draw can be, and at the numbers in this essay the answer is yes by several orders of magnitude.

There is a third cost that is easy to overlook and is the only one that grows with the trial. Each attempt requires computing k imbalances over n units, so the work per attempt is O(nk). The attempts do not grow with n; the work per attempt does, linearly. That is the whole of the trial size’s appearance in this budget, and it is the mildest dependence in the essay.

Why a sampled reference distribution is still a reference distribution #

One conceptual point deserves stating, because the granularity makes it easy to think of the sampling as an approximation to a test rather than as the test.

It is not an approximation. Conditional on the B admissible draws, comparing the observed statistic against them and reporting (number at least as extreme + 1)/(B + 1) is an exact test: under the null, the observed assignment is exchangeable with the B drawn ones, so the p-value is uniform on the multiples of 1/(B + 1) and rejecting at or below a level that is one of those multiples has exactly that level. The +1 in numerator and denominator is what makes it exact rather than approximate, and it is not a continuity correction.

So B does not control bias. It controls resolution and power: with a thousand draws the smallest reportable p-value is 1/1001, so no evidence however strong can produce a smaller one, and a test at level 0.001 is impossible. That is the sense in which a small B costs — not accuracy, but the range of conclusions available.

A sampled randomisation test is exact at a coarse resolution, not approximate at a fine one, and the two descriptions license quite different sentences.

Nothing found is not nothing there #

The third cost is the one that produces wrong statements rather than imprecise ones.

Sampling can return zero acceptances. The estimate is then 0, the count is 0 × C(n, n/2) = 0, and the natural sentence is there are no admissible assignments. That sentence is almost always false.

Twenty thousand draws with no acceptance bounds the rate above by 1.5·10⁻⁴ — the rule of three — and multiplying that bound by C(200, 100) still leaves about 2^183 admissible assignments. The honest statement is a bound, and the bound is enormous.

This is not a hypothetical. The essay before this one measures a real rule that produces it: a balancing function that is a cut in the covariate’s tail, under an ellipsoid whose radius came from a normal approximation, accepts nothing at all in twenty thousand draws where the closed form promised 5.0%. Both numbers are wrong in the same direction about the same rule and neither of them is the count.

A zero from a sampler is a statement about the sampler. The two repairs are both one line: report the rule-of-three bound, and loosen the tolerance until the sampler returns something, which changes the test rather than merely making it feasible and therefore has to be recorded.

Two constraints that cost the same and are not the same #

One more asymmetry is worth a paragraph, because it decides how a budget should be spent.

The acceptance rate is (2Φ(a) − 1)^k in the limit, which is symmetric in the constraints: every function costs the same factor, whatever it is. Balancing the covariate and balancing its fourth power both multiply the rate by about two thirds at a tolerance of one.

What they buy is not symmetric at all. A rule balancing the covariate removes 2/π of a median split of it and everything of a linear outcome; a rule balancing its fourth power removes almost nothing of either, and buys protection only against outcomes shaped like a fourth power, which is a shape few people believe in. The maximin field is entirely about that asymmetry.

So the budget should be spent by what a constraint buys and not by what it costs, and the costs are uninformative because they are all the same. That is a mildly unusual situation — most trades in this fleet have a price that varies with what is bought — and it means the answer to which functions is settled by the geometry alone, with the sampling cost entering only as a ceiling on how many.

The dial that must not be tuned on the answer #

The tolerance is a dial, and it is exactly the kind of parameter people try a few settings of. It must not be.

Loosening the tolerance admits more assignments, which makes the reference distribution wider, which makes the observed statistic less extreme. Tightening it does the reverse. So the p-value is a monotone-ish function of a parameter the analyst controls, and trying three tolerances and reporting the smallest p-value is a search over reference distributions.

The neighbouring field measures exactly this on a different dial: taking the smallest p-value over eight block lengths of a bootstrap rejects 20.0% of true nulls against 3.3% for a length chosen in advance. Nothing about the shape of that result is specific to bootstraps. A dial that moves a reference distribution and is chosen after the statistic is seen is a search, and a search costs what a search costs.

The difference here is that the tolerance is chosen before the trial runs, because it is part of the randomisation — the assignment was produced under it. So the discipline is free: an analyst physically cannot tune the tolerance on the outcome without re-randomising the trial, and if they do re-randomise the trial the tolerance is recorded in the assignment. This is one of the few dials in this fleet whose honest setting is enforced by the mechanism rather than by the analyst.

What is not enforced is the number of draws. B can be chosen after seeing a p-value hovering near a threshold, and another nine thousand draws, because the first thousand were inconclusive is a sequential procedure with an unreported stopping rule — the same defect this site measures elsewhere, arriving in the Monte Carlo layer rather than in the data.

What a p-value from this procedure is a statement about #

Three things have to travel with the number, and none of them is optional.

The tolerance and the basis. The reference distribution is over the admissible set, and the admissible set is defined by both — and a box in one basis is not a box in another, so naming the span is not enough.

The number of admissible draws. It sets the resolution and the standard error, and without it the digits are uninterpretable.

And whether any were found. A test built on a sampler that accepted eleven assignments is a different object from one built on a sampler that accepted ten thousand, and the p-value alone does not say which.

None of that is a technique. It is a record of what happened, which is what a randomisation test always required and which the sampling layer adds three lines to.

What the sixteen-unit case had that this does not #

It is worth closing on what is lost, because the previous essay’s finding is good news and this one is the bill.

At sixteen units the reference distribution is the complete admissible set. The p-value is a ratio of two integers, it is reproducible to the last digit by anybody with the same data and the same rule, and its resolution is 1/3,874 or whatever the admissible count happens to be — set by the trial rather than by a budget. There is no seed anywhere in it.

At two hundred units none of that survives. The reference distribution is a sample, the p-value depends on a seed, its resolution is a choice, and two honest analysts of the same trial with the same rule will report different numbers. That is not a defect of the method; it is what conditioning on a set of size 2^194 costs.

The repair is the one this site applies to every simulated quantity and it is the site’s own premise: the seed is part of the result. A sampled randomisation test is reproducible if and only if the seed, the number of draws, the tolerance and the basis are reported with the p-value, and it is not reproducible otherwise. Four numbers, none of which is currently conventional to print.

What is claimed here, and what is not #

This essay takes the price of a sampled rerandomisation reference distribution, and the claims are the attempts per draw at each number of constraints, the granularity of 1/(B + 1) against the far larger binomial standard error, the rule-of-three bound where nothing is accepted, and the difference between a dial the mechanism enforces and one it does not.

What stays out and is named as a decision: any measurement of power, which needs a false null and a stated effect and is not attempted; the choice of tolerance, which belongs to the trial’s design rather than to its analysis; and importance sampling or Markov-chain schemes for the admissible set, which would remove the rejection cost and introduce a correlation between draws that the granularity arithmetic here assumes away.

The boundary against the essay before it is that this one spends the rate rather than measuring it. That the rate does not depend on the trial size, that it falls geometrically in the constraints, and that the count is astronomical regardless are established there.

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

The claims here are arithmetic rather than measurement, and the field’s library gates them as such: the acceptance rate at each constraint count is required to match the closed form, and the cost per thousand draws is computed from it rather than timed, so a figure that quoted a cost without a rate behind it could not be built.

The refusal is a p-value quoted finer than its draws. A reference distribution of a thousand admissible assignments resolves p to 9.99·10⁻⁴ and cannot return anything between its multiples, so four decimal places claim ten times the resolution the draws contain — and the check refuses the report rather than the test, because the test is correct and the sentence written about it is not.