Why count assignments?
The previous chapter used the bootstrap to approximate the sampling variability of an estimator by resampling the observed data with replacement. This chapter studies a test whose validity is exact for a fixed, finite number of units. The validity comes from a probability mechanism we can name precisely. That mechanism is either the random assignment of a treatment or the exchangeability of observations under a null distribution.
The same reasoning appears in data evaluation. Examples include comparing a modified system against a baseline on randomly assigned users, or asking whether a classifier's accuracy could arise from labels unrelated to features. In each case the central question is the same: which relabelings of the data were equally possible, and why? A permutation test is only as trustworthy as the answer to that question.
The design-based setting
Fix units, labeled , and an integer with . Write .
Potential outcomes. Each unit has two fixed numbers: , the outcome it would show if treated, and , the outcome it would show if untreated. These are not random. Writing them this way assumes that unit 's outcome depends only on its own treatment and not on the treatments of other units.
Assignment. Let be the set of all subsets with , and let . The treated set is drawn uniformly from , independently of the potential outcomes:
This is complete randomization. The only randomness in the problem is the choice of .
Observed outcomes. Unit shows if and otherwise.
In general we cannot recompute what the data would have looked like under a different assignment, because half of each unit's potential outcomes are unobserved. A null hypothesis that fills in the missing half changes this.
Definition 7.6.1
(Fisher's sharp null)
The sharp null hypothesis is for every unit .
Under this hypothesis write for the common value. Then whatever turns out to be. The observed vector is the same under every assignment, so the outcomes for every hypothetical assignment are known exactly.
Test statistic. Before looking at the data, fix the difference in means
Under the sharp null, is computable from the observed data for every , not only the realized .
Definition 7.6.2
(Randomization -values)
The upper-tailed p-value is
and the absolute-value two-sided p-value is
The observed assignment is always counted, so both p-values are at least .
A complete enumeration
Worked example 7.6.3
(Four units, two treated, outcomes )
Take and , so . The observed outcomes are , with total , and the observed treated set is . Here and below, units are named by their outcome values. For a treated pair with sum , the treated mean is and the control mean is , so .
| Treated set | Treated mean | Control mean | |
|---|---|---|---|
The observed statistic is . Only one assignment satisfies , so .
Two assignments satisfy , namely and , so .
The smallest attainable upper p-value is . This nonrandomized counting test cannot reject at level for any outcome of this design. The obstacle is that the design has only six equally likely assignments, not that the data are uninformative.
The explorer below lists every assignment of the design with its exact statistic, groups the tied values, and compares the exact rejection probability with the level for the observed treated set you choose.
No normal approximation and no continuity correction appear here. The reference distribution is the exact list of six values. Ties, when present, are handled by the inequality in the definition, as the next theorem shows.
Exact validity, including ties
Theorem 7.6.4
(Super-uniformity of the randomization p-value)
Assume complete randomization and the sharp null. Let be any real-valued statistic of the assignment, computed from the fixed outcome vector and chosen before the data are seen; for example or . Define . Then for every ,
Proof
(Group equal values, then count the top tail)
Let be the distinct values of over . Let be the number of assignments with , and let be the number with .
If , then . Every assignment in a group of tied values therefore receives the same p-value, and that p-value counts the whole group together with everything above it.
The counts satisfy . Hence the event occurs exactly when , where is the largest index with . If no such index exists, the event is empty and its probability is .
Otherwise the rejection region is the union of the top groups, which contains exactly assignments. The sharp null makes a function of alone, and is uniform. Therefore
Proof X-ray
Where the two hypotheses enter
The one non-obvious move is to replace the event , which looks like a condition on a random number, by the event that lies in the top tie groups: a subset of that is fixed before is drawn. Each hypothesis is used once. The sharp null makes , hence every value and every count , the same whatever turns out to be; without it, the groups would themselves move with the realized assignment. Complete randomization then gives that fixed subset probability ; under another design the count must be replaced by the design probability of the subset.
Ties cause no trouble because the in the definition puts a whole tie group on one side of the cut, so the cut can only fall at a cumulative count , never inside a group. The slack in the final inequality, , measures how far the level lies above the last attainable cumulative count.
Super-uniform, not uniform. Equality holds at and when equals a cumulative count . At the other levels the test is strictly conservative.
In the example every value is distinct, so and . With tied outcomes the groups have more than one member, and the counting must keep them.
Worked example 7.6.5
(Tied outcomes , and the all-equal edge case)
The outcomes are on units , with . List all six assignments, keeping repeated values:
| Treated set | |
|---|---|
For the observed set , the statistic is . One assignment has , so . Two assignments have , so . For a mixed pair, the statistic is . Five assignments have , so .
Multiplicity matters. Collapsing the list to the distinct values would wrongly treat each value as having probability . The group at contains four assignments, which is exactly the in the proof: here and , so jumps from to with nothing in between.
At the extreme, if all outcomes are equal, every assignment gives . Then and , so always, and for every less than . "Exact" means the level guarantee holds in finite samples. It does not mean the p-value is uniformly distributed.
Choose the tail in advance. The theorem directly covers or when the choice is fixed beforehand; a separately justified selection rule may also be recomputed for each assignment.
Worked example 7.6.6
(Choosing the tail after seeing the data)
Suppose one computes both the upper p-value and its lower-tailed counterpart , then reports the smaller. In the design, the event occurs for both and , so its probability is , twice the nominal . Selecting the tail after inspection is a form of postselection.
What a p-value says
The quantity is a tail probability computed under a specified null and a specified design. If every unit's outcome were unaffected by treatment, a uniformly random assignment would produce a difference in means at least as large as the one observed with probability .
Common mistake
(Reading the p-value as the probability that the null is true)
The value is not the probability that the sharp null is true, nor the probability that the effect is zero. It is a probability over assignments, computed by assuming the null. The null is a fixed statement about fixed numbers, and no prior distribution has been placed on it.
The inference also concerns these units. Randomization of assignment is enough to justify the test without any random sampling of units from a population. But for the same reason, assignment alone does not license conclusions about units that were never in the study.
Sharp and weak nulls
The weak null says the average effect is zero: .
The sharp null implies the weak null, but the converse fails because individual effects can cancel. The randomization test above assumes the sharp null when it fills in the missing outcomes, so its guarantee speaks only to the sharp null. The last exercise below constructs the gap explicitly.
Permutation tests from exchangeability
A related but logically separate test needs no randomized assignment.
Suppose are independent, the first drawn from a distribution and the rest from . Under the vector is i.i.d. and therefore exchangeable.
Definition 7.6.7
(Exchangeability)
A random vector is exchangeable if, for every permutation of , the vector has the same distribution as .
Condition on the multiset of pooled values. Every way of splitting the positions into a group of size and a group of size is then equally likely. The same counting proof applies, conditionally on the pooled sample, and hence also unconditionally.
This null concerns distributions, so its conclusions concern distributions too. Its justification is the sampling model rather than a design.
Equal means are not enough, because exchangeability is a statement about whole distributions.
Counterexample mode
Equal means without exchangeability
Let the single group-1 observation be with certainty. Let the two group-2 observations be independent, each equal to with probability . Both groups have mean . Use , with , over the three ways of choosing which pooled value plays the role of the singleton.
- , probability . The pooled values are . The three choices of singleton give . The observed , so .
- , probability . By symmetry, .
- mixed, probability . The pooled values are . The three choices give . The observed , so .
Hence , which exceeds . The permutation test is invalid here because the labels carry information about spread even though the means agree.
The same caution applies in evaluation work. Under an i.i.d. null of independence between features and labels, label permutations can test an association statistic. A classifier fitted independently of the test labels may be held fixed; if training, tuning or selection uses the shuffled labels, the complete label-dependent procedure must be repeated for every shuffle. This is a test of the specified independence null, not a weaker claim, and unrestricted shuffling is not automatically valid for dependent items, such as several items from one source.
The design defines the reference set
For the design-based argument above, unrestricted uniform permutation of all labels reflects complete randomization, in which every size- subset is equally likely. Other assignment designs require their actual probabilities. Exchangeable-sampling permutation tests have the separate justification described above.
- Blocking. If randomization was done separately within blocks, permute only within blocks. The reference set is the product of the within-block subsets.
- Pairs. If one unit in each pair was treated, assignments are within-pair swaps. Independent fair assignment in every pair gives equally likely assignments for pairs (see the paired-design exercise); other designs require their actual probabilities.
- Unequal assignment probabilities. Weight each assignment by its design probability: . The grouping proof goes through with cumulative probabilities in place of counts.
- Clusters or dependence. If whole clusters received treatment together, permute cluster labels, not unit labels. If units influence one another, the potential-outcome model itself needs revision.
- Postselection. Unreproduced selection of a statistic, tail, subgroup or units using treatment labels and outcomes can invalidate the fixed-statistic argument. A predeclared selection rule may instead be repeated for every assignment; selection based only on the fixed pooled outcomes under the sharp null may also preserve the argument.
Bootstrap versus permutation
The two procedures answer different questions.
The ordinary nonparametric bootstrap resamples with replacement to approximate the sampling variability of an estimator around an unknown truth. Its asymptotic validity requires assumptions and can fail for nonregular problems.
The permutation test relabels without replacement under a null that makes the relabelings equally likely. It gives an exact level, but by itself it yields neither a standard error nor a population interval.
Common mistake
(Using one method's reference distribution for the other's question)
An ordinary bootstrap reference distribution is not automatically a null distribution; a null-imposing construction may require recentering or another model. A permutation distribution under the null is not automatically the sampling distribution under an alternative. Neither method intrinsically substitutes for the other.
Computing the test
- Fix the design, statistic, and tail first. Record them before computing anything.
- Exploit structure. Since is fixed, is increasing in the treated sum . It is therefore enough to enumerate treated sums.
- Compare exactly. Ties decide p-values, and floating-point means can split true ties. Compare integer or rational sums where possible. A nonnegative tolerance that provably only enlarges the counted tail, such as counting with exact arithmetic, gives a conservative count; arbitrary rounding can split or reorder ties and needs separate justification.
- Know the limits of exhaustive enumeration. assignments are easily enumerated. are not.
- Use Monte Carlo as an approximation. Draw assignments independently from the actual design distribution and independently of the observed assignment . The plain proportion only approximates the exact p-value. The version
is itself super-uniform under the null, because are exchangeable. It is still not the exact enumeration p-value, and it varies between runs. Report and the random seed.
Exercises
Exercise 7.6.8
(The outcomes are with , and the observed treated unit has outcome . Find and .)
Foundation
Solution(2)
- 1
List the three assignments
There are assignments, and the total is . A treated unit with outcome gives .
Treated unit - 2
Count the tails
The observed statistic is . Only one assignment has , so . Two assignments have , so .
Exercise 7.6.9
(Four units form two pairs, and within each pair exactly one unit was treated, chosen by an independent fair randomization in each pair. The observed treated-minus-control differences are and . With the sum of signed within-pair differences, find .)
Core
Solution(2)
- 1
Identify the assignments the design allows
Key step
The design allows only assignments, one for each choice of which unit is treated in each pair. Under the sharp null, swapping the treatment within a pair flips the sign of that pair's difference:
Signs Using all subsets would be wrong. Two of them place both members of a pair in the same group, and the design gives those assignments probability . Including them changes the reference distribution, so the proof's uniformity step no longer describes how was actually drawn.
Because: Only within-pair swaps have positive design probability.
- 2
Count the upper tail
The observed value is , and only reaches it, so .
Exercise 7.6.10
(Construct potential outcomes for which the weak null holds but the sharp null fails, and explain what this means for the randomization test.)
Synthesis
Solution(3)
- 1
Choose two units with opposite effects
Take two units with :
- Unit 1: and , an effect of .
- Unit 2: and , an effect of .
The average effect is , so the weak null holds. The sharp null fails.
- 2
Compare the imputed and the true outcomes
Key step
Suppose unit 1 is treated. The observed outcomes are . The sharp null would impute those same outcomes for the other assignment. In fact, treating unit 2 would produce and , so the true outcomes would be .
- 3
Interpret the test
The premise of the theorem, that the outcome vector is constant across assignments, is false here, so its guarantee does not apply. A small p-value from the randomization test is evidence against "no unit is affected." It is not, without further argument, evidence against "the effects average to zero." Testing the weak null requires different statistics and a different justification.
Summary
A randomization test counts assignments. Under the sharp null and complete randomization, the observed assignment is a uniform draw from a known finite set; other designs require their actual assignment probabilities. Grouping tied values then gives exactly, usually with conservative slack.
The permutation test for two samples rests instead on exchangeability under a common distribution.
A fixed statistic and a reference set matching how the data actually arose give the guarantees shown here. A selection procedure requires its own valid justification, for example by repeating a predeclared rule across assignments.