Two Reasons to Permute
A permutation test compares an observed statistic with values obtained by rearranging labels. The rearrangement itself does not make a test valid. Validity depends on why those rearrangements represent outcomes that could occur under the null hypothesis. In genomic studies, confusing the two main justifications can turn a useful test into an unjustified one: the same calculation may be exact under a randomized experiment but invalid for observational groups whose distributions differ.
A design-based randomization test is justified by the treatment-assignment mechanism: the study design specifies which assignments could have occurred and with what probabilities. A model-based permutation test is justified by a statistical model under which the observations or labels are exchangeable under the null. The first conditions on the study’s outcomes and uses randomness in assignment; the second uses assumptions about how the data were generated.
The earlier material on exchangeability and exact permutation tests establishes the key model-based idea: under exchangeability, relabelling does not change the joint distribution under the null. Here the emphasis is on distinguishing that assumption from random assignment and on matching each justification to the hypothesis being tested.
Design-Based Randomization Tests
Suppose \(n\) units are assigned to treatment or control, and let \(Z_i=1\) denote treatment assignment for unit \(i\) and \(Z_i=0\) control. Write \(Y_i(1)\) and \(Y_i(0)\) for the outcomes unit \(i\) would have under treatment and control, respectively. Only \(Y_i=Z_iY_i(1)+(1-Z_i)Y_i(0)\) is observed for each unit. The assignment mechanism specifies the set of allowed vectors \(Z=(Z_1,\ldots,Z_n)\) and their probabilities.
The standard exact randomization test uses Fisher’s sharp null hypothesis, \(H_0:Y_i(1)=Y_i(0)\) for every unit \(i\). Under this null, each unit’s outcome is unchanged by assignment, so all outcomes are known under every allowed assignment: they are the observed outcomes. For each assignment, calculate the chosen statistic, such as the difference in treatment and control means. The randomization distribution is the distribution of that statistic induced by the actual assignment mechanism.
The sharp null is stronger than a null hypothesis that only says the average treatment effect is zero. Under a zero-average-effect null, some units could benefit and others be harmed. Their unobserved outcomes under alternative assignments are not determined by the observed data, so the exact randomization distribution cannot generally be calculated by simply reallocating the observed outcomes. The test’s exactness is therefore tied to the null it actually tests.
Worked Example: An Exact Test in a Small Randomized Experiment
Hypothetical study. Four participants are randomly assigned, with exactly two assigned to treatment. Their observed expression changes, in arbitrary expression units, are 2, 4, 6, and 8. The participants with changes 6 and 8 received treatment. Use the difference in means, treatment minus control, and test the two-sided sharp null.
The observed statistic is \(T_{\mathrm{obs}}=(6+8)/2-(2+4)/2=7-3=4\) expression units. Under the sharp null, the four outcomes remain fixed while every assignment of two participants to treatment is considered. There are \(\binom{4}{2}=6\) equally likely assignments under the stated design.
The six treatment groups give differences of means \( -4,-2,0,0,2,4\) expression units. For a two-sided test using the absolute difference, the exact p-value is \(P(|T|\geq |T_{\mathrm{obs}}|)=2/6=0.3333\).
Thus, under the sharp null and this assignment mechanism, one third of the allowed assignments produce a difference at least as extreme in absolute value as the observed difference. This small experiment does not provide strong evidence against the sharp null at a conventional 0.05 significance level. The calculation is exact for the specified randomization and null, but its coarse p-value reflects the small number of possible assignments.
Model-Based Permutation Tests
For an observational comparison, the group labels were not assigned by the investigator. A permutation test can still be justified, but it needs a model. For example, suppose observations from both groups are independent and, under \(H_0\), are drawn from the same distribution. Then, conditional on the pooled observed values and the group sizes, each allocation of those values to the group labels is equally plausible. The labels are exchangeable under this null.
This common-distribution null is stronger than equality of population means. If the null says only that the two means are equal, but allows different variances or shapes, the observations need not be exchangeable across groups. Permuting labels as if they came from one common distribution may then produce the wrong reference distribution. In particular, it is not enough that the test statistic is a difference in means: the null model must justify the permutations used to calibrate that statistic.
Worked Example: A Model-Based Test of a Common Distribution
Hypothetical observational comparison. Three samples from group A have expression values 4, 5, and 6; three independent samples from group B have values 7, 8, and 9. Treat the values as independent draws and test the model-based null that both groups have the same distribution. Use the difference in means, A minus B, and a two-sided permutation test.
The observed statistic is \(T_{\mathrm{obs}}=(4+5+6)/3-(7+8+9)/3=5-8=-3\) expression units. Pooling gives the six values \(4,5,6,7,8,9\). Under the common-distribution null, each of the \(\binom{6}{3}=20\) allocations of three values to group A is equally likely, conditional on the pooled values.
The largest possible absolute difference is 3 expression units: assigning \(4,5,6\) to A gives \(-3\), and assigning \(7,8,9\) to A gives \(3\). Every other allocation has a smaller absolute difference. Therefore exactly two of the 20 allocations are at least as extreme as the observed statistic, and \(p=2/20=0.1000\).
Under the stated independent, common-distribution model, the observed difference is not significant at \(\alpha=0.05\). This is a model-based comparison, not a test made exact by random treatment assignment. Its conclusion concerns compatibility with the common-distribution null; it does not establish that group membership caused any expression difference.
Why Equal Means May Not Justify Permutation
A useful diagnostic is to ask whether the null makes the full group distributions interchangeable, rather than only making one parameter equal. Consider two independent groups with equal population means but unequal variances. The variance of the difference in sample means is \(\sigma_1^2/n_1+\sigma_2^2/n_2\). A label permutation instead pools the groups and reallocates the pooled observations, which can create a reference distribution with a different variance.
Worked Example: Unequal Variances and Unequal Group Sizes
Hypothetical model calculation. Suppose two independent groups have equal population means, but group 1 has variance \(\sigma_1^2=9\) and size \(n_1=2\), while group 2 has variance \(\sigma_2^2=1\) and size \(n_2=6\). This model satisfies a null of equal means, but not the common-distribution null needed for unrestricted label exchangeability.
Under this equal-means model, the actual sampling variance of the difference in sample means is \(9/2+1/6=27/6+1/6=28/6=4.667\) squared expression units. If pooled observations are permuted, their approximate pooled variance under the null is the size-weighted average \((2/8)(9)+(6/8)(1)=18/8+6/8=3\) squared expression units. The corresponding permutation variance for a difference of means is approximately \(3(1/2+1/6)=3(2/3)=2.000\) squared expression units.
The permutation reference variance, 2.000, is substantially smaller than the actual sampling variance, 4.667, in this configuration. A test calibrated from that narrower reference distribution can reject too often when the equal-means null is true. Thus, equality of means alone does not justify unrestricted permutation here. The variance calculation diagnoses the mismatch; it does not, by itself, supply a corrected p-value.
Derivation of the Exactness Argument
The two justifications can be stated as conditional probability arguments. In a randomized experiment, suppose the assignment mechanism gives each allowed assignment \(z\) probability \(\pi(z)\). Under the sharp null, the observed outcome for each unit is invariant to \(z\). Consequently, for any statistic \(T\), its null distribution is \(P(T\leq t\mid \text{observed outcomes},H_0)=\sum_{z\in\mathcal{Z}}\pi(z)I\{T(z)\leq t\}\), where \(\mathcal{Z}\) is the set of allowed assignments and \(I\{\cdot\}\) is 1 when its condition holds and 0 otherwise. The distribution is exact because it reproduces the actual assignment probabilities under the null.
For a model-based test, suppose the pooled observations are independent draws from one common distribution under \(H_0\), and the group sizes are fixed. The joint probability of a particular ordered pooled sample does not depend on which observations receive which group labels. Conditional on the pooled values, all allocations with the fixed group sizes therefore have the same probability. This is the exchangeability argument that makes the permutation distribution appropriate. If group distributions differ under the null, that conditional equality need not hold.
Decide whether the target is a sharp no-effect null, a common-distribution null, or a weaker parameter null such as equal means.
For a randomized experiment, use the assignment mechanism. For a model-based test, state the model assumption that makes labels exchangeable.
Use only assignments allowed by the design, or only permutations justified by the model. Compute the statistic for each allowed rearrangement, using its probability if assignments are not equally likely.
Comparison, Diagnostics, and Limitations
| Feature | Design-based randomization test | Model-based permutation test |
|---|---|---|
| Source of validity | Known treatment-assignment mechanism | Exchangeability under a statistical null |
| Typical exact null | Sharp no-effect null for every unit | Common distribution across groups |
| What is held fixed | Observed outcomes under the sharp null | Pooled observed values and group sizes |
| Main failure | Using assignments the design did not allow, or claiming exactness for a weaker null | Permuting despite nonexchangeable group distributions under the null |
Before reporting a permutation result, check the design or model rather than relying only on a histogram of permuted statistics. For a randomization test, confirm that the possible assignments and their probabilities match the study protocol; arbitrary shuffling is not a substitute for the actual assignment mechanism. For a model-based test, examine whether the scientific null implies the same distribution across groups, including relevant features such as spread and shape. Evidence of unequal spread, strong dependence, or a sampling structure inconsistent with independent exchangeable observations is a warning that unrestricted label permutation may not be calibrated.
The principal alternatives depend on which assumption fails. A design-based analysis can use the actual randomization distribution when assignment was randomized, while an observational analysis may require a model-based method that accounts for the features that invalidate simple exchangeability. Those approaches are not interchangeable with unrestricted label permutation. This tutorial does not prescribe a remedy for each dependence or design structure; the central limitation is that no permutation scheme can repair a null hypothesis or data-generating assumption that does not justify it.
A common mistake is to say, “The groups have equal means under \(H_0\), so their labels can be permuted.” That reasoning confuses equality of a parameter with equality of the full distributions. The correction is to state the exchangeability assumption explicitly and check that it follows from the null and sampling model. In a randomized experiment, instead, justify the reallocations from the assignment mechanism and state whether the tested null is sharp.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- A randomized experiment assigns exactly four of eight units to treatment. What makes treatment-label reallocations appropriate for an exact test of the sharp null?
- Two observational groups are independent samples from the same distribution under \(H_0\). What is held fixed in a conditional label-permutation test, and why are allocations equally plausible?
- Under a null of equal means, the groups have different variances and unequal sample sizes. Is unrestricted label permutation automatically justified? Explain.
- A two-sided randomization test has 12 equally likely allowed assignments, and 3 produce a statistic at least as extreme as observed. What is its exact p-value, and what does it mean?
Solutions. (1) The assignment mechanism selected four of the eight units uniformly from the allowed allocations. Under the sharp null, every unit’s outcome is unchanged by treatment, so the observed outcomes are available under all those allocations; the exact reference distribution follows from the design. (2) The pooled observed values and the group sizes are held fixed. Under the common-distribution model, group labels do not change the joint distribution, so each allocation with the specified group sizes is equally plausible conditional on the pooled values. (3) No. Equal means do not imply equal distributions or exchangeability; unequal variances and unequal sample sizes can make the permutation reference distribution miscalibrated. (4) The exact p-value is \(3/12=0.25\). Under the sharp null and stated assignment mechanism, 25% of allowed assignments yield a statistic at least as extreme as the observed one; it is not the probability that the null is true.