Permutation Tests

Intuition

If the group labels "A" and "B" don't matter (the null hypothesis), then shuffling the labels should produce differences in means just as large as the one we observed, fairly often. If almost no shuffle produces a difference as extreme as the real one, the labels probably do matter.

Precise explanation

  1. Observed statistic dobs=xˉ−yˉd_\text{obs} = \bar x - \bar y.
  2. Pool all values. For b=1..Bb = 1..B: shuffle the pool, call the first nxn_x values "x" and the rest "y", compute dbd_b.
  3. Two-sided p-value with the standard +1 correction (counts the observed arrangement, never 0):
p=1+#{b:∣db∣≥∣dobs∣}B+1.p = \frac{1 + \#\{b: |d_b| \ge |d_\text{obs}|\}}{B + 1}.

Fisher–Yates shuffle (uniform over permutations) using only rng.random():

for i from n-1 down to 1:
    j = int(rng.random() * (i + 1))   # 0 <= j <= i
    swap items[i], items[j]

Floating-point noise can make ∣db∣|d_b| differ from ∣dobs∣|d_\text{obs}| in the last bits even for identical arrangements; compare with a small tolerance (>= abs_obs - 1e-12).

Worked example

x = [5, 6, 7], y = [1, 2, 3]: dobs=4d_\text{obs} = 4. Only the 2 of the 20 equally likely splits (x and y swapped) are as extreme, so the exact p-value is 2/20 = 0.1; a Monte Carlo estimate with many shuffles is close to 0.1.

Common mistakes

  • Shuffling x and y separately (labels never move).
  • Biased shuffles such as j = int(rng.random() * n) for every i.
  • Reporting p = 0.

Why this matters

Permutation tests make almost no distributional assumptions; they also underlie permutation feature importance (XA-08), where shuffling a feature breaks its link with the target.

References