Randomization and Permutation Tests

Definition In an experiment with units $i = 1, \dots, n$, let $Y_i(1)$ and $Y_i(0)$ be the potential responses of unit $i$ under treatment and under control, assuming that each unit’s response depends only on its own assignment. Only one of the two is observed. A sharp null hypothesis specifies every unit’s treatment effect $Y_i(1) - Y_i(0)$, so that under it the missing potential response of every unit can be computed from the observed one. The most common is the sharp null of no effect,

A constant effect, $Y_i(1) - Y_i(0) = \tau_0$ for every $i$ with a number $\tau_0$ fixed in advance, is also a sharp null. The weak null hypothesis that the average effect $\bar{\tau}$ is zero is not sharp, because many different sets of individual effects have average zero.

Definition A randomization test of a sharp null hypothesis needs three ingredients fixed before the responses are examined. They are the assignment mechanism the experiment actually used, which gives each allowed assignment $w$ a known probability, a test statistic $T$, and a rule saying which values count as at least as extreme as the observed one. Under the sharp null every unit’s response under every allowed assignment is known, so the statistic $T(w)$ can be computed for each $w$. With $W$ a random assignment drawn from the mechanism and $w_{\text{obs}}$ the assignment that occurred, the upper-tail p-value is

and a two-sided rule uses $\lvert T \rvert$ in place of $T$. When all allowed assignments are equally likely, the p-value is the proportion of them whose statistic is at least as extreme as the observed one, the observed assignment included. If the sharp null is true, then $P(p \le \alpha) \le \alpha$ for every $\alpha$ between $0$ and $1$, without any model for how the responses arose, because the only randomness the test uses is the randomness the investigator created.

Definition A permutation test fixes a set of rearrangements of the data, such as all reassignments of the group labels that keep the group sizes, recomputes the test statistic for each rearrangement and compares the observed value with the recomputed ones. The permutation distribution is the distribution of the statistic over that set, with equal weight on each rearrangement, or with the design’s probabilities in a randomization test. The p-value is the proportion of rearrangements, weighted by those probabilities when they differ, whose statistic is at least as extreme as the observed value, counting ties as extreme. The test is valid, with $P(p \le \alpha) \le \alpha$ for every $\alpha$ when the null hypothesis is true, if that hypothesis makes every rearrangement in the set leave the joint distribution of the data unchanged and the set is closed under composition, so that one rearrangement followed by another is again in the set. All label shuffles, all shuffles within blocks and all sign changes within pairs are such sets. The next card calls this invariance of the distribution exchangeability. A randomization test is the permutation test whose rearrangements are exactly the assignments the experiment could have produced.

Definition Random variables $X_1, \dots, X_N$ are exchangeable if for every permutation $\pi$ of the indices $1, \dots, N$ the rearranged vector $(X_{\pi(1)}, \dots, X_{\pi(N)})$ has the same joint distribution as $(X_1, \dots, X_N)$. Independent observations from one distribution are exchangeable. Suppose the $n_1$ observations of one group and the $n_2$ observations of the other are all independent. Then the null hypothesis that both groups come from the same distribution makes all $N = n_1 + n_2$ observations independent and identically distributed. Given the pooled values, each of the $\binom{N}{n_1}$ ways of splitting them into groups of the original sizes is then equally likely, and the permutation test of that hypothesis is valid. In a randomized experiment the equal probabilities come from the design instead, and the sharp null fixes the responses, so no sampling model is needed. A null hypothesis saying only that two means are equal does not make the labels exchangeable when the groups can differ in spread or shape.

Definition A restricted permutation scheme allows only the rearrangements that respect the structure imposed by the design or by the null hypothesis, such as swaps within blocks or within pairs, or reassignments of whole clusters. In a randomization test the allowed rearrangements must be exactly the assignments the randomization could have produced, with their probabilities. In a randomized block design that treats $m_b$ of the $n_b$ units in block $b$, chosen uniformly and independently across blocks, there are

equally likely assignments. For $m$ matched pairs in which an independent fair coin chooses the treated member of each pair, there are $2^m$ equally likely assignments, and under the sharp null of no effect each one keeps or reverses the sign of each within-pair difference $d_i$, pair by pair, with $d_i$ taken as treatment minus control.

Definition When the allowed rearrangements are too many to list, a Monte Carlo p-value is computed from $B$ rearrangements drawn independently at random from the null reference distribution, for example from the experiment’s assignment mechanism. Let $b$ be the number of draws whose statistic is at least as extreme as the observed one. The ratio $b/B$ estimates the exact p-value. The plus-one correction reports instead

counting the observed data as one more member of the reference set. Under the null hypothesis the observed statistic and the $B$ simulated ones are exchangeable, so $P(p_{\text{MC}} \le \alpha) \le \alpha$ for every $\alpha$ and every $B$, and the test keeps its stated level despite the simulation. The corrected value is never below $1/(B + 1)$. A complete enumeration already contains the observed assignment and needs no correction. A report states $B$, $b$, the convention, the random seed and the Monte Carlo standard error, which is about $\sqrt{p(1 - p)/B}$ when the exact p-value is $p$.