Faster Exact Permutation Testing: Using a Representative Subgroup

Non-parametric tests based on permutation, rotation or sign-flipping are examples of so-called group-invariance tests. These tests rely on invariance of the null distribution under a set of transformations that has a group structure, in the algebraic sense. Such groups are often huge, which makes it computationally infeasible to use the entire group. Hence, it is standard practice to test using a randomly sampled set of transformations from the group. This random sample still needs to be substantial to obtain good power and replicability. We improve upon the standard practice by using a well-designed subgroup of transformations instead of a random sample. We show this can yield a more powerful and fully replicable test with the same number of transformations. For a normal location model and a particular design of the subgroup, we show that the power improvement is equivalent to the power difference between a Monte Carlo $Z$-test and Monte Carlo $t$-test. In our simulations, we find that we can obtain the same power as a test based on sampling with just half the number of transformations, or equivalently, more power for the same computation time. These benefits come entirely `for free', as our methodology relies on an assumption of invariance under the subgroup, which is implied by invariance under the entire group.