Why Exchangeability Is the Key Assumption
A permutation test compares the observed statistic with statistics obtained after rearranging the data. The rearrangement is not automatically legitimate just because it is easy to compute. Its justification comes from a null hypothesis under which the outcome distribution is unchanged by the allowed rearrangements. This property is called exchangeability.
In genomic studies, observations may be expression measurements from samples and a statistic may compare two groups for one gene. The test's reference distribution is then formed by permuting sample assignments, or equivalently by permuting the pooled observations relative to the fixed group labels. Exactness depends on the null distribution of the observations, not on the number of genes or the complexity of the statistic.
A group is a set of transformations that includes an identity transformation and is closed under composition and inverses. This detail matters: the possible fixed-size group assignments by themselves are not generally a transformation group. A valid formulation uses the full permutation group on the observation indices; the fixed-size assignments appear as the distinct orbit points relevant to the test statistic.
For a two-group comparison with \(n_1\) and \(n_0\) observations, one standard model-based justification is that, under \(H_0\), all \(n=n_1+n_0\) observations are independent draws from the same distribution. Their joint distribution is invariant under every permutation of the \(n\) observation indices. This is a stronger condition than equality of group means: it requires the same distribution under the null. Other designs can justify other transformation groups, but the allowed transformations must preserve the null distribution.
Exact Permutation P-Values
Let \(T(Y)\) be a test statistic, with larger values defined to be more extreme in the direction being tested. For a two-sided test, \(T\) could be the absolute value of a signed contrast. If the full group \(G\) is enumerated, the nonrandomized permutation p-value is
The identity transformation is included. The weak inequality includes ties, so observations with the same statistic as the observed one count as at least as extreme. If different transformations produce the same rearranged data or statistic, each transformation still receives its own weight in this formula.
The result is conditional on the orbit as well as valid unconditionally. Invariance means that, conditional on an orbit, each distinct orbit point has the same probability: for any two points in the orbit, a group transformation maps one to the other, and invariance gives them equal probabilities. Order the orbit points from most to least extreme by \(T\). For any point, its p-value is the fraction of orbit points at least as extreme as it is. If ties occur, every point in a tie block gets the p-value corresponding to the end of that block. Consequently, the number of orbit points with p-value at most \(\alpha\) cannot exceed \(\alpha\) times the orbit size. Dividing by the orbit size gives a conditional probability at most \(\alpha\); averaging over orbits proves the stated bound.
This argument explains both the exactness and the possible conservatism. “Exact” means the stated Type I error guarantee follows from the assumed invariance without relying on a large-sample approximation. It does not mean the p-value must equal \(\alpha\) at every threshold or that the null is necessarily true.
Worked Examples
Worked Example: Six Observations and Fixed-Size Allocations
Suppose a hypothetical genomic assay gives the following expression values for one gene. Group A has values 8, 9, and 10; group B has values 1, 2, and 3. Use the difference in sample means, A minus B, as the statistic, and use a two-sided test. Assume under \(H_0\) that all six observations are independent draws from the same distribution. This makes the pooled outcomes exchangeable under the full permutation group \(S_6\).
The observed statistic is \((8+9+10)/3-(1+2+3)/3=9-2=7\). The group acting on the six labeled observations has \(6!=720\) permutations. The distinct assignments of three observations to A number \(\binom{6}{3}=20\). Each assignment occurs \(3!3!=36\) times among the 720 permutations, because the three observations assigned to A can be ordered in \(3!\) ways and those assigned to B in \(3!\) ways. Thus the 20 assignments have equal weight, and we can count them instead of listing all 720 transformations.
The pooled values sum to 33. If the values assigned to A sum to \(s_A\), then the difference in means is
For the observed absolute difference of 7 or more, \(|(2s_A-33)/3|\geq7\), so \(|2s_A-33|\geq21\). This requires \(s_A\geq27\) or \(s_A\leq6\). Among the 20 allocations, the only subsets with those sums are \(\{8,9,10\}\), with sum 27, and \(\{1,2,3\}\), with sum 6. Therefore the exact two-sided p-value is \(2/20=0.100\). Under the stated exchangeability assumption, this test does not reject at \(\alpha=0.05\).
Worked Example: Ties in a Small Exact Test
In another hypothetical assay, four exchangeable sample values are 0, 0, 1, and 1. Two are labeled A and two B. Suppose the observed assignment puts both 1s in A and both 0s in B. The observed difference in means is \(1-0=1\), and take the absolute difference as the two-sided statistic.
There are \(\binom{4}{2}=6\) equally weighted assignments of two labeled observations to A. One assignment puts both 1s in A and gives absolute difference 1. One puts both 0s in A and also gives absolute difference 1. The other four assignments put one 0 and one 1 in each group, giving absolute difference 0. Hence
This is an exact, discrete p-value, not an approximation to a continuous distribution. The two extreme assignments are tied, and both count in the tail. Under the assumed common distribution of the four independent outcomes, the nonrandomized test is valid but can be conservative at some significance levels.
Worked Example: Equal Means Do Not Guarantee Exchangeability
Consider a hypothetical two-group null in which each observation in group A is independently \(+1\) or \(-1\), each with probability \(1/2\), while each observation in group B is independently \(+2\) or \(-2\), each with probability \(1/2\). Both groups have mean zero. Nevertheless, the pooled observations are not exchangeable across group labels.
For example, with two observations per group, let \(E\) be the event that the first two labeled observations (from A) have absolute value 1 and the last two (from B) have absolute value 2. Under this model, \(P(E)=1\). If a transformation swaps one A and one B position, the event that the transformed vector has absolute values 1 in the first two positions and 2 in the last two has probability 0 under the original group-specific distributions. The joint distribution is therefore not invariant under that swap, even though the group means are equal.
Permuting all four observations as if they had come from one common distribution would not yield an exact test for this equal-means null. A statistic or a large sample does not repair the failed invariance assumption. The null hypothesis and the assumed outcome distributions must justify the transformations used.
Exactness, Approximation, and Practical Checks
An exhaustive permutation test is exact when the specified null makes the data distribution invariant under the entire transformation group used in the calculation. There are two common ways a procedure departs from that guarantee. First, it may use a reference distribution that is only approximately justified, such as a limiting normal or \(t\) distribution. Second, it may estimate the permutation tail from only a subset of transformations. In the latter case, the result has Monte Carlo uncertainty; it is not the exhaustive orbit p-value calculated above. The number of permutations alone does not determine validity.
For genomic data, the observations often include many correlated gene measurements from the same samples. If the null supports permutations of sample indices, applying the same permutation to all genes preserves the observed cross-gene dependence in each rearranged data set. Permuting each gene independently would change that joint dependence. This observation is important for joint analyses, although the exactness argument for one gene's marginal test still rests on that gene's null invariance. Dependence across genes does not, by itself, imply exchangeability across samples.
Before using a permutation reference distribution, check the scientific and sampling assumptions that imply invariance. Ask whether the observations could reasonably be treated as draws from a common distribution under the null, whether sample dependence or batch structure makes arbitrary rearrangements invalid, and whether the null concerns a full distribution or only a parameter such as a mean. A histogram or summary of the observed data can reveal striking differences, but cannot prove exchangeability: the key condition is a statement about the joint distribution under \(H_0\).
A parametric test is an alternative when a defensible model specifies the outcome distribution and its assumptions are more appropriate than exchangeability. An asymptotic test can be useful when its large-sample approximation is justified. Neither is automatically superior: a permutation test avoids a particular parametric reference distribution, but it replaces that assumption with invariance under the chosen transformations. If neither set of assumptions is credible, a small p-value from either procedure may be misleading.
A common mistake is to reason, “The groups have equal means under \(H_0\), so their labels can be permuted.” Equal means alone do not make observations exchangeable; the unequal-variance example above shows why. The correction is to state the null model and the transformation group explicitly, then verify that the joint distribution is invariant under that group. If that cannot be justified, the resulting permutation calculation should not be described as an exact test for that null.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- For six labeled observations split into groups of three, how many full permutations are there, how many distinct fixed-size allocations are there, and how many full permutations produce each allocation?
- Why does a nonrandomized exact permutation p-value use “at least as extreme” rather than “more extreme” when defining its tail?
- A two-group null states only that the population means are equal. What additional issue must be resolved before an unrestricted permutation test is exact?
- In a genomic analysis, why might applying the same sample permutation to every gene be preferable to permuting each gene separately?
Solutions. (1) There are \(6!=720\) permutations and \(\binom{6}{3}=20\) distinct allocations. Each allocation occurs \(3!3!=36\) times. (2) Including ties gives the correct tail rank and makes the nonrandomized p-value super-uniform; excluding ties can make the test anti-conservative. (3) Equal means do not imply equal outcome distributions or invariance. The analyst must justify that the joint null distribution is invariant under the specific permutations, or use a method with assumptions suited to the null. (4) A common permutation retains the observed dependence among gene measurements within each sample, whereas separate gene permutations alter that joint structure.