Source-linked AI summary
Permutation p-values should never be zero: calculating exact p-values when permutations are randomly drawn
Belinda Phipson, Gordon K. Smyth
TL;DR
Genomic analyses often treat randomly drawn permutation and Monte Carlo results as estimated p-values, despite systematic understatement and risks for multiple testing. The paper develops exact calculations for the discrete null distribution generated by random permutations and recommends exact p-values because they ensure valid tests regardless of sample size or permutation count.
Problem
Published permutation and Monte Carlo p-values are often treated as estimators rather than exact probabilities, with permutation p-values understated by about 1/m.
Method
The paper develops a computational strategy for evaluating exact p-values when permutations are randomly drawn.
Results
Exact p-values ensure a valid statistical test regardless of sample size or the number of permutations, whereas unbiased estimators can increase type I error.
Takeaways & Limitations
The authors recommend using exact p-values rather than unbiased estimators because valid p-values are readily available at little or no additional computational cost.
Takeaways & Limitations
Permutation assumes that the permuted items are statistically independent, so the authors generally recommend permuting samples rather than genes when possible.
Abstract
from arXiv · showhide
Permutation tests are amongst the most commonly used statistical tools in modern genomic research, a process by which p-values are attached to a test statistic by randomly permuting the sample or gene labels. Yet permutation p-values published in the genomic literature are often computed incorrectly, understated by about 1/m, where m is the number of permutations. The same is often true in the more general situation when Monte Carlo simulation is used to assign p-values. Although the p-value understatement is usually small in absolute terms, the implications can be serious in a multiple testing context. The understatement arises from the intuitive but mistaken idea of using permutation to estimate the tail probability of the test statistic. We argue instead that permutation should be viewed as generating an exact discrete null distribution. The relevant literature, some of which is likely to have been relatively inaccessible to the genomic community, is reviewed and summarized. A computation strategy is developed for exact p-values when permutations are randomly drawn. The strategy is valid for any number of permutations and samples. Some simple recommendations are made for the implementation of permutation tests in practice.
1 Introduction
Permutation tests are attractive because they require few assumptions, but genomic practice often treats randomly drawn permutations as estimating p-values rather than generating an exact discrete null distribution. This article identifies the resulting understatement and develops a computational solution for exact p-values.
- Permutation tests: Permutation tests estimate a test statistic’s null distribution by randomly permuting class labels, requiring only independent, identically distributed observations under the null.They are useful when standard distributional assumptions are doubtful or the null distribution is intractable.
- The problem: Bootstrap and resampling practice helped promote treating p-values as estimable quantities, despite earlier randomization-test expressions for exact p-values.The article argues that increasing the number of permutations does not by itself justify replacing exact probabilities with estimators.
- Genomic practice: Randomly drawn permutations have become common in genomic research, where many published software tools return estimated rather than exact p-values.The authors were motivated by repeated incorrect calculations in the genomic literature.
- The problem: Published permutation p-values are often understated by about 1/m, where m is the number of permutations, and some software returns values exactly equal to zero.The same issue arises when Monte Carlo simulation assigns p-values.
- Contribution: The article provides a computational solution for evaluating exact p-values when permutations are drawn at random and aims to make the relevant results accessible to genomic researchers.Its novel statistical theory is described as modest.
2 Estimating p-values tends to increase the type I error rate
Replacing an unknown null tail probability with an unbiased Monte Carlo estimator can make the resulting test reject too often. The paper therefore treats p-values as discrete probabilities requiring size-aware calculation rather than ordinary parameter estimation.
- Why estimation fails: Replacing the null tail probability p∞ with an unbiased estimator p̂ can produce P(p̂ ≤ α) > α because estimation variability creates small estimates when p∞ > α.Thus unbiasedness does not preserve the intended test size.
- Monte Carlo estimator: For m Monte Carlo data sets, p̂ = B/m, where B counts simulated statistics at least as extreme as the observed statistic, and p̂ is an unbiased estimator of p∞.Conditional on the observed data, m p̂ follows a binomial distribution with success probability p∞.
- Discrete null behavior: Unconditionally, p̂ has a discrete uniform distribution on 0, 1/m, 2/m, ..., 1.This follows because the conditional binomial distribution is averaged over a uniform null p-value.
- Type I error: The type I error rate P(p̂ ≤ α) exceeds α for most practical small α values and is never less than 1/(m+1), regardless of how stringent α is.It always exceeds α when α = i/m or when α < 1/(m+1).
- Implication: P-values must be evaluated directly as probabilities, because substituting an unbiased estimator generally yields a randomized test with the wrong size.The paper states that a positively biased estimator is needed to achieve the correct randomized-test size.
3 Under-estimating p-values is dangerous in a multiple testing context
Small systematic p-value underestimation can become consequential when thousands of hypotheses are tested together. The paper links this risk to relative error in the smallest p-values, including estimates that incorrectly become zero.
- Family-wise consequences: In large genomic multiple-testing analyses, systematic p-value underestimation can produce dangerously wrong family-wise conclusions even when individual errors are slight.The paper considers settings such as 50,000 transcript-level tests with Bonferroni or Holm adjustment.
- Figure A: Figure A plots actual type I error rate P(p̂ ≤ α) against nominal α for m = 20, with the equality line shown in blue.The plotted rate is generally above nominal for α < 0.5.
- Genomic example: For 30,000 genes analyzed with m = 1000 sample permutations each, the working value p̂ = B/m estimates the tail probability but can misrepresent extreme significance.The example assumes the total number of distinct permutations greatly exceeds 1000.
- Mechanism: Family-wise error depends on relative rather than additive p-value accuracy, so treating a nonzero p-value as zero creates 100% relative error.This is especially consequential for the smallest p-values.
4 Exact p-values for Monte Carlo tests
Monte Carlo tests use simulated null datasets to approximate an unavailable ideal p-value, but the unbiased tail-count estimator can yield invalid test sizes. The exact approach instead evaluates the discrete tail probability of the simulation result.
- Monte Carlo tests simulate m independent null datasets and compare their test statistics with the observed statistic.The ideal p-value would require infinitely many simulated datasets, but only a finite number m is available.
- The estimator B/m is unbiased for the unknown tail probability but does not correctly control the type I error rate.Here B counts simulated statistics at least as extreme as the observed statistic.
- The exact Monte Carlo p-value is obtained by evaluating the tail probability of the discrete count B rather than substituting B/m for the unknown tail probability.This approach accounts for the sampling uncertainty in the finite simulation.
- The correction replaces the unknown tail probability with (b + 1)/(m + 1), adding just enough positive bias to achieve the correct test size.The corrected value is a probability from the randomization distribution, not an unbiased parameter estimate.
5 Sampling permutations without replacement
Permutation tests assess group association by comparing the observed statistic with statistics generated by relabeling observations. When a random subset of distinct permutations is sampled without replacement, the exact p-value has the same form as in Monte Carlo testing.
- Permutation tests randomly relabel group assignments and compare the observed test statistic with statistics from the permuted data.The null hypothesis is that observations are identically distributed across groups.
- Complete enumeration may be impractical because the number of possible distinct statistic values can be very large.The paper distinguishes sampling permutations without replacement from sampling with replacement.
- For m distinct permutations sampled without replacement, the exact p-value is pu = (b + 1)/(m + 1), where b counts permuted statistics greater than tobs.This requires m ≤ mt and distinct statistics different from the original statistic.
- The same result includes exhaustive testing: pt = (bt + 1)/(mt + 1), where bt counts all distinct statistic values exceeding tobs.Exhaustive enumeration is the limiting case of the without-replacement procedure.
6 Sampling permutations with replacement
With-replacement permutation sampling requires an exact conditional calculation because repeated permutations and inclusion of the observed configuration alter the null distribution. The resulting exact p-value is below the conservative without-replacement bound and can be approximated numerically.
- 6 Sampling permutations with replacement: With replacement, independently drawn permutations may repeat and may include the original observed configuration.These possibilities make the exact calculation different from sampling distinct permutations without replacement.
- 6.1 Exact p-values: The exact p-value is pe = P(B ≤ b), where B counts sampled statistics at least as extreme as tobs.The calculation is performed conditionally on the unknown number of possible statistic values exceeding tobs.
- 6.1 Exact p-values: Conditional on Bt = bt, B is binomial with size m and probability pt, while Bt is discrete uniform under the null.The exact expression uses the binomial cumulative probability function.
- 6.2 Computation and approximation: The exact p-value satisfies pe < pu = (b + 1)/(m + 1) and converges to pu as mt increases.The integral approximation can be evaluated numerically, including with Gaussian quadrature.
- 6.2 Computation and approximation: When mt = 1000, pu over-estimates the 0.05 p-value by about 2%, while smaller p-values are over-estimated by greater relative amounts.For small mt, the conservative bound can be substantially more conservative.
- 6.3 Specific scenarios: The number mt depends on the test statistic and sample sizes because different permutations can produce identical statistic values.Equal-sized groups and two-sided statistics are examples where duplicate statistic values can arise.
- 6.3 Specific scenarios: For a one-sided test with n1 = n2 = 5, the number of distinct permutation statistics is mt + 1 = 252.The cited passage also reports that the integral approximation is excellent for the exact p-values in Table 1.
- 6.3 Specific scenarios: Figure 1 compares pu with the exact p-value across b for mt = 126 and mt = 1000, using m = 1000 permutations.The comparison shows how conservativeness depends on the number of possible distinct statistic values.
7 Discussion and recommendations
The authors recommend exact permutation p-values and favor sampling without replacement, while emphasizing that sample permutation is generally preferable to gene permutation. They also distinguish validity from power: exact methods preserve type I error control, whereas small permutation counts mainly reduce power.
- Sampling without replacement is difficult to implement but yields an exact p-value and more statistical power than sampling with replacement.The authors recommend improved algorithms for this approach.
- “Unbiased” p-value estimators should not replace exact p-values because they are not guaranteed to control the type I error rate.The authors note that the risk may be modest in many applications, but valid alternatives are available without extra cost.
- The exact p-value pe requires only trivial extra computation and can improve power when m is a non-negligible fraction of mt.
- Using pe ensures a valid test regardless of sample size or permutation count; choosing m small then costs power rather than validity.More permutations should generally provide greater power.
- Gene permutation can make pu a good approximation to pe because mt is enormous, but gene dependence makes sample permutation preferable when possible.
- Alternatives to permutation can alleviate small-mt problems when the number of samples is not large.