What is the benefit of using permutation tests?

Question

When testing some null versus alternative hypotheses by a test statistic $U(X)$, where $X = \{ x_i, ..., x_n\}$, apply the permutation test with the set $G$ of permutations on $X$ and we have a new statistic $$ T(X) := \frac{\# \{\pi \in G: U(\pi X) \geq U(X)\}}{|G|}. $$

1. What is the benefit of using the permutation test over not using it? I.e. what is it like when the permutation test works?

2. What conditions to make that happen? Such as some conditions on the test statistic $U$ and/or on the null hypothesis?

For example,

1. Should $T(X)$ be equal to the p-value based on $U(X)$, for sample $X$? If yes, why? (references is also appreciated)

   The p-value of $U(X)$ is defined as $$\inf_{c \in \mathbb R: U(x) \geq c} \sup_{F \in H} P(U(X) \geq c | X \sim F)$$. If the permutation test is to estimate the permutation distribution of $U(X) | X=x$, how is $T(X)$ equals the p-value of $U(X)$ at $X=x$? Especially, there may be more than one distributions in the null $H$, and $T(X)$ doesn't consider the null distributions one by one and then take $\sup_{F\in H}$ and $\inf_{c: U(x) \geq c}$.

2. Should the permutation test make $T(X)$ distribution-free over the null hypotheses? What conditions will make that happen?

3. Should $T(X)$ be uniformly distributed over $[0,1]$? What conditions will make that happen? Notice that when $U(\cdot)$ is a constant function, $T(\cdot)$ is also constant at $1$ and the distribution of $T(X)$ is far from being uniform over $[0,1]$.

Thanks and regards!

Answer 1

Since the discussion grew long, I've taken my responses to an answer. But I've changed the order.

Permutation tests are "exact", rather than asymptotic (compare with, for example, likelihood ratio tests). So, for example, you can do a test of means even without being able to compute the distribution of the difference in means under the null; you don't even need to specify the distributions involved. You can design a test statistic that has good power under a set of assumptions without being as sensitive to them as a fully parametric assumption (you can use a statistic that is robust but has good A.R.E.).

Note that the definitions you give (or rather, whoever you're quoting there gives) are not universal; some people would call U a permutation test statistic (what makes a permutation test is not the statistic but how you evaluate the p-value). But once you're doing a permutation test and you have assigned a direction as 'extremes of this are inconsistent with H0', that kind of definition for T above is basically how you work out p-values - it's just the actual proportion of the permutation distribution at least as extreme as the sample under the null (the very definition of a p-value).

So for example, if I want to do a (one-tailed, for simplicity) test of means like a two-sample t-test, I could make my statistic the numerator of the t-statistic, or the t-statistic itself, or the sum of the first sample (each of those definitions is monotonic in the others, conditional on the combined sample), or any monotonic transformation of them, and have the same test, since they yield identical p-values. All I need to do is see how far into (in terms of proportion) the permutation distribution of whatever statistic I choose the sample statistic lies. T as defined above is just another statistic, as good as any other I could choose (T as defined there being monotonic in U).

T won't be exactly uniform, because that would require continuous distributions and T is necessarily discrete. Because U and therefore T can map more than one permutation to a given statistic, the outcomes aren't equi-probable, but they have a "uniform-like" cdf**, but one where the steps aren't necessarily equal in size.

** ($F(x)\leq x$, and strictly equal to it at the right limit of each jump -- there's probably a name for what that actually is)

For reasonable statistics as $n$ goes to infinity the distribution of $T$ approaches uniformity. I think the best way to begin to understand them is really to do them in a variety of situations.

Should T(X) be equal to the p-value based on U(X), for any sample X? If I understand correctly, I found it on page 5 of this slides.

T is the p-value (for cases where large U indicates deviation from the null and small U is consistent with it). Note that the distribution is conditional on the sample. So its distribution isn't 'for any sample'.

So the benefit of using permutation test is to compute the p-value of the original test statistic U without knowing the distribution of X under null? Therefore, the distribution of T(X) can be not necessarily uniform?

I've already explained that T isn't uniform.

I think I have already explained what I see as the benefits of permutation tests; other people will suggest other advantages (e.g.).

Does "T is the p-value (for cases where large U indicates deviation from the null and small U is consistent with it)", mean that the p-value for test statistic U and sample X is T(X)? Why? Is there some reference for explaining that?

The sentence you quoted explicitly states that T is a p-value, and when it is. If you can explain what is unclear about it maybe I could say more. As for why, see the definition of p-value (first sentence at the link) - it quite directly follows from that

There's a good elementary discussion of permutation tests here.

--

Edit: I add here a small permutation test example; this (R) code is only suitable for small samples - you need better algorithms for finding the extreme combinations in moderate samples.

Consider a permutation test against a one-tailed alternative:

$H_0: \mu_x = \mu_y$ (some people insist on $\mu_x \geq \mu_y$*)
$H_1: \mu_x < \mu_y$

* but I usually avoid it because it particularly tends to confuse the issue for students when trying to work out null distributions

on the following data:

> x;y
[1] 25.17 20.57 19.03
[1] 25.88 25.20 23.75 26.99

There are 35 ways of dividing the 7 observations into samples of size 3 and 4:

> choose(7,3)
[1] 35

As mentioned before, given the 7 data values, the sum of the first sample is monotonic in the difference in means, so let's use that as a test statistic. So the original sample has a test statistic of:

> sum(x)
[1] 64.77

Now here's the permutation distribution:

> sort(apply(combn(c(x,y),3),2,sum))
 [1] 63.35 64.77 64.80 65.48 66.59 67.95 67.98 68.66 69.40 69.49 69.52 69.77
[13] 70.08 70.11 70.20 70.94 71.19 71.22 71.31 71.62 71.65 71.90 72.73 72.76
[25] 73.44 74.12 74.80 74.83 75.91 75.94 76.25 76.62 77.36 78.04 78.07

(It's not essential to sort them, I just did that to make it easier to see the test statistic was the second value in from the end.)

We can see (in this case by inspection) that $p$ is 2/35, or

> 2/35
[1] 0.05714286

(Note that only in the case of no x-y overlap is a p-value below .05 possible here. In this case, $T$ would be discrete uniform because there are no tied values in $U$.)

The pink arrows indicate the sample statistic on the x-axis, and the p-value on the y-axis.