Permutation tests

Test whether a group label matters by recomputing the statistic for every (or many random) reshuffling of the labels; the p-value is the share of shuffles at least as extreme as the observed one.

p_{\text{exact}} = \frac{\#\{\text{arrangements with } T^* \text{ at least as extreme as } T_{\text{obs}}\}}{\binom{n_1+n_2}{n_1}}, \qquad p_{\text{MC}} = \frac{\text{count} + 1}{B + 1}

Exact and Monte Carlo permutation p-values

$T_{\text{obs}}$: statistic on the real grouping (e.g. difference in means $ar x - ar y$ )
$T^*$: the same statistic after reassigning the labels
$B$: number of random permutations when full enumeration is too large
$\text{count}$: random permutations with $T^*$ at least as extreme as $T_{ ext{obs}}$

When to use

Comparing two groups (or paired data, by randomly flipping the signs of the differences) with any statistic, without relying on normality.
Especially natural for randomised experiments, where shuffling labels mimics re-running the randomisation.

Assumptions

Under H0 the labels are exchangeable: every assignment of the observed values to groups is equally likely (true under randomisation and H0 of no effect at all).
Observations are independent. Exchangeability can fail when the groups differ in spread, so a significant result may reflect a difference in distribution, not only in means.

How to interpret

The engine enumerates all splits when there are at most 100 000 and otherwise draws $B$ random permutations; the Monte Carlo p-value uses (count + 1)/(B + 1), so it is never 0. Two-sided p = min(1, 2 × smaller one-sided p).
As with any test, the p-value is the probability of a result at least this extreme if H0 were true, not the probability that H0 is true.

Common mistakes

Shuffling within an analysis that ignores pairing or clustering.
Reporting a Monte Carlo p-value of 0 (impossible with the +1 rule) or using too few permutations for small p-values.
Assuming "nonparametric" means "assumption-free".

Example

Group x: 23, 27, 31, 25, 29 (mean 27); group y: 18, 22, 20, 24, 21 (mean 21). Observed difference = 6. All 252 splits were enumerated: two-sided p = 0.0159 (4 splits out of 252 are at least as extreme, counting both directions).