Permutation Test

The permutation test is a non-parametric statistical test used to determine whether two samples come from the same distribution. Given two samples $X_i\stackrel{\text{iid}}{\sim }{P}_1,i=1,\dots ,n$ and $Y_j\stackrel{\text{iid}}{\sim }{P}_2,j=1,\dots ,m$, the null hypothesis is $H_0:P_1=P_2$, and suppose we have a test statistic $T:{\mathcal{X}}^{n+m}\to \mathbb{R}$ that measures the agreement of the first $n$ with the last $m$ elements.

• 📗 An example $T$ is $T(x_1,\dots ,x_n,y_1,\dots ,y_m)=|\frac{1}{n}{\sum }_{i=1}^n{x}_i-\frac{1}{m}{\sum }_{j=1}^m{y}_j|$.

The permutation test is conducted as follows:

Permutation test

1. Input: $Z=(x_1,\dots ,x_n,y_1,\dots ,y_m)\in {\mathcal{X}}^{n+m}$, $T^{\ast }=T(Z)$.
2. For $k=1,\dots K$:
   1. Draw a random permutation ${\sigma }_k\in S_{n+m}$; let $(Z_{\sigma }{)}_i=Z_{\sigma (i)}$.
   2. Compute $t_k=T(Z_{\sigma })$.
3. Return: $p=\frac{1+{\sum }_{k=1}^K\mathrm{𝟙}\{T^{\ast }\le t_k\}}{1+K}$.

We can see that the test relies on the property that a larger $T$ implies a larger asymmetry between the first $n$ and the last $m$ elements. Thus, if $T^{\ast }$ is large, we get a small p-value and is prone to reject $H_0:P_1=P_2$.

The permutation is

• 👍 Good. It is valid for all $P_1$, $P_2$, and proper $T$.

• Neutral. It requires choosing a proper $T$.

• 👎 Bad. The power of the test is not optimal; and it does not give Confidence Intervals for the difference of means.

To see the validity, we require that if $X_i\stackrel{d}{=}{Y}_j$ for all $1\le i\le n,1\le j\le m$, then $T(Z)\stackrel{d}{=}T(Z_{\sigma })$, where $\sigma \sim \mathrm{Unif}(S_{m+n})$, $S_{m+n}$ is the set of all permutations of $m+n$ elements. Then, we know that $p\to P(T^{\ast }\le T(Z_{\sigma }))$ as $K\to \infty$, and we have $P(T^{\ast }\le T(Z_{\sigma }))=1-F_T(T^{\ast })\sim \mathrm{Unif}[0,1]$, where $F_T$ is the CDF of $T^{\ast }=T(Z)$. That is, $p$ is super-uniform.