📊 statistics

More Permutations Do Not Always Increase Power: Non-monotonicity in Monte Carlo Permutation Tests

This paper demonstrates that increasing the number of sampled permutations in Monte Carlo permutation tests does not guarantee higher statistical power, as the test's power can non-monotonically decrease due to the discrete, saw-toothed structure of its underlying distribution.

Original authors: Suman Cha, Seongchan Lee, Antonin Schrab, Ilmun Kim

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Suman Cha, Seongchan Lee, Antonin Schrab, Ilmun Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Misconception: "More is Always Better"

Imagine you are a judge trying to decide if a coin is fair. You have a rule: if the coin lands on heads more than 95% of the time in a series of flips, you declare it "rigged."

In statistics, this is similar to a Permutation Test. Researchers shuffle data around thousands of times to see how often a specific result happens by pure luck. The standard advice has always been: "The more times you shuffle (sample), the better your test becomes."

The logic seemed simple: If you shuffle 10 times, you might get a rough guess. If you shuffle 10,000 times, your guess should be much closer to the truth. Therefore, increasing your "budget" of shuffles should always make your test more powerful (better at catching the truth).

This paper says: That intuition is wrong.

The authors prove that sometimes, adding more shuffles actually makes your test worse at detecting the truth. It's like adding more ingredients to a soup and accidentally making it taste worse.

The "Staircase" Problem

To understand why this happens, imagine a staircase where the steps are uneven.

The Goal: You want to catch a "bad" coin (the alternative hypothesis).
The Rule: You need to see a certain number of "extreme" results to say, "Aha! This is rigged!"
The Trap: The number of extreme results you need to catch is an integer (a whole number like 0, 1, 2, 3). You can't catch "1.5" bad results.

The paper explains that as you increase your shuffling budget ( $B$ ), the "cutoff line" for what counts as a win stays stuck on the same integer for a while, then suddenly jumps up.

The Plateau (The Trap): Imagine you need 3 bad results to win. You shuffle 100 times. The math says you need 3. You shuffle 101 times. The math still says you need 3.
- Because you are doing more shuffles but the target number (3) hasn't changed, it actually becomes harder to hit that target. You are spreading your "bad results" over a larger pool, making it statistically less likely to reach the specific count of 3.
- Result: Your power (ability to win) drops.
The Jump (The Relief): Eventually, you shuffle enough times that the math says, "Okay, now you need 4 bad results to win."
- Suddenly, the target moves up. Because the target moved, your chances of hitting it might actually improve compared to the previous step.
- Result: Your power jumps up.

This creates a "Sawtooth" pattern. As you add more shuffles, your test power goes up and down like a jagged saw blade, rather than smoothly climbing a hill.

The "Sawtooth" in Real Life

The authors call this a Sawtooth Structure.

The Teeth: The sharp drops in performance happen when you add more shuffles but the "winning number" stays the same.
The Gaps: The peaks happen right before the winning number jumps.

They prove mathematically that this doesn't just happen once; it happens infinitely often. No matter how many shuffles you do, if you keep adding them one by one, you will eventually hit a spot where adding one more shuffle makes your test weaker.

The Solution: "Alignment"

So, how do we fix this? The paper suggests a simple rule to avoid the "teeth" of the saw and land on the "peaks."

Think of it like tuning a radio. If you are slightly off-frequency, the sound is static. If you hit the exact frequency, the music is clear.

The authors recommend choosing your number of shuffles ( $B$ ) so that it fits perfectly with your significance level ( $\alpha$ , usually 0.05 or 5%).

The Rule: Choose $B$ so that $(B + 1) \times \alpha$ is a whole number.

If you follow this rule, you are guaranteed to be standing on a "local peak" of power. You aren't necessarily at the absolute highest possible power (that requires infinite shuffles), but you are at the best possible spot for that specific amount of computing power.

Summary of Key Takeaways

More isn't always better: Adding more random shuffles to a test doesn't guarantee a better result. Sometimes, it makes the test slightly less sensitive.
The Discrete Trap: Because statistical tests rely on whole numbers (you can't have half a rejection), the relationship between "how much work you do" and "how well you perform" is jagged, not smooth.
The Fix: Don't just pick a round number like 1,000 or 10,000 shuffles. Do the math to ensure your number of shuffles aligns perfectly with your error rate (e.g., for a 5% error rate, pick a number of shuffles where the math lines up perfectly).
Alternative: If you don't want to worry about this math, you can use a "randomized" version of the test (adding a little bit of extra randomness to the calculation) which smooths out the jagged edges, or use a "sequential" method that stops early if the answer is obvious.

In short: The paper warns statisticians that blindly increasing computing power can backfire due to the "jagged" nature of whole-number math. To get the best results, you need to be a careful architect of your experiment, not just a brute-force worker.

Technical Summary: Non-monotonicity in Monte Carlo Permutation Tests

Problem Statement
Monte Carlo permutation tests are a standard tool for model-free statistical inference, relying on the random sampling of $B$ permutations from a group $G$ to approximate an exact $p$ -value. A prevailing practical intuition suggests that increasing the Monte Carlo budget $B$ invariably improves test performance, specifically by increasing statistical power as the Monte Carlo $p$ -value concentrates around its exact counterpart. This paper challenges that intuition, demonstrating that the relationship between the number of sampled permutations $B$ and statistical power is not monotonic. Specifically, increasing $B$ can, under certain conditions, lead to a decrease in the probability of rejecting the null hypothesis under the alternative.

Methodology and Theoretical Framework
The authors analyze the structural properties of the Monte Carlo permutation test defined by the rejection rule $p_B(X) \leq \alpha$ , where:
$p_B(X) = \frac{1 + \sum_{i=1}^B \mathbb{1}\{T(X^{\pi_i}) \geq T(X)\}}{B + 1}$
The analysis hinges on the integer-valued critical count $k_B = \lfloor (B+1)\alpha \rfloor - 1$ . The rejection event is equivalent to the number of exceedances $R_B(X)$ being less than or equal to $k_B$ .

The core mechanism driving non-monotonicity is the discrete, step-wise nature of $k_B$ as a function of $B$ . The authors distinguish between two regimes in the evolution of $k_B$ :

Jumps: Indices where $k_B$ increases by 1 (occurring when $\lfloor (B+1)\alpha \rfloor = \lfloor B\alpha \rfloor + 1$ ).
Plateaus: Indices where $k_B$ remains constant as $B$ increases (occurring when $\lfloor (B+1)\alpha \rfloor = \lfloor B\alpha \rfloor$ ).

The paper introduces a non-degeneracy assumption: the conditional exceedance probability $q(X) = P(T(X^\pi) \geq T(X) \mid X)$ is not almost surely equal to 1. Under this assumption, the authors derive the unconditional power $\text{Pow}(B) = E[\phi_B(X)]$ , where $\phi_B(X)$ is the conditional rejection probability.

Key Contributions and Results

Proof of Non-monotonicity:
The paper proves that power is not a monotone non-decreasing function of $B$ . Specifically, when $B$ increases within a "plateau" (where $k_B$ is constant), the rejection rule compares an additional Bernoulli trial against the same fixed threshold. For datasets where $0 < q(X) < 1$ , this makes rejection strictly harder, causing the power to decrease.
Sawtooth Structure and Local Maxima:
The authors characterize the power curve as exhibiting a "sawtooth" pattern. They prove that strict local maxima in power occur at specific indices $B$ where a "jump" in the critical count is immediately followed by a "plateau."
- Theorem 1: If $k_B - k_{B-1} = 1$ and $k_{B+1} - k_B = 0$ , then $\text{Pow}(B)$ is a strict local maximum.
- Infinitely Many Maxima: The paper demonstrates that such jump–plateau patterns occur infinitely often as $B \to \infty$ , implying the power curve has infinitely many local maxima.
Alignment Condition:
A simple sufficient condition for a local maximum is $(B+1)\alpha \in \mathbb{N}$ . For common significance levels $\alpha \in \{0.1, 0.05, 0.01\}$ , which are of the form $1/m$ , this condition is not only sufficient but necessary to characterize the set of all strict local maxima.
Quantification of Power Loss:
Proposition 1 quantifies the magnitude of the downward steps in power. It shows that the decrease in power when moving from a jump index to a plateau index is of order $O(B^{-1/2})$ and provides a distribution-free upper bound for this decrease.
Concrete Illustration:
The authors provide a closed-form example using a two-sample Bernoulli problem. They demonstrate that while the Monte Carlo power converges to the exact power as $B \to \infty$ , the path of convergence is oscillatory. Depending on the parameters ( $n, p_1$ ), the Monte Carlo power can be either strictly below or strictly above the exact power for substantial ranges of $B$ , further illustrating that more permutations do not guarantee a "better" test at every step.

Significance and Practical Implications
The paper argues that non-monotonicity is not a pathological curiosity but a fundamental structural feature of Monte Carlo permutation tests arising from the discreteness of the rejection threshold. The authors clarify that this does not imply "more permutations are bad"; increasing $B$ still reduces simulation variability and refines the set of attainable $p$ -values. However, for the specific objective of maximizing power at a fixed level $\alpha$ , simply increasing $B$ is not a monotonic strategy.

The primary practical recommendation is a design rule: practitioners should choose $B$ such that $(B+1)\alpha \in \mathbb{N}$ . This alignment places the test at a local power maximum. Alternatively, the authors suggest using randomized $p$ -values to smooth the discreteness or employing sequential procedures that adaptively determine the number of permutations, rather than fixing $B$ arbitrarily. The work serves as a cautionary note against the unexamined assumption that larger Monte Carlo budgets always yield superior statistical power.