Permutation test

A permutation test (also called re-randomization test or shuffle test) is an exact statistical hypothesis test. A permutation test involves two or more samples. The (possibly counterfactual) null hypothesis is that all samples come from the same distribution ${\displaystyle H_{0}:F=G}$. Under the null hypothesis, the distribution of the test statistic is obtained by calculating all possible values of the test statistic under possible rearrangements of the observed data. Permutation tests are, therefore, a form of resampling.

Permutation tests can be understood as surrogate data testing where the surrogate data under the null hypothesis are obtained through permutations of the original data.

In other words, the method by which treatments are allocated to subjects in an experimental design is mirrored in the analysis of that design. If the labels are exchangeable under the null hypothesis, then the resulting tests yield exact significance levels; see also exchangeability. Confidence intervals can then be derived from the tests. The theory has evolved from the works of Ronald Fisher and E. J. G. Pitman in the 1930s.

Permutation tests should not be confused with randomized tests.

To illustrate the basic idea of a permutation test, suppose we collect random variables ${\displaystyle X_{A}}$ and ${\displaystyle X_{B}}$ for each individual from two groups ${\displaystyle A}$ and ${\displaystyle B}$ whose sample means are ${\displaystyle {\bar {x}}_{A}}$ and ${\displaystyle {\bar {x}}_{B}}$, and that we want to know whether ${\displaystyle X_{A}}$ and ${\displaystyle X_{B}}$ come from the same distribution. Let ${\displaystyle n_{A}}$ and ${\displaystyle n_{B}}$ be the sample size collected from each group. The permutation test is designed to determine whether the observed difference between the sample means is large enough to reject, at some significance level, the null hypothesis H${\displaystyle _{0}}$ that the data drawn from ${\displaystyle A}$ is from the same distribution as the data drawn from ${\displaystyle B}$.

The test proceeds as follows. First, the difference in means between the two samples is calculated: this is the observed value of the test statistic, ${\displaystyle T_{\text{obs}}}$.

Next, the observations of groups ${\displaystyle A}$ and ${\displaystyle B}$ are pooled, and the difference in sample means is calculated and recorded for every possible way of dividing the pooled values into two groups of size ${\displaystyle n_{A}}$ and ${\displaystyle n_{B}}$ (i.e., for every permutation of the group labels A and B). The set of these calculated differences is the exact distribution of possible differences (for this sample) under the null hypothesis that group labels are exchangeable (i.e., are randomly assigned).

The one-sided p-value of the test is calculated as the proportion of sampled permutations where the difference in means was greater than ${\displaystyle T_{\text{obs}}}$. The two-sided p-value of the test is calculated as the proportion of sampled permutations where the absolute difference was greater than ${\displaystyle |T_{\text{obs}}|}$. Many implementations of permutation tests require that the observed data itself be counted as one of the permutations so that the permutation p-value will never be zero.