📊 statistics

Minimally Discrete and Minimally Randomized p-Values

This paper introduces and analyzes "minimally discrete" and "minimally randomized" p-values, demonstrating that these refined constructions dominate traditional natural, mid, and randomized p-values by reducing conservativeness and auxiliary variation while maintaining validity, thereby offering more efficient inputs for meta-analysis and multiple testing methods.

Original authors: Joshua Habiger, Pratyaydipta Rudra

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joshua Habiger, Pratyaydipta Rudra

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

Imagine you are a judge presiding over a trial. Your job is to decide if a defendant (the "Null Hypothesis") is innocent or guilty based on the evidence presented. In statistics, this evidence is summarized into a single number called a p-value.

The Rule: If the p-value is very small (like 0.01), it means the evidence is so strong against the defendant that you reject the "innocent" assumption and declare them guilty.
The Ideal: In a perfect world, if the defendant is actually innocent, the p-value should be like a roll of a fair 100-sided die. It could be any number between 0 and 1 with equal chance. This makes it easy to set a fair rule: "If the number is below 5, we convict."

The Problem: The "Staircase" Effect

The paper tackles a specific problem: What happens when the evidence isn't smooth and continuous, but comes in discrete chunks?

Think of a smooth ramp versus a staircase.

Continuous Data (The Ramp): You can slide down to any point. If you need to stop exactly at the 5% mark, you can do it perfectly.
Discrete Data (The Staircase): You can only stand on the steps. You can't stand between steps.

In the real world, many things are like stairs (e.g., counting the number of heads in 5 coin flips, or the number of defective items in a batch). You can't have 4.5 defective items.

When statisticians try to apply the "fair rule" (the 5% cutoff) to a staircase, they hit a wall.

If they set the rule at "Step 4," they might convict too often (too many false alarms).
If they set it at "Step 5," they might convict too rarely (letting guilty people go free).

To fix this, statisticians have developed three "workarounds" to make the staircase act more like a ramp:

Natural p-values: The "Safe" approach. It's very conservative. It's like saying, "I'll only convict if you are definitely on the step below the line." This is safe, but it lets too many guilty people go.
Mid-p-values: The "Compromise." It splits the difference. "If you are on the line, I'll convict half the time." This is better, but still has some wiggle room.
Randomized p-values: The "Coin Flip." If you land on the tricky step, I flip a coin. Heads = Convict, Tails = Innocent. This makes the math perfect (uniformly distributed), but it introduces chaos. If you run the same experiment again, you might get a different result just because the coin landed differently. This makes the results hard to replicate.

The Solution: "Minimally" Discrete and "Minimally" Randomized

The authors, Joshua Habiger and Pratyadipta Rudra, say: "We can do better."

They argue that when we have to deal with these "staircases," we don't have to be as clumsy as the current methods. We can be minimalist.

1. Minimally Discrete (MD) p-values

The Analogy: Imagine you have a bag of marbles of different colors.

Old Way: You group all the "Red" marbles together and treat them as one big lump. If you need to pick 50% of the red marbles, you have to guess or be very conservative.
New Way (MD): You realize that even though the marbles are all "Red," they are actually distinct individuals. You line them up in a specific order (Rank 1, Rank 2, Rank 3...).
The Result: Instead of treating the whole group as a single block, you pick the exact number of individuals you need to reach your 5% limit.
Why it's better: It's less "chunky." It uses the data's natural order to be more precise. It's still safe (you won't convict an innocent person too often), but it's more powerful (you catch more guilty people) because you aren't throwing away information by grouping things too broadly.

2. Minimally Randomized (MR) p-values

The Analogy: Imagine you are playing a game where you need to flip a coin to decide a winner, but you want the game to be fair.

Old Way: You flip a coin for every single person who lands on the tricky step. This creates a lot of noise. If you replay the game, the winners change wildly just because of the coin flips.
New Way (MR): You realize you only need to flip the coin for the absolute minimum number of people necessary to make the math work.
The Result: You still use the coin flip to make the math perfect, but you flip it far less often.
Why it's better: The results are much more stable. If you run the experiment again, you get the same answer more often. It reduces the "noise" added by the randomness.

Why Should You Care?

The paper is essentially a guide on how to be a smarter statistician when dealing with "chunky" data.

For Scientists: If you are testing a new drug or a new policy, using these "Minimally" methods means you are less likely to miss a real effect (higher power) and your results are more likely to be reproducible (less random noise).
For Meta-Analysis: When many scientists combine their studies (like a giant group project), using these better p-values makes the final conclusion more accurate. It's like combining high-resolution photos instead of blurry ones.

The Big Takeaway

The authors are saying: "Just because your data comes in steps doesn't mean you have to be clumsy about it."

By carefully ordering the data (Minimally Discrete) and only using randomness when absolutely necessary (Minimally Randomized), we can get the best of both worlds: Statistical safety (we don't lie about innocence) and Statistical power (we don't miss the truth).

It's the difference between using a sledgehammer to crack a nut (the old, conservative ways) and using a precision screwdriver (the new, minimal ways). You still get the job done, but you do it with less force and more precision.

1. Problem Statement

In statistical hypothesis testing, $p$ -values are standard inputs for downstream methods such as meta-analysis and multiple hypothesis testing (MHT). These methods typically assume that under the null hypothesis ( $H_0$ ), $p$ -values follow a uniform distribution on $[0, 1]$ .

However, when data $X$ follows a discrete distribution (e.g., count data, contingency tables), it is generally impossible to construct a test with an exact size $\alpha$ (i.e., $E_0[\delta(X)] = \alpha$ ) without randomization. This leads to three common approaches, each with drawbacks:

Natural $p$ -values: Defined as $P(X, 1) = \Pr_0(T(X) \geq T(x))$ . These are valid (conservative) but stochastically larger than uniform, leading to a loss of power in downstream methods.
Mid- $p$ -values: Defined as $P(X, 1/2) = \Pr_0(T(X) > T(x)) + 0.5\Pr_0(T(X) = T(x))$ . These are less conservative but are only "sub-uniform" in the convex order, meaning inequalities used in downstream analysis (like Fisher's method) are not sharp.
Randomized $p$ -values: Defined using an auxiliary uniform variable $U$ , $P(X, U)$ . These are exactly uniform under $H_0$ but introduce extraneous variation (noise) because the $p$ -value depends on the realization of $U$ . This reduces replicability (the same data can yield different $p$ -values in repeated experiments).

The core problem is that existing methods either sacrifice power (conservatism) or introduce unnecessary variability (randomization noise) due to the "discreteness effect."

2. Methodology

The authors propose a framework based on minimality principles to construct "optimal" $p$ -values that mitigate these issues.

Key Definitions

Minimally Discrete (MD) Test Functions: Instead of grouping all outcomes with the same test statistic value $T(x)$ $T (x)$ together (which creates large "ties" in discrete distributions), the authors propose ranking individual data points $x \in \mathcal{X}$ $x \in X$ via a one-to-one mapping $R: \mathcal{X} \to \mathbb{N}$ $R : X \to N$ .
- An MD test function $\phi^{MD}_\alpha$ rejects $H_0$ for the "most extreme" individual points first, only randomizing at the very last point needed to achieve size $\alpha$ .
- This contrasts with standard tests (like Likelihood Ratio Tests) which randomize over the entire set of points where $T(x) = k$ .
Minimally Discrete $p$ -values (MD-T): Natural or mid- $p$ -values constructed using the MD test function $R$ rather than the standard statistic $T$ .
Minimally Randomized (MR) $p$ -values (MR-T): Randomized $p$ -values constructed using the MD test function.

Theoretical Framework

The paper utilizes stochastic ordering and convex ordering (Shaked and Shanthikumar, 2007) to compare these new $p$ -values against their traditional counterparts.

Stochastic Order ( $\leq_{st}$ ): $X \leq_{st} Y$ if $F_X(t) \geq F_Y(t)$ for all $t$ .
Convex Order ( $\leq_{cx}$ ): $X \leq_{cx} Y$ if $E[h(X)] \leq E[h(Y)]$ for all convex functions $h$ .

The authors define conditions where a test statistic $T$ and a ranking $R$ "agree" (i.e., $T(x) \geq T(y) \implies R(x) \leq R(y)$ ), ensuring the new $p$ -values respect the evidence provided by the original test.

3. Key Contributions and Results

The paper establishes that MD and MR $p$ -values dominate their traditional counterparts in specific orders, leading to sharper bounds and more efficient inference.

A. Minimally Discrete (MD) Natural $p$ -values

Result: MD natural $p$ -values are stochastically smaller than (dominate) standard natural $p$ -values.
Implication: They are still valid (stochastically larger than or equal to Uniform) but are less conservative. This translates to higher power for downstream decision rules (e.g., in MHT) while maintaining Type I error control.
Theorem 1: Proves that for any $\alpha$ and $\theta$ , the power of the MD decision rule is greater than or equal to the standard rule, and the Type I error remains $\leq \alpha$ .

B. Minimally Discrete (MD) Mid- $p$ -values

Result: MD mid- $p$ -values dominate standard mid- $p$ -values in the convex order.
Implication: Since many downstream methods (like Fisher's method for meta-analysis) rely on convex inequalities (e.g., $E[-2\log(P)]$ ), using MD mid- $p$ -values provides sharper bounds. The distribution of the MD mid- $p$ -value is "closer" to the uniform distribution than the standard mid- $p$ -value.
Theorem 3: Shows that for any convex function $h$ , $E[h(P^{MD})] \leq E[h(P^{standard})] \leq E[h(U)]$ . This tightens the inequalities used to prove validity in meta-analysis.

C. Minimally Randomized (MR) $p$ -values

Result: MR $p$ -values maintain the exact uniform distribution under $H_0$ (like standard randomized $p$ -values) but exhibit lower variance attributable to the auxiliary variable $U$ .
Implication: The "noise" introduced by randomization is minimized. If the test statistic $T$ is sufficient, the MR $p$ -value has the same distribution as the standard randomized $p$ -value, but the conditional variance given the data is smaller.
Theorem 2: Proves that $Var(P^{MR}(X, U) | X) \leq Var(P^{standard}(X, U) | X)$ . This improves replicability, as the $p$ -value is less sensitive to the specific realization of the random number generator.

4. Significance and Applications

Meta-Analysis: The paper demonstrates that using MD mid- $p$ -values in Fisher's method ( $T = -2 \sum \log P_i$ ) yields sharper bounds on the distribution of the test statistic under the global null. This reduces the conservativeness of existing meta-analysis methods for discrete data.
Multiple Hypothesis Testing (MHT): For procedures like Benjamini-Hochberg (FDR control), using MD natural $p$ -values allows for more powerful detection of true positives without violating Type I error constraints, as the $p$ -values are stochastically smaller (more extreme) than standard conservative $p$ -values.
E-values and Bayes Factors: The results facilitate the conversion of mid- $p$ -values to valid E-values (Vovk and Wang, 2021) and Bayes Factors with tighter bounds, improving the efficiency of these tools.
Theoretical "Gold Standard": The paper establishes a new benchmark for handling discrete data. It argues that the "discreteness effect" is not a fixed limitation but can be minimized by carefully choosing how ties are broken (ranking) in the construction of the test function.

5. Conclusion

Habiger and Rudra demonstrate that the non-uniqueness of most powerful tests in discrete settings is not a bug but a feature that can be exploited. By constructing Minimally Discrete and Minimally Randomized $p$ -values, researchers can achieve:

Higher Power (less conservativeness) for natural/mid- $p$ -values.
Sharper Inequalities for convex-order-based methods (meta-analysis).
Reduced Variance and improved replicability for randomized methods.

The work provides a rigorous theoretical foundation for constructing more efficient statistical procedures for discrete data, moving beyond the traditional trade-off between validity and power.