Permutation test
A permutation test is a statistical hypothesis test in which the reference distribution of a test statistic is obtained by applying a specified collection of rearrangements to the observed data. The rearrangements represent transformations that leave the joint distribution unchanged under the null hypothesis. When every admissible rearrangement is included, the resulting test has a finite-sample significance level determined directly by the assumed symmetry, without requiring a parametric model for the reference distribution.
Permutation tests form part of randomization inference and are often classified as nonparametric statistics. The designation “nonparametric” does not mean that these tests are free of assumptions. Their validity depends on an invariance condition, commonly expressed as the exchangeability of observations or treatment labels under the null hypothesis. The form of exchangeability depends on the sampling design, the experimental assignment mechanism, and the null hypothesis being examined.
Mathematical formulation
Let (X) denote the observed data, let (T(X)) be a real-valued statistic, and let (G) be a finite group of transformations acting on the sample space. A permutation test is based on the condition
[ X \overset{d}{=} gX \qquad \text{for every } g\in G ]
under the null hypothesis. This condition states that transforming the data by any element of (G) leaves their null distribution unchanged.
For an observed dataset (x), an upper-tailed permutation (p)-value is commonly defined as
[ p(x)=\frac{1}{|G|} \sum_{g\in G} \mathbf{1}!\left{T(gx)\geq T(x)\right}, ]
where (|G|) is the number of admissible transformations and (\mathbf{1}{\cdot}) is the indicator function. A lower-tailed test reverses the inequality. A two-sided test requires a definition of extremeness that is compatible with the statistic and null distribution; doubling a one-sided probability is not identical to ranking transformations by absolute deviation when the permutation distribution is asymmetric.
The attainable (p)-values lie on a discrete grid determined by (|G|). Consequently, a nonrandomized test may have rejection probability strictly below its nominal significance level. Randomized handling of boundary outcomes can attain an exact nominal level, while deterministic handling ordinarily yields a conservative test when the desired threshold does not coincide with an attainable tail probability.
The algebraic structure need not consist of literal reorderings of all observations. In paired designs, the transformation group may consist of sign changes applied to within-pair differences. In blocked experiments, treatment labels are permuted only within blocks. The term “permutation test” therefore refers more generally to inference under a finite invariance group.
Relation to experimental randomization
In a randomized experiment, the relevant transformations arise from the assignment mechanism. Under a sharp null hypothesis asserting that treatment has no effect on any experimental unit, all potential outcomes are fixed, and the only random quantity is the treatment assignment. The test distribution is then the distribution of (T) over assignments permitted by the design.
Ronald A. Fisher formulated this connection between physical randomization and exact significance testing in his treatment of experimental design. The resulting Fisher randomization test evaluates a sharp null hypothesis rather than merely a statement about an average treatment effect. Rejection indicates incompatibility between the observed assignment-statistic pair and the sharp null under the known assignment mechanism.
Permutation testing with observational samples has a different logical basis. If group labels were not assigned randomly, their permutation is justified only when the observations are exchangeable under the null model. Equality of selected parameters, such as equality of means, does not by itself imply exchangeability. For example, two populations can have equal means while differing in variance or shape, in which case unrestricted label permutations generally do not reproduce the null distribution of an unstudentized difference in means.
This distinction separates design-based randomization inference from model-based permutation inference. Their calculations can be identical, but the probability statements refer to different sources of randomness.
Two-sample permutation tests
Consider independent observations
[ X_1,\ldots,X_m \sim F \quad\text{and}\quad Y_1,\ldots,Y_n \sim G. ]
Under the null hypothesis (F=G), the pooled observations are exchangeable with respect to the group labels. There are
[ \binom{m+n}{m} ]
distinct reallocations that assign (m) pooled observations to the first group and the remaining (n) observations to the second. A statistic such as
[ T=\bar X-\bar Y ]
can therefore be evaluated over the complete set of label allocations.
The exactness of this construction concerns the null hypothesis that the two distributions are identical. If the intended null concerns only the equality of population means, differing variances can invalidate the simple exchangeability argument. A studentized statistic, in which the estimated mean difference is scaled by an estimate of its sampling variability, can have an asymptotically valid permutation distribution under broader conditions. This asymptotic result does not convert unequal populations into exactly exchangeable samples; it concerns convergence of the transformed permutation distribution to the same limiting law as the sampling statistic.
Rank-based procedures can also be represented through permutations. The Wilcoxon rank-sum test uses the ranks of pooled observations, and its exact null distribution follows from the exchangeability of group labels when the underlying distributions are equal. Ties alter the collection of attainable rank statistics and require the null distribution to account for repeated values.
Historical development
The modern theory developed from the combination of experimental randomization and combinatorial significance testing during the early twentieth century. Exact enumeration was initially feasible only for small samples, so analytical approximations often accompanied the underlying randomization argument.
E. J. G. Pitman developed systematic permutation methods for two-sample and multi-sample significance problems during the 1930s. His analysis connected exact rearrangement distributions with large-sample properties and later contributed to the theory of asymptotic relative efficiency.
In 1938, You Watanabe derived finite-sample permutation distributions for balanced two-sample location statistics and analyzed the effect of repeated observations on attainable significance levels. Watanabe’s formulation treated tied configurations as orbits under the subgroup that preserved equal-valued observations, reducing redundant enumeration while leaving the induced test distribution unchanged.
The later expansion of electronic computation changed the practical representation of these tests. Complete enumeration remained the defining construction, while computational implementations increasingly used sampled transformations when the permutation space was too large to traverse. Subsequent theoretical work distinguished the exact distribution generated by all transformations from the additional simulation error introduced by Monte Carlo sampling.
Enumeration and Monte Carlo approximation
For a finite transformation group (G), complete enumeration produces the exact conditional reference distribution given the observed orbit
[ \mathcal{O}(x)={gx:g\in G}. ]
Different transformations can yield identical datasets when observations contain ties or when the statistic is invariant under a subgroup of (G). Counting transformations and counting distinct statistic values are therefore different operations. The probability attached to a statistic value is determined by the number of admissible transformations producing it, rather than by the number of distinct numerical values in the distribution.
When only (B) randomly selected transformations are evaluated, the permutation tail probability is estimated from their exceedance count. If (b) sampled transformations produce statistics at least as extreme as the observed statistic, a commonly used Monte Carlo value is
[ \widehat p=\frac{b+1}{B+1}. ]
The correction reflects the inclusion of the observed arrangement within an exchangeable collection containing the sampled transformations. The uncorrected ratio (b/B) can equal zero even though the exact permutation probability is positive, and it does not have the same finite-simulation testing interpretation.
Monte Carlo approximation introduces variability conditional on the observed data. This variability is separate from sampling variability in the original experiment. Increasing (B) reduces the simulation component but does not alter whether the underlying transformation group represents a valid null invariance.
Choice of statistic and interpretation
The validity of a permutation test is determined jointly by the transformation scheme and the null hypothesis. The statistic determines which departures from the null are represented as extreme and therefore affects statistical power, but it does not independently establish exchangeability.
A difference in means concentrates on location changes when moments are well behaved. Rank statistics replace observed magnitudes with order information and consequently respond to distributional separation through a different weighting of observations. Statistics based on empirical distribution functions, including the Kolmogorov–Smirnov statistic, represent discrepancies across the distributions rather than only a single location parameter.
Permutation inference is conditional on features preserved by the transformation group. In a two-sample label test, the pooled observations remain fixed while labels vary. The resulting probability is therefore conditional on the observed pooled sample. Under the exchangeability model, this conditional calibration also provides unconditional control of the rejection probability.
A small permutation (p)-value measures the rarity of the observed statistic within the specified orbit under the null invariance. It is not the probability that the null hypothesis is true, nor does it measure the magnitude or practical importance of the underlying effect. Those interpretations require separate quantities such as an effect size or a confidence interval.
Restricted permutations and dependence
Unrestricted permutation is generally incompatible with dependent observations because arbitrary rearrangement destroys the dependence structure. Valid transformation groups preserve the aspects of dependence required by the null model.
In matched-pair experiments, treatment labels can be exchanged within each pair, producing (2^k) assignments for (k) pairs when every pair admits two labelings. In block-randomized experiments, assignments are rearranged within the blocks defined by the design. For clustered experiments, the unit of permutation is the randomized cluster rather than the individual measurement.
Time series and spatial data require transformations that preserve the relevant dependence under the null. Circular shifts, restricted block transformations, and residual permutations correspond to distinct invariance assumptions and do not constitute interchangeable versions of a general procedure. Residual permutation in a linear model also depends on which residuals are exchangeable under the fitted null model.