Is a permutation test always exact?

Only when the reference construction and assumptions justify exactness; Monte Carlo sampling also introduces approximation.

Can paired observations be shuffled freely?

Generally no; the pairing must be respected.

Does a larger number of permutations fix the wrong null scheme?

No. It only estimates the wrong reference distribution more precisely.

AI Glossary / Statistics and probability / Intermediate

Permutation test

Definition

A permutation test assesses a statistic by comparing its observed value with values produced by rearrangements allowed under a null hypothesis or an experimental randomization scheme. The rearrangements create a reference distribution. The p-value is determined by how often the resulting statistic is at least as extreme as the observed statistic, using a stated definition of extremeness.

What it means

The test asks whether the observed arrangement looks unusual relative to arrangements that would be permissible if the null model held. It keeps selected features of the data fixed while varying labels, pairings, or other components specified by the design.
Permutation testing avoids some parametric reference-distribution assumptions, but it is not assumption-free. The validity of the rearrangement is central: a shuffle that destroys essential structure can produce an invalid reference distribution.

How it works

Specify the hypothesis and choose a statistic that captures the difference or association of interest. Decide in advance whether the alternative is one-sided or two-sided and how ties count toward the tail probability.
Identify the justified permutation scheme. For independent samples with exchangeable observations under the null, group labels may be reassigned while group sizes remain fixed. In a randomized experiment, rearrangements should reproduce the actual assignment mechanism under an appropriate null, such as a sharp no-effect hypothesis.
Paired data require a different scheme. Swapping labels within pairs may be justified by paired randomization or an appropriate exchangeability condition. Arbitrarily pooling all measurements ignores the pairing. Time series, clustered data, and blocked studies may require restricted permutations or other methods.
Calculate the observed statistic. Enumerate every admissible arrangement when feasible, or sample a sufficiently large collection using a documented random-number procedure. Recalculate the statistic for each arrangement using the same processing steps.
For an exhaustive equally weighted reference set, divide the number of qualifying extreme arrangements by the total number, including the observed arrangement. If the randomization design assigns unequal probabilities, those probabilities must be reflected instead of assuming a uniform distribution.
For a Monte Carlo approximation, a common valid convention adds one to both the number of extreme sampled statistics and the number of sampled rearrangements. This avoids reporting an unjustified zero p-value. Document the implementation, random seed, and number of resamples.
Exchangeability is stronger than equality of means. A naive label-permutation test of a mean difference need not be exact when distributions differ in variance or shape under a mean-equality null. Studentized procedures and asymptotic justifications require their own conditions.
Two-sided definitions also differ. Some implementations double a smaller one-sided tail; others compare absolute deviations. State the convention rather than assuming all software outputs must match.

Three practical examples

AI evaluation: researchers test a paired performance contrast using rearrangements consistent with how tasks or systems were assigned.
Product experimentation: an analyst reproduces a randomized allocation to assess an observed outcome difference.
Association analysis: a team permutes allowable pairings to evaluate a predeclared relationship between measurements.

Think of it this way

Think of replaying a fair allocation process while keeping the observed outcome values on the table. The question is how often a permitted replay would place the values into groups that look as different as the actual allocation.

Worked example

Consider two groups of three independent observations: A = 6, 7, 8 and B = 1, 2, 3. The observed difference in means, A minus B, is 7 minus 2 = 5.
Assume all six values are exchangeable under the null. There are 6 choose 3 = 20 distinct choices for which three values receive label A; the remaining three receive label B. Internal ordering within either group does not change the statistic.
Only the assignment placing 6, 7, and 8 in A produces a difference at least +5. The exhaustive one-sided p-value is 1/20 = 0.05.
For a two-sided test using absolute differences, the reversed assignment also qualifies, producing -5. No other assignment reaches an absolute difference of 5, so the two-sided p-value is 2/20 = 0.10.
These small-sample values are discrete. They arise from a full enumeration, not a simulation, and they depend on the stated exchangeability assumption and tail rule.

Illustrative case study

Fictional case: Alder Evaluation compares two support systems on matched tasks. An initial analyst proposes shuffling every result across all tasks. The team instead preserves the task pairing and checks whether within-task label swaps fit the study design. Its report documents that choice because the permutation scheme determines what null question the p-value answers.

Common misconceptions and mistakes

Do not equate random shuffling with a valid statistical test. The design determines which rearrangements are allowed.
Do not treat a permutation p-value as the probability that the null is true. Avoid reporting zero simply because no sampled statistic was more extreme.
A bootstrap usually resamples observations with replacement for a different purpose; it is not the same operation as permuting labels.
If feature selection or tuning used the outcomes, those steps may need to be repeated within each permutation to reflect the full tested procedure.

Business use

Permutation methods can support interpretable comparisons when the assignment or exchangeability structure is clear. Businesses should preserve the analysis specification, sampling unit, allowed rearrangements, statistic, tail convention, and resampling settings so that a result can be reproduced and its scope assessed.

Check your understanding

Why are there 20 assignments in the example?

Answer: Choosing three of six values determines both groups.

Why is the two-sided result twice the one-sided result here?

Answer: The absolute-value rule includes the equally extreme reversed assignment in this symmetric reference set.

Related terms

Null distribution
Paired data
Bootstrap
P-value
exchangeability
randomization test
Monte Carlo method
restricted permutation

Learn next

Learn next how experimental randomization supports exact inference, why restricted permutations preserve design structure, and how studentization changes the behavior of tests under unequal variability.

Sources

Sources: SciPy, permutation_test documentation, https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.permutation_test.html . This primary developer reference explains independent, paired-sample, and pairing permutations, exhaustive and randomized calculations, and tail conventions. The six-value example was independently enumerated; the case is fictional.

Previous: Permutation language modeling Next: Permutation variable importances