# Two-tailed one-sample permutation test

I want to test the significance of the classification accuracy of a cross-validated binary classifier.

I performed a permutation test to determine whether the true classification accuracy is higher than the chance level classification accuracy:

How to perform a two-tailed version of such a test?

• If you're generally interested in how to perform a two-tailed permutation test, that's okay, but for your particular purpose, what's wrong with the regular proportion test? The R function is prop.test. Also, what did you permute, the group labels and then run the same classification model (retrained, I guess) to check for accuracy?
– Dave
Commented Sep 26, 2019 at 0:38
• It boils down to how, exactly, you quantify "at least as extreme". With location tests, often deviation from a point-null (absolute difference in means) makes sense but in other cases it may make more sense to argue that you should do other things (doubling the smaller p-value is pretty common; sometimes it makes sense to do just that). Commented Sep 26, 2019 at 5:24

In many cases the P-value of a 2-sided test is twice the P-value of a 1-sided test.

For demonstration purposes, here are descriptions of a sample of size $$n = 100$$ from a Laplace distribution (centered at 2 and with much heavier tails than normal).

summary(x)
Min.  1st Qu.   Median     Mean  3rd Qu.     Max.
-13.0858  -0.2901   1.0873   0.8850   1.8196  11.6360
sd(x);  length(x)
[1] 3.122601
[1] 100

boxplot(x, col="skyblue2", pch = 20, horizontal=T)


Here is a permutation test, in R, of $$H_0: \mu = 0$$ vs $$H_a: \mu \ne 0.$$ At each iteration, the sign of each observation is randomly changed between $$\pm 1.$$ At each iteration, the mean of the sign-permuted data is found. [That is, the 'metric' of the permutation test is the sample mean.] The observed mean of the sample is 1.885.

set.seed(1234)
a.obs = mean(x)
a.prm = replicate(10^5, mean(sample(c(-1,1),100,rep=T)*x) )
mean(abs(a.prm) >= abs(a.obs))
[1] 0.00496                     # P-value of two-sided test

hist(a.prm, prob=T, col="skyblue2", xlim=c(-7,7))
abline(v=c(a.obs,-a.obs), col="red")


The P-value of the two-sided test is the area in both tails beyond the vertical red lines.

For a one-sided test (against $$H_a: \mu > 0,$$ the P-value would be the value in the right tail beyond 0.885. R-code 'mean(a.prm >= a.obs), which returns 0.00223.

Notes: (1) In the R code for the P-values, the vector with >= is a logical vector with $$10^5$$ TRUEs and FALSEs, and the mean is the proportion of its TRUE`s. (2) Eudey et al. has an elementary presentation of permutation tests; Sect. 2 on paired tests is similar to your one-sample test.

• Thanks! In my case, shuffles correspond to permutations of the two classes' labels I classify. So you would just double the p_value I found with the one-sided test? Commented Oct 10, 2019 at 0:49
• If you do a one-sided test and get P-value 0.01, then the P-value for a corresponding 2-sided test is 0.02. // But you can't apply the 'doubling rule' blindly. If your one-sided test is in the "wrong direction" and the P-value is 0.83, then you obviously wouldn't double that P-value. Commented Oct 10, 2019 at 0:56
• Thanks! In which cases doesn't this (doubling the smallest one-sided p-value to get the two-sided one) hold true? Commented Oct 10, 2019 at 2:05
• Getting a probability > 1 is always a clue something's wrong. Commented Oct 10, 2019 at 2:29

If you have collected $$N$$ permutation scores, $$s_1,\ldots,s_N$$, the two-sided p-value for a treshold, $$t$$, can be estimated as $$p_2(t) = {\rm min}(2\frac{|\{ s_i \geq t\}|}{N}, 2(1-\frac{|\{s_i \geq t\}|}{N}))$$. I.e. just divide 2 times the number of permutations with scores greater or equal to your treshold with the total number of permutations. If the resulting value is less than one, then use the value directly, othervise subtract the value from 2.