1
$\begingroup$

I have a question with regard to the number of permutations in a permutation test. Assume I want to do a two group independent t-test. In the permutation variant of the t-test, I would repeatedly generate permutations of the group labels [e.g., (1, 2, 1, 2, ..., 1) ] and compute a t statistic for each iteration.

Assume that I want to do an exhaustive permutation test where I generate all possible divisions of the sample into two groups. According to Ernst (2004), "[c]omputation of the permutation distribution of a test statistic involves careful enumeration of all $\binom{N}{n}$ divisions of the observations." Here, $N$ is the total sample size and $n$ is the size of one of the groups. According to Ernst (2004) -- and all other references I found on this topic -- creating all "divisions of the observations" is accomplished by generating all permutations of the group labels.

However, generating all permutations of the group labels will result in duplicate "divisions of the observations" if the two groups are of equal size. For example, the permutations $(1, 1, 2, 2)$ and $(2, 2, 1, 1)$ clearly correspond to the same division, but they represent different permutations of the group labels. Therefore, the number of unique division of the observations not given by the binomial coefficient, but you have to divide it by 2 (for $K$ equal-sized groups, you have to divide the number of permutations of the group labels by $K!$). Note that no duplicates occur if the groups are of different size.

This results in several questions on my part: Has this matter been treated in any reference (I did not find any)? Has this issue been overlooked completely so far? Or is there a sensible reason to generate duplicate divisions in the case of equal group sizes? (note that you do not do that when you have unequal group sizes, so in my opinion this would be weird)

Ernst, M. D. (2004). Permutation methods: a basis for exact inference. Statistical Science, 19, 676-685.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

No, there is no reason to generate duplicate divisions, except that they don't do a lot of harm and it is computationally expensive to avoid them. In practice, permutations are almost always drawn at random with replacement, see:

Phipson, B, and Smyth, GK (2010). Permutation p-values should never be zero: calculating exact p-values when permutations are randomly drawn. Statistical Applications in Genetics and Molecular Biology Volume 9, Issue 1, Article 39. https://arxiv.org/abs/1603.05766

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks a lot for your response! Indeed I have read your paper and I was wondering if my point may have any implications with regard to a point you raise, i.e., sampling permutations without replacement. When sampling without replacement, I thought it might make sense to sample unique sample divisions rather than permutations? I agree that in practice distinguishing between partitions and permutations rarely matters. $\endgroup$
    – M. Papenberg
    Dec 17, 2019 at 10:14
  • 1
    $\begingroup$ Yes, assuming you are computing a two-sided test and the two groups are of equal sizes, it is theoretically optimal to sample unique sample divisions (excluding the original division). This is optimal in the sense that it produces maximum statistical power for the test for any given number of divisions. The ideal is to use all possible unique divisions exactly once. $\endgroup$
    – Gordon Smyth
    Dec 17, 2019 at 10:55
  • $\begingroup$ your responses are very much appreciated! $\endgroup$
    – M. Papenberg
    Dec 17, 2019 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.