📊 statistics

Sharp Lower Bound on the Minimax Risk for Multinomial Uniformity Testing via a Conditional Central Limit Theorem

This paper establishes a sharp lower bound on the minimax risk for multinomial uniformity testing in the intermediate regime by proving a conditional central limit theorem for weighted sums, thereby providing an exact constant characterization that matches existing upper bounds.

Original authors: Alon Kipnis

Published 2026-07-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alon Kipnis

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 detective trying to solve a mystery in a massive, crowded room.

The Setup: The Uniform Room vs. The Tilted Room
You have a room with $N$ different colored bins (categories). You are told that someone is dropping $n$ marbles into these bins.

The "Uniform" Story (Hypothesis 0): The person is dropping marbles completely at random. Every bin has an equal chance of catching a marble. It's a perfectly fair game.
The "Tilted" Story (Hypothesis 1): The person is cheating. They are slightly favoring some bins over others. The distribution is no longer perfectly flat; it's "tilted."

Your job is to look at the final count of marbles in each bin and decide: Is this a fair game, or is someone cheating?

The Problem: The "Needle in a Haystack" Dilemma
The cheating is very subtle. The person isn't dumping a whole bucket into one bin; they are just nudging the odds slightly.

If you have very few marbles ( $n$ is small), you can't tell the difference. It looks like random noise.
If you have a huge number of bins ( $N$ is huge), the signal gets diluted.
The paper focuses on a "Goldilocks" zone: You have enough marbles and enough bins that the cheating is just barely detectable, but only if you use the perfect mathematical tool.

The Metric: The "Signal-to-Noise" Ratio
The author, Alon Kipnis, introduces a special ruler called the Signal-to-Noise Ratio (SNR), which he calls $u_n$ .

Think of the "Signal" as the tiny tilt in the bins caused by the cheater.
Think of the "Noise" as the natural randomness of marbles bouncing around.
If the Signal is huge compared to the Noise, you can easily spot the cheater.
If the Signal is tiny compared to the Noise, you will fail.
The paper looks at the specific moment where the Signal and Noise are balanced in a way that makes the answer neither "always yes" nor "always no," but a specific probability (like a coin flip that is slightly weighted).

The Big Discovery: The "Conditional Crystal Ball"
For a long time, mathematicians knew how to solve this problem if they could pretend the marbles were dropped in a slightly different way (called the "Poissonized" version). In that imaginary world, they knew the exact odds of catching the cheater.

But the real world (the "Multinomial" version) is trickier because the total number of marbles is fixed at exactly $n$ . You can't just add or remove marbles to make the math easier.

The Paper's Breakthrough:
Kipnis proves that the "Real World" answer is exactly the same as the "Imaginary World" answer.

To do this, he uses a clever mathematical trick he calls a "Conditional Central Limit Theorem."

The Analogy: Imagine you are trying to predict the average height of people in a room. Usually, you just measure everyone. But here, you are forced to only look at people who fit through a specific doorway (conditioning on the total count).
Kipnis shows that even with this strict door constraint, the math behaves beautifully. The "noise" of the marble counts, when you look at the right combination of weights, still forms a perfect, smooth bell curve (the Normal distribution).
Because it forms this perfect curve, he can calculate the exact probability of making a mistake.

The Result: The Perfect Score
The paper concludes that in this specific "Goldilocks" zone, the best possible detective (the minimax risk) will get the answer right with a probability determined by a famous mathematical curve (the Gaussian function, $\Phi$ ).

Specifically, the risk of making a mistake is exactly $2\Phi(-u^*/2)$ .

If the signal is strong ( $u^*$ is large), this number is tiny (you almost never make a mistake).
If the signal is weak ( $u^*$ is small), this number is large (you are guessing).
Most importantly, this paper proves that you cannot do any better than this. It is the sharp lower bound. No other method, no matter how clever, can beat this score.

In Summary
This paper is about proving that when you are trying to detect a very subtle bias in a large set of random data, there is a hard limit to how well you can do. The author proves that this limit is exactly the same as a slightly simpler, theoretical version of the problem, using a sophisticated mathematical lens (the Conditional Central Limit Theorem) to show that the "real world" constraints don't actually make the problem harder than the "theoretical" one.

Technical Summary: Sharp Lower Bound on the Minimax Risk for Multinomial Uniformity Testing via a Conditional Central Limit Theorem

Problem Setup
This paper addresses the minimax goodness-of-fit testing problem for uniformity based on $n$ independent observations from a multinomial distribution over $N$ categories. The null hypothesis $H_0$ posits that the underlying distribution $q$ is uniform ( $q_{unif} = (1/N, \dots, 1/N)$ ). The alternative hypothesis $H_1$ consists of distributions $q$ that deviate from uniformity by at least $\epsilon$ in the $\ell_p$ norm, defined as $\|q - q_{unif}\|_p \ge \epsilon$ . The objective is to characterize the minimax risk $R^*$ , defined as the infimum over all tests $\psi$ of the sum of Type I and Type II errors.

The analysis focuses on an intermediate asymptotic regime where $n \to \infty$ , $N \to \infty$ , and $N = o(n^2)$ . In this regime, the signal-to-noise ratio (SNR) is defined as:
$u_n := \frac{\epsilon^2 n N^{3/2 - 2/p}}{\sqrt{2}}$
Previous literature established that if $u_n \to \infty$ , the risk vanishes, and if $u_n \to 0$ , the risk approaches 1. The critical case occurs when $u_n \to u^* \in (0, \infty)$ , where the minimax risk converges to a non-trivial constant. While a Poissonized version of this problem was recently shown to yield an upper bound of $2\Phi(-u^*/2)$ (Kipnis [2025]), the exact value for the multinomial setting remained an open question.

Methodology
The paper establishes the matching lower bound for the multinomial minimax risk through a sequence of technical steps involving Poissonization, Bayesian analysis, and a novel conditional limit theorem.

Reduction to Poisson Mixture Models: The authors utilize the equivalence between the multinomial distribution and a Poisson distribution conditioned on the total count $S_N = \sum O_i = n$ . By defining a Poisson mixture model where the rates $Q_i$ are random variables, the problem is transformed into a Bayesian setting. A specific "least favorable" prior $\pi^*$ is constructed, consisting of local two-sided perturbations of the uniform distribution.
Likelihood Ratio Approximation: The optimal test in the Poisson setting is a likelihood ratio test. The authors show that the exact likelihood ratio weights can be approximated by a simpler quadratic statistic $T(w^*) = \sum w^*_{O_i}$ , where $w^*_m \propto (m - n/N)^2 - m$ . This approximation is shown to preserve the asymptotic distribution of the test statistic.
Conditional Central Limit Theorem (C-CLT): The core technical contribution is Theorem 2.3, a conditional central limit theorem for weighted sums under a Poisson mixture prior, conditioned on the total count $S_N = n$ . The proof employs characteristic functions and an inversion formula for the lattice variable $S_N$ . It decomposes the Fourier integral into three regions (near zero, intermediate, and far) to demonstrate that the conditional distribution of the standardized statistic converges to a standard normal distribution, provided specific moment and correlation conditions are met.
De-Poissonization: By combining the C-CLT with the equivalence between the conditioned Poisson model and the multinomial model (Lemma 3.3), the authors transfer the risk bounds from the Poisson setting back to the original multinomial setting.

Key Results
The main result, Theorem 2.1, proves that under the assumptions $N = o(n^2)$ and $u_n \to u^* \in (0, \infty)$ , the minimax risk satisfies:
$\liminf_{n \to \infty} R^* \ge 2\Phi(-u^*/2)$
Combined with the existing upper bound from Kipnis [2025], this yields Corollary 2.2, providing an exact characterization of the asymptotic minimax risk:
$\lim_{n \to \infty} R^* = 2\Phi(-u^*/2)$
This result confirms that the Poissonized analysis provides the sharp constant for the multinomial problem in the intermediate regime.

Significance
The paper claims to provide the first exact sharp-constant characterization of the multinomial minimax risk for uniformity testing in the intermediate regime where the signal-to-noise ratio converges to a finite constant. By proving the matching lower bound, the work closes the gap left by previous upper bounds derived from Poissonized models. The significance lies in the rigorous justification that the "de-Poissonization" step does not alter the asymptotic risk constant, relying fundamentally on the newly established conditional central limit theorem for weighted sums. This resolves the precise behavior of the testing risk in a regime where the number of categories grows with the sample size but remains sub-quadratic.

More like this