A permutation test is a method of statistical hypothesis testing that compares an observed result with results obtained by rearranging the data in ways permitted under a null hypothesis. For example, a test comparing two groups may repeatedly reassign group labels while preserving group sizes, recompute a measure of their difference, and determine how often the rearranged results are at least as extreme as the observed result. Its validity depends on whether those rearrangements correctly represent the null hypothesis or the experiment’s assignment mechanism—not simply on the ability to shuffle the data.
Principle and terminology
A permutation test requires three main ingredients:
- A clearly specified null hypothesis.
- A test statistic measuring the feature of interest.
- A collection of permissible rearrangements and their probabilities.
The resulting values form a permutation distribution, which serves as the null reference distribution for the statistic. A p-value measures the probability, under that reference distribution, of obtaining a statistic at least as extreme as the one observed.
“Permutation test” and “randomization test” are often used interchangeably, but a useful distinction concerns the source of validity:
- In a permutation test based on a sampling model, rearrangements are justified by assumptions about the joint distribution of the observations.
- In a randomization test, rearrangements reproduce the treatment-assignment mechanism of an actual randomized experiment.
These approaches can produce identical calculations while supporting different interpretations. In particular, a randomized assignment mechanism need not assign equal probability to every possible allocation, so a valid randomization distribution may require unequal weights.
Permutation tests are commonly described as nonparametric because many do not require a specified family such as the normal distribution. They are not assumption-free, and their exactness applies only to the null hypotheses and rearrangements for which the required invariance holds.
Exchangeability and validity
The central sampling-model condition is exchangeability: under the null hypothesis, the joint distribution of the data must remain unchanged by the permitted rearrangements.
For two independent samples, a common null hypothesis is
where and are the populations’ distribution functions. If observations within each sample are independent draws from their respective populations and the samples are independent, this null makes the pooled observations exchangeable across group labels.
This condition is stronger than equality of means. Two populations can have equal means but different variances or shapes. An ordinary permutation test using an unstandardized difference in means is therefore not generally an exact test of equality of means alone. Unequal group sizes combined with unequal variances are a particularly important source of miscalibration.
In randomized experiments, validity can instead follow from randomization. Under a sharp null hypothesis, such as no treatment effect for any experimental unit, every unit’s outcome is fixed across the possible assignments. Reassigning treatment according to the actual design then produces the appropriate reference distribution without requiring the observed outcomes to be independent draws from a common population.
A sharp null differs from the weaker hypothesis that the average treatment effect is zero. Positive and negative individual effects may average to zero without satisfying the sharp null. This distinction is central to the interpretation of randomization-based causal inference.
Mathematical formulation
Let denote the observed data, the test statistic, and a finite collection of permitted transformations. In a common construction, is a transformation group, includes the identity, and is sampled uniformly. If larger values of provide stronger evidence against the null, the exhaustive permutation p-value is
where is an indicator function.
For a two-sided comparison, one may instead use
provided that the absolute value is an appropriate measure of departure from the null. There is no universal two-sided convention: absolute deviations and doubled one-sided tail probabilities can differ for asymmetric or discrete reference distributions.
Under the relevant invariance conditions, the test satisfies
where is the chosen significance level. Thus, the probability of a Type I error is controlled at the stated level.
“Exact” means that this control does not rely on a large-sample approximation. It does not mean that the rejection probability equals for every possible . Because permutation distributions are discrete, ordinary nonrandomized tests can be conservative. Ties are conventionally counted as at least as extreme; other tie-handling rules can alter calibration.
Two-sample procedure and example
For independent groups of sizes and , a standard procedure is:
Calculate the observed difference in sample means,
Pool the observations.
Assign observations to the first group and the remaining to the second.
Recalculate the statistic for each permitted allocation.
Compare the observed statistic with the resulting distribution.
There are
distinct allocations when the observations are treated as labeled units. This binomial coefficient is often much smaller than the number of all orderings, because rearrangements within either group do not change the allocation.
For example, suppose the observed groups are
The observed mean difference is . There are allocations. Only two have an absolute mean difference of at least : assigning the three smallest values to one group and the three largest to the other, in either direction. The two-sided permutation p-value is therefore
This example also illustrates the coarse resolution of small permutation distributions. Even a complete separation of these groups cannot produce a two-sided p-value below with this statistic and convention.
Exhaustive and Monte Carlo computation
When the number of permissible allocations is manageable, the reference distribution can be enumerated exhaustively. For larger datasets, its size can make enumeration impractical.
A Monte Carlo method approximates the test by drawing random permissible transformations. If independent transformations are drawn uniformly from the full transformation group and produce statistics at least as extreme as the observed statistic, a standard finite-simulation p-value is
The added one accounts for the observed configuration. Under the appropriate invariance and sampling scheme, this construction yields a valid randomized implementation and prevents a reported p-value of zero. Formulas can differ for other sampling schemes, such as exhaustive sampling without replacement.
The number of simulations affects both resolution and simulation error. With the formula above, the smallest attainable p-value is . For independently sampled transformations, the approximate standard error of the simulated tail fraction is
with the unknown estimated in practice. Very small tail probabilities require many simulations to estimate precisely. Reproducible reporting includes the statistic, permutation scheme, number of draws, tail convention, and random-number seed.
Designs requiring restricted rearrangements
The experimental unit and dependence structure determine what may be rearranged. Shuffling individual observations indiscriminately can generate an invalid reference distribution.
Paired observations
For matched pairs, labels may be swapped within each pair, rather than across all observations. In terms of paired differences , this corresponds to independently replacing by or .
Such sign flips are justified by randomized treatment assignment within pairs under a sharp null, or by an appropriate symmetry assumption on the distribution of the differences. A zero population mean for the differences alone is insufficient for finite-sample exactness.
Blocks and clusters
In blocked experiments, assignments must preserve the blocking restrictions specified by the experimental design. In cluster-randomized studies, treatment is reassigned at the cluster level, not independently among people within clusters. The randomization unit need not be the measurement unit.
Dependent observations
Unrestricted shuffling generally destroys serial dependence in time series and spatial dependence in geographic data. Block rearrangements, circular shifts, or other restricted transformations can be appropriate under specific assumptions, but none is automatically valid for every dependent dataset.
Regression and nuisance variables
Testing a coefficient in linear regression is more complicated when other predictors must remain controlled. Simply shuffling the response can destroy its relationships with nuisance predictors and test the wrong null hypothesis.
Residual-permutation procedures fit a model, rearrange selected residuals, and reconstruct responses or statistics. Their validity depends on the design, error assumptions, and precise procedure; many are approximate rather than universally exact. Permutations do not by themselves eliminate confounding in observational data.
Choice of statistic and hypothesis
A permutation procedure is not tied to a particular statistic. It can use differences in means, medians, ranks, correlations, regression coefficients, classification accuracy, or multivariate distances. The statistic should match the scientific question and the departures from the null that matter.
The choice affects statistical power. A statistic sensitive to location shifts may have little power against differences in spread or distributional shape.
For testing equal means when group variances differ, a studentized statistic can be used, such as
The denominator is recomputed for every allocation. Under suitable regularity conditions, studentized permutation tests can be asymptotically valid for equality of means even without exchangeability. This large-sample validity must not be confused with finite-sample exactness under identical distributions.
The statistic and analysis pipeline must also be handled consistently. If outcome-dependent feature selection, model fitting, or tuning forms part of the tested procedure, those steps generally need to be repeated within each permutation. Holding them fixed after selecting them using the original labels can make the reference distribution too favorable to the observed result.
Related methods and applications
Permutation tests and bootstrap methods both reuse observed data, but they have different usual purposes. A permutation test rearranges data under a null hypothesis. An ordinary bootstrap resamples observations with replacement to approximate an estimator’s sampling distribution, often for uncertainty estimation. The two procedures are not interchangeable.
Permutation methods are used in experiments, genetics, neuroscience, ecology, and machine learning, especially when analytic null distributions are difficult to derive. In predictive modeling, label permutations can assess whether a complete training and evaluation procedure performs better than expected under a specified no-association null. The rearrangements must still respect grouping, repeated measurements, and other relevant structure.
For multiple testing, a shared set of permutations can preserve dependence among test statistics. For example, recording the largest statistic in each rearrangement can provide a reference distribution for adjusted tests. Strong familywise error control requires additional conditions beyond merely applying permutations to every outcome.
A permutation p-value does not measure an effect size or the probability that the null hypothesis is true. Under a specified effect model, tests can sometimes be inverted to construct a confidence interval: each proposed effect is tested, and the nonrejected values form a confidence set. The resulting coverage depends on the same design and model assumptions that justify the underlying tests.
Historical development
Permutation and randomization testing developed alongside modern experimental design. Ronald Fisher established the role of randomized assignment in statistical inference, and his 1935 book The Design of Experiments presented reasoning based on the possible assignments of treatments. Early applications were constrained by the effort required to enumerate rearrangements. Electronic computation later made exhaustive calculations and large Monte Carlo samples practical, extending these methods to complex statistics and high-dimensional data.