Permutation Tests: A p-Value Built by Shuffling the Labels

Most hypothesis tests get their p-value from a theoretical distribution — the t-distribution, the chi-square, the F. A permutation test takes a different route: it builds the reference distribution directly from your own data, by repeatedly shuffling the group labels and recomputing the statistic. The p-value then comes from simple counting, with no formula for a sampling distribution required. For small samples, where the assumptions behind a t-test are hardest to defend, that makes it one of the most transparent tests in statistics.

The Core Idea

Suppose a study compares two groups on some outcome. The null hypothesis says the group label has no effect on the outcome — that the two groups come from the same distribution. If that is true, then which observation carries which label is purely an accident of how the groups were formed, and any reshuffling of the labels would have been equally likely to occur.

That gives a direct recipe. Pool all the observations, deal them out into groups of the original sizes in every possible way, and compute the test statistic (here, the difference in group means) for each arrangement. The resulting collection of values is the permutation distribution: what the statistic looks like when labels carry no information. If the difference actually observed sits far out in the tail of that distribution, the null hypothesis becomes hard to believe.

Worked Example

Problem: Eight students are randomly split into two groups of four. Group A is taught with a new revision method; Group B uses the standard method. Their exam scores are:

Group	Scores	Mean
A (new method)	78, 85, 82, 90	83.75
B (standard)	72, 75, 80, 77	76.00

The observed difference in means is 83.75 − 76.00 = 7.75 points. Is that more than luck in the split could plausibly produce?

Step 1 — Count the possible splits. Under the null hypothesis, any four of the eight scores could equally well have landed in Group A. The number of ways to choose 4 scores from 8 is the combination C(8,4) = 70 (the counting rule covered in permutations and combinations). Because 70 is small, every split can be examined — no approximation is needed.

Step 2 — Compute the difference for every split. The pooled scores total 639. For each of the 70 splits, the mean of the four scores in "Group A" minus the mean of the other four gives one value. The four largest positive values are:

Arrangement	Group A gets	Group B gets	Difference
1	80, 82, 85, 90	72, 75, 77, 78	8.75
2 (actual data)	78, 82, 85, 90	72, 75, 77, 80	7.75
3	77, 82, 85, 90	72, 75, 78, 80	7.25
4	78, 80, 85, 90	72, 75, 77, 82	6.75

The other 66 splits all give a difference of 6.25 or less. By symmetry, the mirror-image splits give the same values with a negative sign: −8.75, −7.75, and so on.

Step 3 — Count the tail. Only two of the 70 splits produce a difference of 7.75 or more: the actual data, and the one that swaps the scores 78 and 80 between the groups. For a one-sided test asking whether the new method is better, the p-value is simply:

For a two-sided test, splits at least 7.75 in either direction count. That adds the two mirror-image splits at −7.75 and −8.75, giving 4 ÷ 70 ≈ 0.057.

Comparing With the t-Test

Running a pooled two-sample t-test on the same eight scores gives t = 2.551 with 6 degrees of freedom and a two-sided p-value of about 0.043 (one-sided, about 0.022). The permutation test's 0.057 lands on the other side of the conventional 0.05 line. Neither answer is an error. The t-test's p-value is only trustworthy if the scores are roughly normal, which cannot be checked with four scores per group, while the permutation p-value is exact for the question "how unusual is this split among all 70?" But because only 70 splits exist, the p-value can only move in steps of 1/70 — the smallest achievable two-sided value here is 2/70 ≈ 0.029. With samples this tiny, a result near 0.05 is simply borderline, and the honest conclusion is that the evidence is suggestive rather than decisive. Reporting the effect size alongside the p-value, as in effect size, is more informative than the threshold crossing itself.

The Steps, in General

• Choose a test statistic that captures the effect of interest — a difference in means, a difference in medians, a correlation, or anything else computable from the data.
• Compute that statistic on the actual data.
• Pool the observations, shuffle the labels, and recompute the statistic. Repeat for every possible shuffle, or for a large random sample of them.
• The p-value is the proportion of shuffled statistics at least as extreme as the observed one, matching the tail direction chosen in advance (see one-tailed vs. two-tailed tests).

When There Are Too Many Splits: Random Shuffles

Enumeration stops being practical quickly. Two groups of 15 give C(30,15) = 155,117,520 possible splits — too many to list casually. The standard fix is to draw a large number of random shuffles, say 10,000, and count how many produce a statistic at least as extreme as the observed one. The result is an estimate of the exact p-value, and its accuracy improves with the number of shuffles: for a true p-value near 0.03, 10,000 shuffles give a run-to-run margin of only about ±0.002.

Applied to the eight scores above, a 10,000-shuffle simulation lands close to the exact 0.029, differing only by that small random noise. When counting random shuffles, the usual convention is to compute p = (k + 1) ÷ (N + 1), where k is the number of shuffles at least as extreme and N is the number of shuffles. The extra 1 in each place counts the actual data as one of the arrangements, which guarantees the p-value is never reported as exactly zero — an impossible claim from a finite number of shuffles.

Permutation Test vs. Bootstrap

The two techniques are often confused because both resample the data by computer. They answer different questions. Bootstrapping resamples with replacement to see how much a statistic varies from sample to sample, which produces standard errors and confidence intervals. A permutation test reshuffles without replacement, moving the same observations between groups, specifically to simulate a world in which the null hypothesis is true, which produces a p-value. One estimates uncertainty; the other tests a hypothesis.

Strengths and Limits

The main strength is that no distributional shape is assumed. The test does not need normality, and it works equally well on skewed data, on a median difference, or on a statistic with no textbook sampling distribution at all. It also fits randomized experiments naturally: if the labels were assigned by random allocation, the permutation test's shuffling mirrors exactly the randomization that actually took place.

The main limit is that the null hypothesis it tests is that the groups have the same distribution overall, not merely the same mean. If two groups have equal means but very different spreads, a permutation test on the mean difference can still flag them, especially with unequal group sizes. The test also needs the observations to be exchangeable under the null, so it is a poor fit for data with dependence, such as repeated measurements on the same subjects, unless the shuffling is designed to respect that structure.

Real-World Uses

Small clinical and lab experiments: when only a handful of subjects are randomized to treatment or control, a randomization-based p-value avoids leaning on normality assumptions that cannot be checked with so little data.

Website and product experiments: for a quick A/B test on a metric with heavy skew, such as revenue per visitor, a permutation test on the difference in means or medians is a straightforward alternative to a parametric test.

Testing a correlation: shuffling one variable's values while leaving the other fixed breaks any real pairing between them, giving a null distribution for the correlation coefficient without assuming bivariate normality.

Common Mistakes

Shuffling within the wrong unit. The reshuffling must mimic how labels could have been assigned. Shuffling individual measurements that come in matched or repeated pairs treats dependent data as independent and produces p-values that are too small.

Choosing the tail direction after seeing the data. As with any test, deciding between a one-sided and two-sided count after looking at the results inflates the false-positive rate. Decide before running it.

Using too few random shuffles. A p-value estimated from 100 shuffles is very noisy. When the result is near a decision threshold, use several thousand shuffles, or more, so the estimate is stable.

Treating it as assumption-free. A permutation test drops the normality assumption but keeps others: exchangeability under the null, and a statistic that actually reflects the effect of interest.

Is a permutation test the same as a bootstrap?

No. A bootstrap resamples with replacement to estimate how variable a statistic is, producing confidence intervals. A permutation test reshuffles the existing observations between groups without replacement to build a null-hypothesis distribution, producing a p-value.

How many shuffles are enough?

For a rough answer, a few thousand is usually adequate; for a p-value near a threshold such as 0.05, ten thousand or more gives a steadier estimate. If the total number of possible splits is small enough to enumerate, as in the worked example, the exact count removes simulation noise entirely.

Does a permutation test require normally distributed data?

No. Because the reference distribution comes from the data itself, the method works on skewed or otherwise non-normal data. It does still require that the observations be exchangeable under the null hypothesis.

How does it relate to the Mann-Whitney test?

The Mann-Whitney test is essentially a permutation test applied to the ranks of the data rather than the raw values, which is why its exact p-values for small samples come from counting arrangements. It belongs to the family of tests introduced in non-parametric tests.

Can the test statistic be something other than the mean difference?

Yes, and that flexibility is a major advantage. The statistic can be a difference in medians, a ratio of variances, a correlation, or any quantity computable from the data, since the shuffling procedure builds its own reference distribution for whichever statistic is chosen.