Darwin grew fifteen pairs of maize plants, one cross-fertilized and one self-fertilized in each pair, and Fisher analyzed the differences in height. The course page The Sign Test and the Wilcoxon Signed-Rank Test lists the fifteen differences, in eighths of an inch, as Wilcoxon (1945) took them from Fisher: thirteen favor the crossed plant and two favor the self-fertilized one. The sum of the fifteen differences is 314 eighths of an inch. Fisher's $t$-test gives $p = 0.0497$, which rests on the differences being a sample from a normal distribution, and two of them, $-48$ and $-67$, are far from the rest. Is there a test whose p-value is exact for these fifteen numbers without any assumption about the shape of their distribution?
There is. If crossing made no difference to height, then within each pair the label "crossed" could equally well have gone on the other plant, and the difference would have had the opposite sign. Under that hypothesis each of the $2^{15} = 32{,}768$ ways of attaching signs to the fifteen sizes is as likely as the one observed. Counting how many give a sum at least as large in absolute value as 314 gives an exact p-value. That is a permutation test: the reference distribution is generated by transformations of the data that leave its distribution unchanged when the null hypothesis holds.
Here is the route. First we count Darwin's sign patterns. Then we state the principle behind the count in general, for any finite group of transformations, and prove that the p-value it produces is exact. Paired data use sign flips and two samples use relabelings, and we prove which statistics give the same test. The rank tests of the course turn out to be permutation tests applied to ranks. Next we derive the mean and variance of the two-sample permutation distribution and prove where the test fails: it tests equal distributions, and as a test of equal means it loses its level when both the variances and the sample sizes differ. The studentized permutation test repairs it. Finally we prove that a p-value computed from a random sample of permutations is still valid, and invert the test to get a confidence interval. The article assumes Hypothesis Tests for a Mean for p-values and levels; Comparing Systems with Significance Tests applies the paired version to retrieval experiments, and this article supplies the theory under it.
Darwin's plants, counted
The fifteen differences have sizes $6, 8, 14, \dots, 75$, two of them carrying a minus sign. Every number in this article is computed by tools/experiments/statistics/permutation-tests.py. The script lists all 32,768 sign patterns, attaches each to the fifteen sizes and computes the sum of the fifteen signed differences:
- 835 patterns give a sum greater than the observed 314 and 28 give exactly 314, so 863 give a sum at least as large; the one-sided p-value is $863/32{,}768 = 0.0263$;
- the distribution of the sum is symmetric about zero (flipping every sign negates the sum), so 1,726 patterns give a sum at least 314 in absolute value, and the two-sided p-value is $1{,}726/32{,}768 = 0.0527$.
The $t$-test's two-sided $p = 0.0497$, with $t = 2.148$, is close to the exact 0.0527 but on the other side of 0.05. With a two-sided test at the 5% level, the exact count does not reject, and the normal model does by a hair. The difference matters less than what the count assumes: nothing about normality, only that under the null hypothesis each difference was as likely to have come out with the other sign.
The principle: a group of transformations
The count above used three ingredients: a set of transformations of the data (the sign patterns), a hypothesis that says these transformations do not change the distribution of the data, and a statistic. Fisher (1935) described the idea for experiments in which every rearrangement can be listed, and Hoeffding (1952) studied the large-sample power of "tests based on permutations of observations". The general setting is as follows.
The data are a random vector $X$ taking values in a set $\mathcal X$. A finite collection $\mathcal G$ of maps $g: \mathcal X \to \mathcal X$ forms a group under composition: it contains the identity, the composition of two of its maps is in it, and each map has an inverse in it. Two groups appear in this article:
- Sign flips. For paired differences $X = (D_1, \dots, D_n)$, the $2^n$ maps $(d_1, \dots, d_n) \mapsto (\epsilon_1d_1, \dots, \epsilon_nd_n)$ with each $\epsilon_i = \pm1$.
- Relabelings. For two samples pooled into $Z = (Z_1, \dots, Z_N)$, the first $n_1$ from one group and the other $n_2 = N - n_1$ from the other, the $N!$ maps $(z_1, \dots, z_N) \mapsto (z_{\pi(1)}, \dots, z_{\pi(N)})$, one for each permutation $\pi$ of $\{1, \dots, N\}$.
The null hypothesis is the randomization hypothesis: for every $g \in \mathcal G$, the random vector $gX$ has the same distribution as $X$. For sign flips it says that the joint distribution of the differences is unchanged by any change of signs. It holds in particular when the differences are independent and each is symmetric about zero. For relabelings it says that $Z_1, \dots, Z_N$ are exchangeable; in particular it holds when the two samples are independent draws from one common distribution, $P = Q$. Under the randomization hypothesis no element of the group is distinguishable from the observed arrangement.
A test statistic is a function $T: \mathcal X \to \mathbb R$, with large values counting against the null hypothesis. The permutation p-value is the share of the group that gives a value at least as large as the observed one: $$p(x) = \frac{1}{\lvert\mathcal G\rvert}\#\{g \in \mathcal G: T(gx) \ge T(x)\}.$$ The observed arrangement is always counted (the identity is in $\mathcal G$), so $p(x) \ge 1/\lvert\mathcal G\rvert$. A two-sided test uses $\lvert T\rvert$ as its statistic.
The key fact is a counting lemma about lists of numbers.
Lemma 1. Let $t_1, \dots, t_N$ be real numbers and $0 \le \alpha \le 1$. For each $j$ let $c_j = \#\{k: t_k \ge t_j\}$. Then $\#\{j: c_j \le \alpha N\} \le \alpha N$. If the $t_j$ are distinct, $\#\{j: c_j \le \alpha N\} = \lfloor\alpha N\rfloor$.
Proof. Let $J = \{j: c_j \le \alpha N\}$, suppose $J$ is not empty, and let $j^*$ be an index in $J$ with the smallest value $t_{j^*}$ among those in $J$. Every $k \in J$ has $t_k \ge t_{j^*}$, so $c_{j^*} \ge \lvert J\rvert$. Since $j^* \in J$, $c_{j^*} \le \alpha N$, and so $\lvert J\rvert \le \alpha N$. If the values are distinct, the index with the $c$-th largest value has $c_j = c$ exactly, so $J$ consists of the indices of the $\lfloor\alpha N\rfloor$ largest values. $\square$
Theorem 1 (exactness). Under the randomization hypothesis, $P\big(p(X) \le \alpha\big) \le \alpha$ for every $\alpha \in [0, 1]$, whatever the statistic $T$ and whatever the distribution of $X$ within the null hypothesis. If $T(gx)$, $g \in \mathcal G$, are distinct for almost every $x$, then $P\big(p(X) \le \alpha\big) = \lfloor\alpha\lvert\mathcal G\rvert\rfloor/\lvert\mathcal G\rvert$, which is $\alpha$ whenever $\alpha\lvert\mathcal G\rvert$ is a whole number.
Proof. Step 1: every point of an orbit is compared with the same list. For a fixed $x$ and any $h \in \mathcal G$, the list of values $\{T(g\,hx): g \in \mathcal G\}$ is the same list, with multiplicities, as $\{T(gx): g \in \mathcal G\}$, because $g \mapsto gh$ is a one-to-one map of $\mathcal G$ onto itself (its inverse is $g \mapsto gh^{-1}$). Hence $p(hx)$ is computed by comparing $T(hx)$ with the same list of $N = \lvert\mathcal G\rvert$ values $t_g = T(gx)$: in the notation of Lemma 1, $p(hx) = c_h/N$. Step 2: count over the orbit. By Lemma 1, for every fixed $x$, $$\frac1N\sum_{h \in \mathcal G}\mathbf 1\big[p(hx) \le \alpha\big] = \frac1N\#\{h: c_h \le \alpha N\} \le \alpha.$$ Step 3: average over the data. Under the randomization hypothesis $hX$ has the distribution of $X$ for each $h$, so $P(p(X) \le \alpha) = P(p(hX) \le \alpha)$ for every $h$, and averaging over $h$, $$P\big(p(X) \le \alpha\big) = E\Big[\frac1N\sum_{h \in \mathcal G}\mathbf 1\big[p(hX) \le \alpha\big]\Big] \le \alpha.$$ With distinct values Step 2 holds with equality, $\lfloor\alpha N\rfloor/N$, for almost every $x$. $\square$
Three remarks on what the theorem says. It is a finite-sample statement, not a large-sample approximation. It holds for every statistic, so the statistic can be chosen for power without any effect on validity. And the group property is used in Step 1: if the transformations did not form a group, the list of values seen from $hx$ could differ from the list seen from $x$, and the counting would fail. Ties between values of $T$ make the test conservative, as the inequality allows; Darwin's 28 patterns that tie the observed sum are counted against the null hypothesis, which is the conservative choice.
The equality clause rarely applies as stated to the tests of this article, because their statistics repeat across the group. The relabeling group of $N!$ maps produces each split of the pooled sample into a first group of $n_1$ and a second of $n_2$ exactly $n_1!\,n_2!$ times, and a statistic computed from the two groups takes the same value each time. So the p-value over the $N!$ permutations equals the p-value over the $\binom{N}{n_1}$ splits, and a uniformly random permutation gives a uniformly random split; that is why the counts below run over splits (210, or 847,660,528). Likewise, under sign flips a two-sided statistic takes the same value at a pattern and at its mirror image. In such cases the equality clause applies with the group replaced by the set of distinct arrangements: the splits for the two-sample test (for a two-sided test with $n_1 = n_2$, the pairs of complementary splits, which give the same $\lvert D\rvert$), the $2^{n-1}$ mirror pairs for a two-sided sign-flip test. (If $\mathcal G$ splits into classes of $r$ elements on each of which $T(gx)$ is constant, there are $M = \lvert\mathcal G\rvert/r$ classes. The p-value of each arrangement is then its count among the $M$ class values divided by $M$, and Steps 2 and 3 of the proof go through with Lemma 1 applied to those $M$ values. This gives $\lfloor\alpha M\rfloor/M$ when the class values are distinct.)
Paired data: sign flips
Example (Student's sleep data). The ten differences in hours of sleep between Student's two drugs (The Sign Test and the Wilcoxon Signed-Rank Test works them by signs and ranks) have mean 1.58 hours. Nine are positive and one is zero. Flipping signs can give a sum as large in absolute value as the observed 15.8 hours only when the nine nonzero differences all carry the same sign. The zero difference can carry either sign without changing anything. So 4 of the 1,024 sign patterns are as extreme, and the two-sided sign-flip p-value is $4/1024 = 0.0039$. That is the sign test's value for these data: when every nonzero difference has the same sign, the magnitudes cannot add anything. The paired $t$-test, which assumes normality, gives $p = 0.0028$.
Would the test change if the mean were replaced by the $t$ statistic, the mean divided by its estimated standard error? Under sign flips it would not.
Theorem 2 (studentizing changes nothing under sign flips). For sign flips of $d_1, \dots, d_n$ (not all zero), the one-sided sign-flip tests based on the sum $\sum d_i$ and on the one-sample statistic $t = \bar d/(s_d/\sqrt n)$ give the same p-value, and so do the two-sided tests based on $\lvert\sum d_i\rvert$ and $\lvert t\rvert$.
Proof. A sign flip leaves each $d_i^2$ unchanged, so $q = \sum d_i^2$ is the same for every element of the orbit. Since $(n - 1)s_d^2 = q - n\bar d^2$, $$t = \frac{\sqrt n\,\bar d}{\sqrt{(q - n\bar d^2)/(n - 1)}},$$ a function of $\bar d$ alone within the orbit. On $-\sqrt{q/n} < \bar d < \sqrt{q/n}$ its derivative is $\sqrt{n(n - 1)}\,q/(q - n\bar d^2)^{3/2} > 0$, so $t$ is a strictly increasing function of $\bar d$, and $\lvert t\rvert$ an increasing function of $\lvert\bar d\rvert$. At the ends of the range, where every $\lvert d_i\rvert$ is equal and all signs agree, $s_d = 0$ and $t = \pm\infty$ with the sign of $\bar d$, which preserves the order. An increasing function of the statistic orders the orbit the same way, so the counts in the definition of $p$ agree. $\square$
For Darwin's data the script confirms that the $t$ statistic gives the same 863 and 1,726 patterns. The randomization test of Comparing Systems with Significance Tests flips the signs of per-topic differences in a retrieval measure, so it is this test. By Theorem 2, running it on the paired $t$ statistic instead of the mean difference would make no difference.
Rank tests are permutation tests of ranks
Theorem 1 holds for any statistic, including one computed from ranks. The rank tests of the course are permutation tests whose statistics are functions of ranks.
- The sign test is the sign-flip test with the statistic "number of positive differences". For Darwin's data, 13 of 15 are positive, and the count of sign patterns with at least 13 or at most 2 positive gives $p = 0.0074$, the binomial value on the course page.
- The Wilcoxon signed-rank test is the sign-flip test with the statistic $W^+$, the sum of the ranks of $\lvert d_i\rvert$ that carry a plus sign. A sign flip does not change the ranks of the absolute values, only which of them are counted, so the null distribution is that of a sum of ranks each included with probability one half. For Darwin's data the smaller rank sum is 24, and the sign-flip count gives the exact two-sided $p = 0.0413$ of the course page.
- The Wilcoxon rank-sum test is the two-sample permutation test whose statistic is the sum of the first group's ranks in the pooled sample (The Wilcoxon Rank-Sum Test), and the Kruskal–Wallis test is the permutation test with several groups and the statistic $H$ computed from the pooled ranks (The Kruskal–Wallis Test samples its permutation distribution).
- Fisher's exact test for a $2 \times 2$ table is the two-sample permutation test applied to a 0/1 outcome with the statistic "number of ones in the first group"; Worked problem 2 shows that the permutation distribution is the hypergeometric.
What do the ranks buy? When there are no ties, the permutation distribution of a rank statistic is the same for every data set of a given size, because the ranks are always $1, \dots, N$. One table serves every application, and the course page on signed ranks recomputes Wilcoxon's own. A permutation test of the raw values needs its distribution recomputed for each data set, which is easy by computer and was laborious by hand. What do the ranks cost? The magnitudes. Asymptotic Relative Efficiency of Rank Tests measures the loss: the signed-rank test needs $\pi/3$ times as many observations as the $t$-test under normality, and can need fewer for heavy-tailed data. For permutation tests that use the values themselves, Hoeffding (1952) showed, by his abstract, that under his conditions they are "asymptotically (as the sample size tends to $\infty$) as powerful as certain related standard parametric tests".
Two samples: permuting labels
Example (older and younger adults). The course sample of Welch's t-Test has the systolic blood pressures of 10 NHANES adults aged 60 and over and 30 aged 18 to 39, drawn at random with the course script's seed. The older group's mean is 142.333 mm Hg and the younger group's 115.511, a difference in means of 26.822 mm Hg. Their standard deviations are 24.31 and 10.71: the small group is the variable one.
Under the null hypothesis that the 40 pressures are exchangeable, every choice of which 10 of the 40 are labeled "older" is equally likely, and there are $\binom{40}{10} = 847{,}660{,}528$ of them. That is too many to list here, so the script samples 99,999 relabelings at random; the last section proves that the sampled p-value is still valid. Before the numbers, two facts about the two-sample statistic.
Theorem 3 (the pooled t statistic gives the same test). For relabelings of a pooled sample, the permutation tests based on the difference in means $D = \bar z_1 - \bar z_2$ and on the pooled two-sample $t$ statistic give the same p-value, one-sided and two-sided.
Proof. Let $\bar z$ be the grand mean and $\mathrm{SST} = \sum_{i=1}^N(z_i - \bar z)^2$; both are the same for every relabeling. The between-groups sum of squares is $n_1(\bar z_1 - \bar z)^2 + n_2(\bar z_2 - \bar z)^2$, and since $\bar z_1 - \bar z = \frac{n_2}{N}D$ and $\bar z_2 - \bar z = -\frac{n_1}{N}D$, it equals $\frac{n_1n_2}{N}D^2$. The within-groups sum of squares is therefore $\mathrm{SSW} = \mathrm{SST} - \frac{n_1n_2}{N}D^2$, and the pooled statistic is $$t = \frac{D}{\sqrt{\dfrac{\mathrm{SSW}}{N - 2}\Big(\dfrac1{n_1} + \dfrac1{n_2}\Big)}} = \frac{c\,D}{\sqrt{\mathrm{SST} - kD^2}}, \qquad c = \sqrt{\frac{(N - 2)\,n_1n_2}{N}},\quad k = \frac{n_1n_2}{N}.$$ As in the proof of Theorem 2, its derivative in $D$ is $c\,\mathrm{SST}/(\mathrm{SST} - kD^2)^{3/2} > 0$ where $\mathrm{SSW} > 0$, so $t$ is an increasing function of $D$ within the orbit and $\lvert t\rvert$ of $\lvert D\rvert$. Where $\mathrm{SSW} = 0$, $\lvert D\rvert$ takes its largest value in the orbit, $\sqrt{\mathrm{SST}/k}$, and $t = \pm\infty$ with the sign of $D$, which preserves the order. $\square$
The script checks the theorem permutation by permutation: for each of the 30 × 99,999 sampled relabelings, $\lvert D\rvert$ and the pooled $\lvert t\rvert$ make the same decision. Dwass (1957) made the same observation for $D$ and $c\bar z_1$: the grand total is fixed, so the first group's mean orders the relabelings as $D$ does.
Theorem 4 (moments of the permutation distribution). Under uniform random relabeling of fixed numbers $z_1, \dots, z_N$, the difference in means has $$E_\pi(D) = 0, \qquad \operatorname{Var}_\pi(D) = S^2\Big(\frac1{n_1} + \frac1{n_2}\Big), \qquad S^2 = \frac{1}{N - 1}\sum_{i=1}^N(z_i - \bar z)^2.$$
Proof. Under a uniform relabeling the first group is a simple random sample of $n_1$ of the $N$ numbers, drawn without replacement. Its mean $\bar z_1$ has expectation $\bar z$ and variance $\frac{\sigma_N^2}{n_1}\cdot\frac{N - n_1}{N - 1}$, where $\sigma_N^2 = \frac1N\sum(z_i - \bar z)^2$: this is the finite population correction, derived in The Sampling Distribution of the Mean. Since $n_2\bar z_2 = N\bar z - n_1\bar z_1$, $$D = \bar z_1 - \frac{N\bar z - n_1\bar z_1}{n_2} = \frac{N}{n_2}(\bar z_1 - \bar z).$$ So $E_\pi(D) = 0$ and $\operatorname{Var}_\pi(D) = \frac{N^2}{n_2^2}\cdot\frac{\sigma_N^2}{n_1}\cdot\frac{n_2}{N - 1} = \frac{N\sigma_N^2}{N - 1}\cdot\frac{N}{n_1n_2} = S^2\Big(\frac1{n_1} + \frac1{n_2}\Big)$, because $N/(n_1n_2) = 1/n_1 + 1/n_2$. $\square$
The permutation distribution therefore has the spread of the pooled-variance standard error computed from the total sample variance $S^2$, with no allowance for the two groups having different spreads. For the 40 adults, the standard deviation of all 40 is 18.97 mm Hg, so the permutation standard deviation of $D$ is 6.928 mm Hg. Welch's standard error, $\sqrt{s_1^2/n_1 + s_2^2/n_2}$, is 7.933 mm Hg. The ratio of the two is 0.873. The permutation distribution is narrower than the sampling variation of $D$ that Welch's formula estimates, because it spreads the large variance of the 10 older adults over all 40 positions. Given these data, $S^2$ also contains the observed difference itself, since $(N - 1)S^2 = \mathrm{SSW} + \frac{n_1n_2}{N}D^2$ (the decomposition in the proof of Theorem 3): of $S^2 = 360.0$, the part $\frac{n_1n_2}{N}D^2/(N - 1) = 138.4$ comes from the observed difference. Without it the permutation standard deviation would be 5.44 mm Hg. The two effects act in opposite directions, and the permutation distribution is narrower than Welch's even so; Theorem 5 below treats the null case, where the difference is absent.
The p-values bear this out. Over 30 seeds of 99,999 relabelings, the permutation test based on the difference in means gave a median p-value of 0.00008, and by Theorem 3 the pooled $t$ statistic gave the same. The pooled $t$-test itself gives $p = 0.00002$ ($t = 4.870$). The test based on Welch's statistic, $t = 3.381$, computed for each relabeling, gave a median of 0.00534 (interquartile range 0.00524 to 0.00541), close to Welch's $t$-test, $p = 0.0068$. All agree that the older adults' pressures are higher. They disagree by a factor of about 70 on how strong the evidence is, and the reason is a statement about what each test tests.
What the two-sample test tests
The randomization hypothesis for relabelings is that the 40 values are exchangeable, which for two independent samples means $P = Q$: the two populations have the same distribution. Theorem 1 guarantees the level for that hypothesis and no other. A rejection says the distributions differ, but not how: it might be the means, the spreads or the shapes. Chung and Romano (2013, §1) make the point that the test based on the difference in means "is only appropriate as a test of equality of population means". Even as such a test, they note, it does not control its level in large samples unless the sample sizes are comparable or the variances equal. The same distinction appears for ranks in What the Rank-Sum Test Tests. The next theorem makes the failure exact.
Theorem 5 (the permutation variance under equal means). Let $X_1, \dots, X_{n_1}$ be independent with mean $\mu$ and variance $\sigma_1^2$, and $Y_1, \dots, Y_{n_2}$ independent of them with the same mean $\mu$ and variance $\sigma_2^2$. Then the permutation variance of Theorem 4, computed from the pooled data, has expectation $$E\big[\operatorname{Var}_\pi(D)\big] = \frac{n_1\sigma_1^2 + n_2\sigma_2^2}{n_1n_2},$$ while the actual variance of $D$ is $\operatorname{Var}(D) = \sigma_1^2/n_1 + \sigma_2^2/n_2$. The difference is $$E\big[\operatorname{Var}_\pi(D)\big] - \operatorname{Var}(D) = \frac{(n_1 - n_2)(\sigma_1^2 - \sigma_2^2)}{n_1n_2},$$ which is zero exactly when $n_1 = n_2$ or $\sigma_1^2 = \sigma_2^2$.
Proof. The pooled values $Z_1, \dots, Z_N$ are independent with common mean $\mu$ and variances $\sigma_i^2$ equal to $\sigma_1^2$ or $\sigma_2^2$. Then $\sum_i(Z_i - \bar Z)^2 = \sum_i(Z_i - \mu)^2 - N(\bar Z - \mu)^2$, whose expectation is $\sum_i\sigma_i^2 - N\operatorname{Var}(\bar Z) = \sum_i\sigma_i^2 - \frac1N\sum_i\sigma_i^2$. Dividing by $N - 1$, $E(S^2) = \frac1N\sum_i\sigma_i^2 = \frac{n_1\sigma_1^2 + n_2\sigma_2^2}{N}$. By Theorem 4, $E[\operatorname{Var}_\pi(D)] = E(S^2)\frac{N}{n_1n_2}$, which is the first formula. The actual variance follows from independence. Subtracting, over the common denominator $n_1n_2$: $n_1\sigma_1^2 + n_2\sigma_2^2 - n_2\sigma_1^2 - n_1\sigma_2^2 = (n_1 - n_2)(\sigma_1^2 - \sigma_2^2)$. $\square$
When the smaller sample has the larger variance, $(n_1 - n_2)(\sigma_1^2 - \sigma_2^2) < 0$: the permutation distribution is too narrow, and the test rejects too often. When the smaller sample has the smaller variance, it is too wide and the test is conservative. Theorem 5 is about the expected variance. The distributional statement is Chung and Romano's (2013) Theorem 2.1. It shows that the permutation distribution of $\sqrt N D$ converges to a normal distribution with variance $\frac{1}{p(1 - p)}\sigma^2(\bar P)$, where $p$ is the limit of $n_1/N$ and $\sigma^2(\bar P)$ the variance of the mixture $\bar P = pP + (1 - p)Q$. By contrast (their Remark 2.1), the sampling distribution of $\sqrt N D$ under equal means has variance $\frac1p\sigma_1^2 + \frac1{1 - p}\sigma_2^2$. Under equal means the mixture's variance is $p\sigma_1^2 + (1 - p)\sigma_2^2$, and their Example 2.1 states that the two variances agree if and only if $p = 1/2$ or $\sigma_1^2 = \sigma_2^2$, the large-sample form of Theorem 5.
The remedy: studentize. Theorem 3 says that the pooled $t$ statistic is no remedy, since it orders the relabelings exactly as $D$ does. The remedy is to divide by a standard error that is right whether or not the variances are equal, Welch's $\sqrt{s_1^2/n_1 + s_2^2/n_2}$, recomputed for every relabeling. Chung and Romano's Theorem 2.2 proves, for statistics of this studentized form, that the permutation distribution converges to the standard normal, the same limit as the statistic's sampling distribution under equal means. The studentized permutation test is therefore exact when $P = Q$, by Theorem 1, and has asymptotic level $\alpha$ when only the means are equal. Chung and Romano credit the idea to Neuhaus, for censored data, and its application to comparing means to Janssen (1997).
The level, by simulation. The script draws one sample from the NHANES adults aged 60 and over, shifted to the mean of the adults aged 18 to 39, and one from the adults aged 18 to 39. The population means are then equal, and the standard deviations are 21.02 and 12.85 mm Hg (variance ratio 2.68). For each design it draws 1,000 pairs of samples for each of 30 seeds and tests each pair at the 5% level, the permutation tests with 499 random relabelings. The table gives the median rejection rate over the 30 seeds, and the last column the large-sample rate that Chung and Romano's Theorem 2.1 predicts for the test based on $D$.
| Design | Permutation, $D$ | Permutation, Welch's $t$ | Welch $t$-test | Pooled $t$-test | Predicted, $D$ |
|---|---|---|---|---|---|
| 10 older, 30 younger | 0.127 | 0.065 | 0.061 | 0.126 | 0.120 |
| 30 older, 10 younger | 0.016 | 0.041 | 0.048 | 0.016 | 0.013 |
| 20 older, 20 younger | 0.055 | 0.055 | 0.053 | 0.055 | 0.050 |
With the variable group small, the test based on the difference in means rejects a true hypothesis of equal means 12.7% of the time (interquartile range over seeds 0.122 to 0.130), two and a half times the nominal rate. It tracks the pooled $t$-test throughout, as Theorem 3 leads one to expect. The prediction from the limit, 0.120, is close. Reversing the sizes makes the same test conservative, and equal sizes make it nearly right. The studentized permutation test stays within about 1.5 points of 5% in every design, as Welch's $t$-test does. These are results for these two NHANES populations at these sample sizes; at 10 and 30 they are some distance from the limit, and the studentized test's 0.065 is above 0.05.
Which to use? If the question is whether the two groups differ in any way, the plain permutation test is exact and needs no studentizing. If the question is whether the means differ, and the spreads may not be equal, the studentized statistic keeps the exactness for identical distributions and adds approximate validity for equal means, so there is little reason to use anything else. For the 40 adults the studentized permutation p-value of 0.0053 is the one that answers the question about means.
Monte Carlo p-values
For the 40 adults the script used 99,999 random relabelings, not all 847 million. Is a p-value computed from a random sample of the group still exact? Yes, if the observed arrangement is counted as one of the sample. Dwass (1957) studied tests based on randomly chosen permutations, and Phipson and Smyth (2010), who review that literature, show that the commonly used estimate $b/B$ is not a valid p-value and that $(b + 1)/(B + 1)$ is.
Theorem 6 (Monte Carlo permutation p-values). Let $G_1, \dots, G_B$ be drawn independently and uniformly from $\mathcal G$, independently of $X$, and let $b = \#\{j: T(G_jX) \ge T(X)\}$. Under the randomization hypothesis, $$\hat p = \frac{b + 1}{B + 1}\quad\text{satisfies}\quad P(\hat p \le \alpha) \le \alpha\ \text{ for every } \alpha \in [0, 1].$$
Proof. Step 1: a representation. Let $H$ be uniform on $\mathcal G$, independent of $X$ and the $G_j$, and put $X' = HX$. Conditionally on $H = h$ and on the $G_j$, $X'$ is $hX$, which by the randomization hypothesis has the distribution of $X$; since that conditional distribution does not depend on $h$ or the $G_j$, $X'$ is independent of $(H, G_1, \dots, G_B)$ and has the distribution of $X$. Now $X = H^{-1}X'$ and $G_jX = G_jH^{-1}X'$. Set $K_0 = H^{-1}$ and $K_j = G_jH^{-1}$. Step 2: the $K$s are independent and uniform. $H^{-1}$ is uniform, because inversion is a one-to-one map of the group onto itself. Given $H = h$, each $G_jh^{-1}$ is uniform, because right multiplication by $h^{-1}$ is one-to-one, and they are independent of each other. So $K_0, K_1, \dots, K_B$ are independent, each uniform on $\mathcal G$, and independent of $X'$. Step 3: exchangeability. The $B + 1$ statistics $T(K_jX')$, $j = 0, \dots, B$, are therefore conditionally independent and identically distributed given $X'$, hence exchangeable, and the observed statistic is the one with $j = 0$. By exchangeability, the probability that index 0 has $c_0 = \#\{j: T(K_jX') \ge T(K_0X')\} \le k$ equals the average over the $B + 1$ indices of the same probability, which by Lemma 1 (with $N = B + 1$ and $\alpha N = k$) is at most $k/(B + 1)$. Since $\hat p = c_0/(B + 1)$, $P(\hat p \le \alpha) \le \lfloor\alpha(B + 1)\rfloor/(B + 1) \le \alpha$. $\square$
The proof needs only that the transformations are drawn uniformly and independently; it does not need them to be distinct, and repeats of the identity are harmless. The "$+1$" is the observed arrangement, and it keeps $\hat p$ from being 0.
What goes wrong with $b/B$? Because the transformations are drawn with replacement from a finite group, two draws can coincide and the $B + 1$ values can tie with positive probability, so $b$ is not exactly uniform. When the group is so large that repeated draws and ties have negligible probability, the exchangeability in the proof makes $b$ uniform on $\{0, 1, \dots, B\}$ in the limit, and $P(b/B \le \alpha)$ approaches $(\lfloor\alpha B\rfloor + 1)/(B + 1)$. With $B = 1000$ and $\alpha = 0.05$ that is $51/1001 = 0.0509$, above the nominal 0.05, while $(b + 1)/(B + 1)$ gives $50/1001 = 0.0500$. (For a small group the ties change the picture; Phipson and Smyth (2010) note that with replacement the exact p-value is slightly less than $(b + 1)/(B + 1)$.) The excess is small, but a p-value of exactly zero, which $b/B$ produces whenever no sampled arrangement reaches the observed one, is wrong in a way that matters when many tests are made. For the 40 adults the 30 runs found between 2 and 11 relabelings with $\lvert D\rvert$ at least 26.822, so $\hat p$ ranged from 0.00003 to 0.00012.
The Monte Carlo p-value is valid at any $B$, and $B$ controls only how close it is to the full permutation p-value $p(x)$. Given the data, each $G_j$ is uniform on $\mathcal G$, so $P(T(G_jx) \ge T(x)) = p(x)$ exactly and $b$ is binomial with $B$ trials and probability $p(x)$. The standard deviation of $\hat p$ is then $\sqrt{Bp(1 - p)}/(B + 1)$, about $\sqrt{p(1 - p)/B}$. For a p-value near 0.05 and $B = 9{,}999$ it is about 0.002.
Confidence intervals by inverting the test
A test of every possible value of a parameter gives a confidence set: the values that are not rejected. For paired data, the hypothesis that the differences are symmetric about $\delta$ can be tested by flipping the signs of $d_i - \delta$. The set of $\delta$ for which the two-sided test at level 0.05 does not reject is a 95% confidence set for the center of symmetry. By Theorem 1 its coverage is at least 95% whenever the differences are symmetric about their center, with no further assumption.
For Student's sleep data the script scans $\delta$ in steps of 0.001 hours and refines the endpoints by bisection. For a two-sided statistic the accepted set need not be an interval in general, but here it can be found exactly. Between consecutive differences each $\lvert d_i - \delta\rvert$ is a fixed linear function of $\delta$, so a sign pattern's sum can cross the observed sum (or its negative) only where $\sum_{i \in A}(d_i - \delta) = 0$ for some set $A$ of differences, that is, at the mean of a subset; the kinks at $\delta = d_i$ are subset means too. The p-value is therefore constant between consecutive subset means. The 272 distinct subset means run from 0 to 4.6 hours and are at least 0.0016 apart, wider than the scan's step of 0.001. Evaluating the p-value exactly at every subset mean, at the midpoints between them and beyond the two ends (where it is constant and rejects), the script finds the exact accepted set $[5/6, 37/15]$, one interval. Inverting the sign-flip test gives the interval from 0.83 to 2.47 hours. The $t$ interval, which assumes normal differences, runs from 0.70 to 2.46 hours. The permutation interval is shorter on the left. Ten differences give only 1,024 sign patterns, so the p-value as a function of $\delta$ is a step function and the interval's endpoints sit where it crosses 0.05. Its coverage is at least 95% by construction but need not be exactly 95%. For the shift between two samples, the same inversion of the rank-sum test gives the Hodges–Lehmann interval of What the Rank-Sum Test Tests.
Randomization and populations
Two justifications lead to the same calculation. In a randomized experiment the experimenter assigns treatments at random. If the treatment has no effect on any unit, the outcomes would have been the same under every assignment, and the random assignment alone makes every relabeling equally likely. The randomization hypothesis then holds by design, with no assumption about how the units were sampled. That is the setting Fisher (1935) described, and Phipson and Smyth (2010) note that the idea of permutation tests was first described by him, with every permutation listed. In a population model the two samples are independent random samples and the null hypothesis is that their populations are the same. Pitman's papers of 1937 and 1938 carry the title "Significance tests which may be applied to samples from any populations". By their titles, they treat two samples, the correlation coefficient (permuting one variable against the other) and the analysis of variance in that setting; Dwass (1957) credits Pitman with the two-sample test based on the difference in means. Theorem 1 covers both: it needs only that the group leaves the distribution of the data unchanged, and it does not matter whether that invariance comes from the design or from the sampling.
The difference matters for what a rejection means. In the randomized experiment it is evidence that the treatment affected some units. In the population model it is evidence that the populations differ, and, as the previous sections showed, not necessarily in the parameter the statistic was chosen to estimate. The Darwin example is of the first kind only if the crossed and self-fertilized plant in each pot were placed at random; the course page's data cannot say whether they were.
What is proved here, what is cited, what the experiment shows
Proved here. The counting lemma and the exactness of permutation p-values under the randomization hypothesis for any finite group and any statistic, with equality for distinct values (Lemma 1, Theorem 1). That the one-sample $t$ statistic and the mean give the same sign-flip test (Theorem 2), and the pooled $t$ statistic and the difference in means the same two-sample test (Theorem 3). The mean and variance of the two-sample permutation distribution (Theorem 4), given the finite population correction proved on the course page. The expected permutation variance under equal means and its difference from the actual variance (Theorem 5). The validity of $(b + 1)/(B + 1)$ (Theorem 6) and the level of $b/B$. The identification of the sign, signed-rank and rank-sum tests and Fisher's exact test as permutation tests follows from the definitions, and Worked problem 2 checks the last.
Cited. The limiting permutation distributions of the unstudentized and studentized statistics (Chung and Romano, 2013, Theorems 2.1 and 2.2, Remark 2.1 and Example 2.1). Hoeffding's (1952) large-sample power result. The history: Fisher (1935) as reported by Phipson and Smyth (2010); Pitman (1937, 1938) by title; Dwass (1957); Janssen (1997) and Neuhaus as credited by Chung and Romano.
What the experiments show. The exact counts for Darwin's and Student's data and the inverted interval. For the 40 NHANES adults, Monte Carlo p-values over 30 seeds and the permutation-by-permutation agreement of $D$ and the pooled $t$. For the two NHANES age-group populations with equal means, the rejection rates in the table, which are observations for those populations and sample sizes.
Worked problems
The four problems are posed here, on hand-sized subsets of the article's data and on its theorems; the article's script checks each number.
Problem 1 (an enumeration of all splits). Take the first four older adults of the Welch sample, with pressures 162.0, 157.3, 137.3 and 142.7 mm Hg, and the first six younger adults, 113.3, 120.0, 130.0, 114.7, 111.3 and 124.7 mm Hg (values rounded here to one decimal; the script uses the exact means of the readings). Find the two-sided permutation p-value for the difference in means by listing all splits, and check Theorem 4.
Solution. The p-value is $1/210 = 0.0048$. There are $\binom{10}{4} = 210$ ways to choose which four of the ten values form the first group. The observed difference in means is $D = 30.833$ mm Hg. Every one of the four older adults has a higher pressure than every one of the six younger ones, so the observed split puts the four largest values in the first group, which gives the largest possible $D$. A split with $D \le -30.833$ would need the first group's mean to be far below the second's, and the most negative split, with the four smallest values in the first group, gives only $D = -27.500$, because the four smallest values sit closer to the center than the four largest. So only the observed split is as extreme, out of the 210, and the script's enumeration confirms the count of 1. For Theorem 4, the sample variance of the ten values is $S^2 = 328.59$, so $\operatorname{Var}_\pi(D) = 328.59\,(1/4 + 1/6) = 136.91$; the variance of the 210 values of $D$ computed directly is 136.91, and their mean is 0.
Problem 2 (Fisher's exact test). Call a pressure of at least 130 mm Hg "high". In the ten adults of Problem 1, all four of the four older adults are high, and five of the ten are high. Show that the permutation distribution of the number of high values in the first group is hypergeometric, and find the one-sided p-value.
Solution. The one-sided p-value is $1/42 = 0.0238$. Under random relabeling the first group is a random subset of four of the ten adults. The number $K$ of high values in it is therefore the number of high values in a sample of four drawn without replacement from ten, of which five are high. Counting subsets, $P(K = j) = \binom5j\binom{5}{4 - j}\big/\binom{10}{4}$, the hypergeometric distribution: $1/42$, $5/21$, $10/21$, $5/21$ and $1/42$ for $j = 0, \dots, 4$, which the script also obtains by tallying all 210 splits. The observed $K = 4$ is the largest possible value, so $p = P(K \ge 4) = \binom54\binom50/210 = 5/210 = 1/42$. This is Fisher's exact test for the $2 \times 2$ table of group against high pressure, conditional on both margins, as The Chi-Square Test of Independence derives the distribution of a table given its margins.
Problem 3 (the smallest attainable p-value). With $n$ paired differences, none zero, what is the smallest two-sided p-value a sign-flip test can produce, and how many pairs are needed before a test at the 5% level can reject?
Solution. The smallest p-value is $2/2^n$, and at least six pairs are needed. By Theorem 1 the p-value is a count divided by $2^n$. The observed pattern and its mirror image (every sign flipped) always give the same value of $\lvert T\rvert$ for any statistic of the form $\lvert\sum\epsilon_ia_i\rvert$, so the two-sided count is at least 2. With $n = 5$ the smallest p-value is $2/32 = 0.0625 > 0.05$, so five pairs can never reject; with $n = 6$ it is $2/64 = 0.031$. This is the floor the course page found for the sign and signed-rank tests, and the same argument applies to every sign-flip test whose two-sided statistic takes the same value at a sign pattern and at its mirror image.
Problem 4 (the predicted level of the unstudentized test). For samples of 10 from a population with variance $\sigma_1^2$ and 30 from one with variance $\sigma_2^2$, with $\sigma_1^2/\sigma_2^2 = 2.677$, find the large-sample rejection rate at nominal level 0.05 of the two-sided permutation test based on the difference in means, when the means are equal.
Solution. The rate is about 0.120. Take $\sigma_2^2 = 1$ and $p = 10/40 = 0.25$. By Chung and Romano's Theorem 2.1, with equal means, the permutation distribution of $\sqrt N D$ has variance $\frac{p\sigma_1^2 + (1 - p)\sigma_2^2}{p(1 - p)} = \frac{0.25 \times 2.677 + 0.75}{0.1875} = 7.569$, while the sampling distribution has variance $\frac{\sigma_1^2}{p} + \frac{\sigma_2^2}{1 - p} = 10.708 + 1.333 = 12.041$. The test rejects when $\lvert D\rvert$ exceeds 1.96 permutation standard deviations, which is $1.96\sqrt{7.569/12.041} = 1.96 \times 0.793 = 1.554$ actual standard deviations. Since $D$ is approximately normal, the rejection rate is $2\,(1 - \Phi(1.554)) = 0.120$. The simulation of 10 older and 30 younger NHANES adults found 0.127, slightly above the limit.
Summary
- A permutation test compares the observed statistic with its values over a group of transformations that leave the data's distribution unchanged under the null hypothesis. Its p-value is exact in finite samples for any statistic (Theorem 1).
- Paired data use sign flips, two samples use relabelings. Studentizing by the one-sample $t$ changes nothing under sign flips, and the pooled $t$ changes nothing under relabelings (Theorems 2 and 3).
- The sign, signed-rank, rank-sum and Kruskal–Wallis tests and Fisher's exact test are permutation tests with statistics computed from signs, ranks or counts.
- The two-sample permutation distribution of the difference in means has variance $S^2(1/n_1 + 1/n_2)$, built from the total variance (Theorem 4). As a test of equal means it is too liberal when the smaller sample is the more variable, and too conservative in the reverse case (Theorem 5); in the NHANES simulation it rejected 12.7% of the time at nominal 5%. Studentizing by Welch's standard error restores the level approximately and keeps exactness for identical distributions.
- With randomly sampled transformations, $(b + 1)/(B + 1)$ is a valid p-value at every $B$ (Theorem 6); $b/B$ is not.
- Inverting the test gives confidence intervals; for the sleep data, 0.83 to 2.47 hours.
What we have learned
A permutation test draws its exactness from an invariance, and that invariance must be the null hypothesis one actually wants to test. Sign flips and relabelings give exact tests of symmetry and of identical distributions; as tests of a mean or a difference in means they need a studentized statistic. The bootstrap, which The Plug-In Principle and Why the Bootstrap Works introduces, approaches the same questions by estimating the distribution of a statistic rather than by conditioning on an orbit of the data. Comparing Systems with Significance Tests shows the two disagreeing on ten retrieval topics, and the paired comparisons of evaluation scores in Paired Comparisons of Models use both. Both, as stated here, assume independent units. The Jackknife turns to a third resampling scheme, leaving one observation out, and Resampling Dependent and Clustered Data shows what to permute or resample when the units are not independent.
References
- Chung, E., and Romano, J. P. (2013). Exact and asymptotically robust permutation tests. The Annals of Statistics, 41(2), 484–507. https://doi.org/10.1214/13-AOS1090 (arXiv:1304.5939) record
- Dwass, M. (1957). Modified randomization tests for nonparametric hypotheses. The Annals of Mathematical Statistics, 28(1), 181–187. https://doi.org/10.1214/aoms/1177707045 record
- Fisher, R. A. (1935). The Design of Experiments. Edinburgh: Oliver and Boyd. record · 3 pages
- Hoeffding, W. (1952). The large-sample power of tests based on permutations of observations. The Annals of Mathematical Statistics, 23(2), 169–192. https://doi.org/10.1214/aoms/1177729436 record
- Janssen, A. (1997). Studentized permutation tests for non-i.i.d. hypotheses and the generalized Behrens–Fisher problem. Statistics and Probability Letters, 36(1), 9–21. https://doi.org/10.1016/S0167-7152(97)00043-6 record
- Phipson, B., and Smyth, G. K. (2010). Permutation p-values should never be zero: Calculating exact p-values when permutations are randomly drawn. Statistical Applications in Genetics and Molecular Biology, 9(1), Article 39. https://doi.org/10.2202/1544-6115.1585 (arXiv:1603.05766) record
- Pitman, E. J. G. (1937a). Significance tests which may be applied to samples from any populations. Supplement to the Journal of the Royal Statistical Society, 4(1), 119–130. https://doi.org/10.2307/2984124 record
- Pitman, E. J. G. (1937b). Significance tests which may be applied to samples from any populations. II. The correlation coefficient test. Supplement to the Journal of the Royal Statistical Society, 4(2), 225–232. https://doi.org/10.2307/2983647 record
- Pitman, E. J. G. (1938). Significance tests which may be applied to samples from any populations. III. The analysis of variance test. Biometrika, 29(3–4), 322–335. https://doi.org/10.1093/biomet/29.3-4.322 record
- Wilcoxon, F. (1945). Individual comparisons by ranking methods. Biometrics Bulletin, 1(6), 80–83. https://doi.org/10.2307/3001968 record · 6 pages