Source-linked AI summary
Exact testing with random permutations
Jesse Hemerik, Jelle Goeman
TL;DR
Random permutations reduce the computational burden of permutation testing, but their exactness and assumptions have received limited treatment. The paper gives a conditional Monte Carlo proof strategy and extensions, establishing validity under group-based conditions and supporting applications to multiple-testing procedures.
Problem
Using the full permutation group can be computationally infeasible, while the validity assumptions for tests using random permutations have remained unclear.
Source: §1 · p. 2Method
The paper views random-permutation testing as a conditional Monte Carlo test and extends results under a group structure, with the identity transformation included.
Source: §3.1 · p. 9, §3.3 · p. 11Results
With the identity included, the random-permutation test has rejection probability at most α under the null, and suitable conditions yield exactness.
Source: §3.3 · pp. 11, 13Takeaways & Limitations
The results can be used to prove properties of multiple-testing procedures based on random permutations.
Source: §1 · p. 3Unbiasedness and consistency do not generally hold for random-permutation tests, though they may be proved in specific scenarios.
Source: Discussion · p. 17
Abstract
from arXiv · showhide
When permutation methods are used in practice, often a limited number of random permutations are used to decrease the computational burden. However, most theoretical literature assumes that the whole permutation group is used, and methods based on random permutations tend to be seen as approximate. There exists a very limited amount of literature on exact testing with random permutations and only recently a thorough proof of exactness was given. In this paper we provide an alternative proof, viewing the test as a "conditional Monte Carlo test" as it has been called in the literature. We also provide extensions of the result. Importantly, our results can be used to prove properties of various multiple testing procedures based on random permutations.
1 Introduction
Using the full permutation group can be computationally infeasible, so random permutations are often used, but their p-values are commonly treated as estimates. This paper clarifies the assumptions needed for exact random-permutation tests and develops results relevant to multiple testing.
1 Introduction
- Using all permutations can be infeasible, and random-permutation p-values are often treated as estimates of full-group p-values.Naive use of random permutations can also produce extreme anti-conservativeness.Source: §1 · p. 2
- The exactness argument for random permutations remained incomplete because it did not establish which assumptions, such as group structure, ensure validity.Permutation samples come from a conditional null distribution, unlike Monte Carlo draws from the null distribution.Source: §1 · p. 2
- The paper extends work on random transformations to study fundamental properties of random permutation tests, focusing mainly on test level.Other properties, including consistency, may be established in more specific scenarios.Source: §1 · pp. 2–3
- The results can be used to prove properties of multiple-testing procedures based on random permutations, and the paper gives both conditioning-based and direct proofs.The paper also reviews fixed-group results and distinguishes permutation tests from Monte Carlo tests.Source: §1 · p. 3
2 Fixed transformations
For fixed transformations, the paper establishes level control under a group-structure assumption and describes when exactness is attainable. It also explains how ties, non-group transformation sets, and the null distribution affect test behavior and p-value interpretation.
2.1 Basic permutation test
- A finite transformation set must form a group—containing identity and inverses and closed under composition—so that its transformed sets are permutation-invariant.The group assumption is fundamental throughout the paper.Source: §2.1 · p. 3
- Under composite null hypotheses, properties such as unbiasedness and consistency do not generally hold, though they may be established for specific scenarios.The paper's fixed-group results may be extended to random permutations for more specific settings.Source: §2.1 · p. 4
- The basic fixed-group permutation test has level at most α, but can be conservative when ties occur.Discrete data often produce ties.Source: §2.1 · pp. 4–5
- Under Condition 1, the test of Theorem 1 is exact if and only if α ∈ {0, 1/m, ..., (m − 1)/m}, with m equal-size sets in the partition.Source: §2.1 · pp. 5–6
- Discrete data often fail Condition 1, and even when it holds, α = 0.05 may not lie on the exactness grid; boundary randomization guarantees exactness but reduces reproducibility.The randomized test can depend on a random decision.Source: §2.1 · pp. 5–6
- If the transformation set is not a group, the test can be highly anti-conservative or conservative; balanced permutations are one non-subgroup example.The cited discussion warns that balanced permutations can lead to anti-conservative tests.Source: §2.1 · p. 7
2.2 Permutation p-values
- A permutation statistic should not automatically be interpreted as a null-distribution quantile, because the null may not specify a unique data distribution.A strict p-value may therefore not exist; a weak p-value is a random variable p satisfying P(p ≤ c) ≤ c under every null distribution.Source: §2.2 · pp. 7–8
3 Random transformations
Section 3 separates estimation from exact testing with random transformations, then develops validity results using group structure and conditional Monte Carlo reasoning.
3.1 Comparison of Monte Carlo and permutation tests
- Unlike independent Monte Carlo null draws, random-permuted datasets are dependent under the null; group structure makes them iid conditionally on the orbit.This conditional structure motivates viewing the procedure as a conditional Monte Carlo test.Source: §3.1 · pp. 8–9
3.2 Estimated p-values
- The estimate B/w is unbiased but can be anti-conservative, especially with small cutoffs such as those from Bonferroni correction.For fixed w, the probability that B/w falls below a small cutoff need not vanish as the cutoff decreases.Source: §3.2 · p. 10
3.3 Random permutation tests
- With the identity included, group-based random-permutation tests have rejection probability at most α under Hp.Transformations may be sampled with replacement from G or without replacement from G excluding the identity.Source: §3.3 · p. 11
- Without replacement from distinct equivalence classes, the test is exact for α in {0/w, 1/w, ..., (w−1)/w}, under condition 1.The result also holds with replacement from the specified representatives under condition 1.Source: §3.3 · p. 12
- A tie-randomized rejection rule—reject above the cutoff and reject with probability a at the cutoff—has rejection probability exactly α under Hp.The adaptation can be unnecessary when the without-replacement test is already exact under Proposition 2.Source: §3.3 · pp. 13–14
- A finite subset of transformations can yield a test with rejection probability at most α, even when the ambient group is infinite.When the finite subset is itself a group, the test is non-random and coincides with the basic permutation test.Source: §3.3 · pp. 14–15
3.4 p-values based on random transformations
- The randomized p-value is exactly uniform under Hp, and p′ ≤ α exactly when the corresponding randomized test rejects.The test randomizes its decision at the boundary case.Source: §3.4 · pp. 15–16
- For independent uniform random transformations, (B+1)/(w+1) is a weak p-value, not exactly uniform, but approximates p′ with large w and few ties.The paper states the weak-p-value result for random permutations drawn with replacement or, under the stated alternative, without replacement.Source: §3.3 · p. 12, §3.4 · p. 16
4 Applications
The applications show how the results support exact random-permutation procedures in multiple testing and settings with general data spaces and transformation groups. They also allow a limited number of transformations while retaining exactness.
4 Applications
- The results apply to arbitrary data spaces and transformation groups, including functional data settings.The paper cites functional data analysis as an example and notes Cox and Lee (2008) use permutation testing with such data.Source: §4 · p. 16
- Hemerik and Goeman (2017) used theorem 2 to construct a confidence interval around SAM's estimate of the false discovery proportion.SAM is a permutation-based multiple-testing method that estimates the fraction of false positives among rejected hypotheses.Source: §4 · p. 16
- Adding the identity permutation can make Meinshausen's (2006) simultaneous confidence bounds for the false discovery proportion exact.The method constructs a multidimensional quantile across l hypotheses; the paper notes that id should be added to the random permutations.Source: §4 · p. 17
- The method permits limited transformations, such as 100, in computationally intensive closed testing while retaining exactness.Goeman and Solari (2011) suggest combining Meinshausen (2006) with closed testing; the paper allows a limited number of transformations in that setting.Source: §4 · p. 17
Discussion
The results establish properties of random-permutation tests in a general setting, but some properties require more specific scenarios. They may also inform multiple-testing procedures that use the permutation-test principle.
Discussion
- Unbiasedness for composite null hypotheses and consistency do not hold in general, but may be established for specific scenarios.Results for fixed permutations may be extended to random permutations.Source: Discussion · p. 17
- Properties established for fixed permutations may provide a route to results for random permutations in specific scenarios.The paper points to prior results by Hoeffding (1952), Lehmann and Romano (2005), and Pesarin and Salmaso (2010, 2013).Source: Discussion · p. 17
- The results may help analyze permutation-based multiple-testing methods built on the principle behind the permutation test.Westfall and Young (1993) is one example of such a method.Source: Discussion · p. 17