Permutation Test
Non-parametric hypothesis test, which tests for the equality of two population distributions.
Table of contents
Hypothesis
The null hypothesis is:
$$ H_0: F_X = F_Y $$
where $F_X$ and $F_Y$ are the cumulative distribution functions of the two populations.
The alternative hypothesis is:
$$ H_1: F_X \neq F_Y $$
Test Statistic
Let $X_1, \dots, X_m$ be the sample from population $X$, and $Y_1, \dots, Y_n$ be the sample from population $Y$.
The test statistic is the difference in means:
$$ t_{obs} = \overline{X}_m - \overline{Y}_n $$
Idea
If the null hypothesis is true, even when the samples are shuffled and resplit into two groups, the statistic should not change much.
Procedure
Let $Z = (X_1, \dots, X_m, Y_1, \dots, Y_n)$ be the combined sample. Let $N = m + n$.
There are $N!$ possible permutations of the combined sample.
Then, for each permutation $Z^\ast$ of $Z$, define $\overline{X}_m^\ast$ and $\overline{Y}_n^\star$ as the means of the first $m$ and last $n$ elements of $Z^\ast$.
If the null hypothesis is true:
\[T = \overline{X}_m^\ast - \overline{Y}_n^\ast\]The probability that $T$ is more extreme than $t_{obs}$ is should be low.
So our p-value is:
$$ p = \Pr(T > t_{obs}) = \frac{1}{N!} \sum_{i=1}^{N!} I(T_i > t_{obs}) $$
i.e. count the number of times $T_i > t_{obs}$ to find the proportion of times this happens.
What?
Basically, we’re forming a distribution of $T$ by permuting the combined sample.
In the distribution of $T$, we’re looking at the probability of observing a value as extreme as $t_{obs}$.
If the null hypothesis is true, then the probability of observing more extreme values than $t_{obs}$ should be low.
Realistically
As $N$ gets large, performing $N!$ permutations becomes unreasonable.
So we pick a large number $B$, and randomly sample $B$ permutations.
Then, our p-value is:
$$ p = \frac{1}{B} \sum_{i=1}^{B} I(T_i > t_{obs}) $$