Permutation test

Remarks

Under $H_0$, $P(p(Z) \le \alpha) \le \alpha$ for every $\alpha \in [0, 1]$, so the test has level $\alpha$, whatever the law of $Z$. In the two-sample problem, $Z$ is the pooled sample $X_1, \dots, X_m, Y_1, \dots, Y_n$ with $N = m + n$, and $H_0$ says that all $N$ values are i.i.d. Since $T$ usually depends only on which values fall in the first group, one may count the $\binom{N}{m}$ splits instead of the $N!$ permutations. When $N!$ is too large, one uses a random sample of permutations, which gives a Monte Carlo approximation of $p(Z)$.

Example: $X = (3, 5)$, $Y = (1, 4)$ and $T = \bar X - \bar Y$, so $T = 4 - 2.5 = 1.5$. The $6$ splits of $\set{1, 3, 4, 5}$ give the $X$-pairs $\set{1,3}, \set{1,4}, \set{1,5}, \set{3,4}, \set{3,5}, \set{4,5}$ and the values $-2.5, -1.5, -0.5, 0.5, 1.5, 2.5$. Two of them are at least $1.5$, so $p = 2/6 = 1/3$.

Non-example: if under $H_0$ the two groups have the same mean but different variances, the pooled vector is not exchangeable. The clause on exchangeability fails, and the test of equal means need not have level $\alpha$.

The Mann–Whitney U test is a permutation test whose statistic depends only on the ranks.