Learn AI Create the Future — with Pranay
Main site

Resampling, Likelihood and Bayes

Permutation tests

A permutation test builds the null distribution by shuffling group labels — an exact test for any statistic, with almost no assumptions to break.

Read these first

On this page 5
  1. Why it exists
  2. How it works
  3. A real example you have seen
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

A permutation test asks: if the group labels meant nothing, how often would shuffled labels produce a difference this big?

Two friends deal a card game and one gets all four aces. "Lucky deal!" she claims. How suspicious should you be? Reshuffle and redeal a thousand times, and count how often one player gets all four aces by honest chance.

That is a permutation test. The "labels" — who got which cards, which users saw which page — get reshuffled, and you watch what pure chance produces.

Why it exists

The t-test reaches its verdict through formulas resting on assumptions — bell shapes, big-enough samples. When data is small, lumpy, or strange, those assumptions creak.

The permutation test needs almost none of that. Its logic is self-contained: if the new page changed nothing, then the labels "old" and "new" are decoration, and shuffling them should not matter. So shuffle, and see. Fisher described the idea in the 1930s; computers made it practical.

How it works

old page: [0, 0, 120, ...]      new page: [0, 150, 0, ...]
observed gap between averages: 54

pool everything  →  shuffle  →  deal into two fake groups
                →  gap = -12
                →  shuffle again  →  gap = 31
                →  ... 10,000 shuffles ...

how many shuffled gaps ≥ 54?   say 19%  →  chance explains this fine

The pile of shuffled gaps shows what "nothing going on" looks like for your data — its lumps, its zeros, its outliers, all included. No borrowed bell curve. The p-value is a straight count.

A real example you have seen

This logic decides real product experiments: revenue-per-visitor data is mostly zeros with a few large purchases — exactly the shape that embarrasses textbook tests. Genetics labs shuffle case/control labels across thousands of genes. Sports analysts shuffle match outcomes to check whether a "hot streak" outruns chance.

Remember this

  • Shuffle the labels; recompute; repeat — the shuffles are the null hypothesis.
  • Works for any statistic — means, medians, accuracy gaps — with minimal assumptions.
  • The p-value is a plain count: how often chance matched your result.

What to learn next

Developer — Code and libraries.

Setup

bash
pip install numpy scipy

Outputs verified with numpy 1.26 and scipy 1.14, CPU. Shuffle counts reproduce with these versions; other versions may shift the p-value in the third decimal.

Revenue per visitor: zeros, spikes, and a verdict

Ten visitors saw the old page, ten the new. Most bought nothing — the usual e-commerce shape that makes t-tests nervous.

permutation.py
import numpy as np

rng = np.random.default_rng(0)
a = np.array([0, 0, 120, 0, 0, 340, 0, 90, 0, 0])       # old page, rupees
b = np.array([0, 150, 0, 260, 0, 0, 410, 0, 180, 90])   # new page, rupees
observed = b.mean() - a.mean()
print(f"observed difference: {observed:.0f} rupees per visitor")

pooled = np.concatenate([a, b])
count = 0
for _ in range(10_000):
    rng.shuffle(pooled)                  # deal the labels out at random
    diff = pooled[10:].mean() - pooled[:10].mean()
    count += diff >= observed
print(f"p-value (one-sided): {count / 10_000:.4f}")
Output
observed difference: 54 rupees per visitor
p-value (one-sided): 0.1869

Verdict: shuffled labels beat 54 rupees about 19% of the time. This data does not yet separate the new page from luck — an honest, useful answer that saves a premature launch announcement.

The walkthrough

rng.shuffle(pooled) enacts the null hypothesis physically. Under "the page changed nothing", each visitor's spend was fixed; only the label was luck. Shuffling replays that luck.

pooled[10:] and pooled[:10] re-deal the twenty values into fake groups of the original sizes. Group sizes stay fixed; only membership rotates.

diff >= observed makes it one-sided. You asked "is new better?". For two-sided, count abs(diff) >= abs(observed).

scipy wraps this — same logic, vectorised, with two-sided defaults:

python
from scipy import stats
res = stats.permutation_test((a, b), lambda x, y: np.mean(y) - np.mean(x),
                             n_resamples=10_000, alternative="greater",
                             random_state=rng)
print(f"scipy p-value: {res.pvalue:.4f}")
Output
scipy p-value: 0.1852

The tiny difference from 0.1869 is shuffle-to-shuffle noise; both are estimates of the same exact p-value.

Permutation or bootstrap? Shuffling answers "is there a difference?" (a test). Resampling with replacement answers "how big, give or take?" (an interval). They are siblings with different jobs — see bootstrapping.

Common mistakes

Shuffling when the groups were not exchangeable to begin with. If new-page visitors arrived mostly on payday weekend, labels carry timing information, and shuffling destroys real structure. Randomised assignment is what licenses the shuffle.

Shuffling within dependent data. Same trap as the bootstrap: for repeat visitors, shuffle visitors, not individual visits. The unit you shuffle must be the unit that was randomised.

Too few shuffles for a strong claim. With 10,000 shuffles the smallest honest p-value is about 0.0001. Chasing "p < 0.00001" needs a million shuffles — or the statistic's tail approximation.

Forgetting the +1 convention. Purists compute (count + 1) / (shuffles + 1) so the p-value can never be exactly zero — your observed arrangement is itself one valid shuffle. scipy does this internally.

Try it yourself

Move the 410 sale from b to a and rerun. Predict the direction of the p-value's move first. Then swap the statistic to a difference in medians and see how the story changes with all those zeros.

What to learn next

Researcher — Mathematics and papers.

Exchangeability and exactness

Let data $Z = (Z_1, \dots, Z_N)$ carry labels $g \in {0, 1}^N$. The permutation null $H_0$ asserts the joint distribution of $Z$ is invariant under relabelling — exchangeability of the combined sample. Under $H_0$, every arrangement of labels is equally likely conditional on the pooled values, so for any statistic $T$:

$$ p = \frac{1}{|\Pi|} \sum_{\pi \in \Pi} \mathbf{1}\left[ T(Z_{\pi}) \geq T(Z) \right] $$

Where:

  • $\Pi$ — the group of admissible rearrangements ($\binom{N}{n}$ label assignments for two groups).
  • $Z_\pi$ — the data under rearrangement $\pi$.
  • $\mathbf{1}[\cdot]$ — the indicator function.

This test is exact at finite $n$: $\Pr(p \leq \alpha \mid H_0) \leq \alpha$ with no distributional assumptions beyond exchangeability. Randomly sampling $B$ permutations gives a Monte Carlo estimate; including the identity yields the unbiased $\hat{p} = \frac{1 + #{T_\pi \geq T}}{1 + B}$, and $\operatorname{se}(\hat p) \approx \sqrt{p(1-p)/B}$ guides the choice of $B$.

What the null actually is

$H_0$ is identical distributions, a stronger claim than equal means. A significant result can reflect a variance or shape difference if the statistic is sensitive to it. Conversely, for testing means specifically under possibly unequal variances, use a studentised statistic (the t-statistic rather than the raw mean gap): studentisation restores asymptotic validity outside strict exchangeability (Janssen, 1997; Chung and Romano, 2013, Exact and asymptotically robust permutation tests).

Power and relatives

  • The permutation t-test has the same asymptotic power as the classical t-test under normality — assumption-freeness costs essentially nothing at moderate $n$ (Lehmann and Romano, Testing Statistical Hypotheses, ch. 15).
  • Rank tests are permutation tests applied to ranks: Mann–Whitney is the permutation test of the rank-sum statistic, computed cleverly — see nonparametric-tests.
  • Fisher's exact test permutes under fixed margins of a 2×2 table.
  • Paired data permutes sign flips within pairs ($2^n$ arrangements); factorial designs permute within strata (Freedman–Lane scheme for regression residuals).

Multiple testing, exactly

The maxT procedure (Westfall and Young, 1993) permutes once and records the maximum statistic across $m$ hypotheses per shuffle; comparing each observed statistic to the max-distribution controls FWER while automatically respecting the dependence among tests — strictly more powerful than Bonferroni under correlation. This is the standard in neuroimaging and genomics pipelines.

Kernel two-sample tests

Modern high-dimensional two-sample testing keeps the permutation engine and upgrades the statistic: the Maximum Mean Discrepancy (Gretton et al., 2012, A kernel two-sample test) embeds distributions in an RKHS and permutes to calibrate — the standard tool for comparing embedding distributions or generated-vs-real samples in ML.

Cost

$O(B \cdot c(N))$ with $c$ one statistic evaluation; embarrassingly parallel. Full enumeration is feasible for tiny groups ($\binom{20}{10} = 184{,}756$). History: Fisher's lady-tasting-tea design (The Design of Experiments, 1935) and Pitman's randomisation tests (1937).

What to learn next