The Permutation Test

The permutation test is a nonparametric method for testing whether two distributions are the same. This test is exact, meaning that it is not based on large sample theory or approximations.

Suppose that $X_1,\dots ,X_m\sim F_X$ and $Y_1,\dots ,Y_n\sim F_Y$ are two independent samples and $H_0$ is the hypothesis that two samples are identically distributed. This is the type of hypothesis we would consider when testing whether a treatment differs from a placebo. More precisely we are testing

$$H_0:F_X=F_Y\mathrm{versus}{H}_1:F_X\ne F_Y.$$

Let $T=(x_1,\dots ,x_m,y_1,\dots ,y_n)$ be some test statistic. For example,

$$T(X_1,\dots ,X_m,Y_1,\dots ,Y_n)=\left|{\bar{X}}_m-Y_n\right|.$$

Let $N=m+n$ and consider forming all $N!$ permutations of the data $X_1,\dots ,X_m,Y_1,\dots ,Y_n$. For each permutation, compute the test statistic $T$. Denote these values by $T_1,\dots ,T_{N!}$. Under the null hypothesis, each of these values is equally likely. The distribution ${\mathbb{P}}_0$ that puts mass $1/N!$ on each $T_j$ is called the permutation distribution of $T$. Let $t_{\mathrm{obs}}$ be the observed value of the test statistic. Assuming we reject when $T$ is large, the p-value is

$$\text{p-value}={\mathbb{P}}_0(T>t_{\mathrm{obs}})=\frac{1}{N!}\sum _{j=1}^{N!}\mathbb{I}\{T_j>t_{\mathrm{obs}}\}.$$

Usually its not practical to evaluate all $N!$ permutations. We can approximate the p-value by sampling randomly from the set of permutations. The fraction of times $T_j>t_{\mathrm{obs}}$ among these samples approximate the p-value.

Algorithm for Permutation Test

1. Compute the observed value of the test statistic

$$t_{\mathrm{obs}}=T(X_1,\dots ,X_m,Y_1,\dots ,Y_n).$$

2. Randomly permute the data. Compute the statistic again using the permutated data.
3. Repeat the previous step $B$ times and let $T_1,\dots ,T_B$ denote the resulting values.
4. THe approximate p-value is

$$\frac{1}{B}\sum _{j=1}^B\mathbb{I}\left\{T_j>t_{\mathrm{obs}}\right\}.$$

Tip

In large samples, the permutation test usually gives similar results to a test that is based on large sample theory. The permutation test is thus most useful for small samples.