Permutation statistics yield different results when computed again I am doing a within-subject design experiment and trying to analyze my data. To simplify my problem, let's say that there is condition A and condition B, and I have 24 pariticipants. I want to do permutation statistics in order to test if there is a difference between condition A and B. From what I understood, there is 2^24 possible permutations, as we compute either A(i) - B(i) or B(i) - A(i) for each participant. As this is not possible to do all the permutation, I only compute N=2000 permutations but then, if I run multiple times my code, since there is always a different permutation, sometimes I can get a significant results p < 0.05 and sometimes a non significant results. This is annoying as I don't want to do "p-hacking".
My question is then : How to deal with permutation statistics yielding different results when we only do a part of possible permutations ?
I tried to read different explanation of permutation statistics and some says that 5000 permutations "is enough" but that does not solve the problem of non-determinism...
I hope that I am clear, feel free to ask for more details if needed.
Thank you !
 A: If you're down to setting seeds to get reproducible results from
permutation tests, something may be wrong. Maybe the sample size (e.g., your 24) is too small,
you're not using enough permutations (e.g., your 2000), the metric does not take enough uniquely
different values, or there is a programming error. Obviously, a simulated
permutation test is subject to simulation error, but in my experience,
running such a test several times with different seeds (or no seed) gives
substantially similar results on each run.
Let's take a look at the kind of simulated permutation test you are
using---for fictitious non-normal data---to see how my version of it works in R.
Suppose we have $n = 24$ differences $B - A$ as in my vector dif below:
The observed average difference is $1.67.$  Also, descriptive graphics show
the differences are right skewed. Thus they are not excellent candidates for testing either with a one-sample t test or a one-sample nonparametric Wilcoxon signed=rank test. (But, for the record,
both tests do reject that the differences are centered at $0$, the Wicoxon test with
a warning about ties.)
ad.obs = mean(dif); ad.obs
[1] 1.666667


R code for figure:
par(mfrow = c(1,3))
 hist(dif, prob=T, col="skyblue2"); rug(dif)
 boxplot(dif, col="skyblue2")
 qqnorm(dif, pch=19); qqline(dif, col="green2", lwd=2)
par(mfrow = c(1,1))

A one-sided permutation test that averages the differences after randomly switching the 24
signs shows a significant difference with P-value about $1.5\%,$
set.seed(2022)
ad.prm = replicate(5000, mean(dif*sample(c(-1,1),24,rep=T)))
mean(ad.prm > mean(dif))
[1] 0.0142  #  P-value of simulated permutation test


hist(ad.prm, prob=T, br=30, col="skyblue2")
 abline(v=ad.obs, col="red", lwd=2, lty="dotted")
length(unique(ad.prm))
[1] 3838

Two additional runs with different seeds and different numbers of permuted means
give essentially the same result.
set.seed(1776)
ad.prm = replicate(10^5, mean(dif*sample(c(-1,1),24,rep=T)))
mean(ad.prm > mean(dif))
[1] 0.01146

length(unique(ad.prm))
[1] 15437

set.seed(14)
ad.prm = replicate(5000, mean(dif*sample(c(-1,1),24,rep=T)))
[1] 0.0122
length(unique(ad.prm))
[1] 3827

Note: Here is R code used to sample the fictitious differences used above.
set.seed(426)
dif = round(rexp(24,1/5)-rexp(24, 1/2), 2)

