📊 statistics

Tight Sample Bounds for Renyi and Min-Entropy Estimation

This paper establishes tight sample complexity bounds for estimating min-entropy and Rényi entropy, proving that min-entropy requires $\Theta(k \log k)$ samples—correcting a previous characterization—and that Rényi entropy of order $\alpha$ requires $\Theta(\alpha k^{1-1/\alpha})$ samples, utilizing novel estimators and lower-bound constructions to resolve the dependence on both alphabet size and order.

Original authors: Arman Adibi, Piotr Krysta

Published 2026-07-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Arman Adibi, Piotr Krysta

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 figure out how "chaotic" a secret code is. In the world of information theory, this chaos is called entropy. Think of entropy as a measure of how hard it is to guess what will happen next. If you have a bag of marbles where every color is equally likely, the bag is very chaotic (high entropy); you have no idea which color you'll pull out. But if the bag is mostly red marbles with just one blue one, it's predictable (low entropy).

To solve this mystery, you don't need to see every single marble. You just need to pull out a few samples to get a good guess. The big question for scientists is: How many marbles do you need to pull to get a reliable answer? The answer changes depending on what kind of chaos you are measuring. Sometimes you just want to know the average chaos (like the average temperature of a room). Other times, you need to know the worst-case chaos (like the hottest spot in a fire, because that's where the danger lies). This paper dives deep into the math of counting those marbles to solve these different types of chaos puzzles.

The Mystery of the Hidden Heavy Hitter

In this paper, the authors tackle a specific puzzle: How many samples do we need to estimate "Min-Entropy"?

Min-entropy is the "worst-case" version of chaos. It doesn't care about the average; it only cares about the single most likely outcome. Imagine a lottery where one number is slightly more likely to win than the others. Min-entropy is all about spotting that one "heavy" number. If you miss it, your prediction of the lottery is useless.

For a long time, some researchers thought estimating this "heavy number" was just as easy as estimating the average chaos. They guessed you only needed about $k / \log k$ samples (where $k$ is the total number of possible outcomes). But the authors of this paper say: "Nope, that's wrong."

They prove that finding that one heavy number is actually much harder. You need $\Theta(k \log k)$ samples. That's a factor of $\log k$ more than the average case. To put it in perspective: if you have a million possible outcomes, finding the average chaos might take a few thousand guesses, but finding the single most likely outcome requires millions of guesses.

Why was the old idea wrong?
The authors explain that the old method relied on a mathematical tool that assumes the "shape" of the data changes smoothly. But Min-entropy is like a sharp spike. You can change the data just a tiny bit (so the old tool thinks it's almost the same), but that tiny change could move the "heavy" number to a completely different spot. Because the old tool can't handle these sharp spikes, it fails. The authors show that to find the spike, you have to look much harder and collect way more data.

The Growing Order Challenge

The paper also looks at a middle ground called Rényi Entropy. Think of this as a dial you can turn.

Turn it all the way left, and you get the "average" chaos.
Turn it all the way right, and you get the "worst-case" (Min-entropy).
Turn it somewhere in the middle, and you get a mix.

The authors ask: What happens if we turn the dial higher and higher as the number of possible outcomes ( $k$ ) gets bigger?

They discovered a precise rule for this. If you turn the dial to a setting called $\alpha$ (where $\alpha$ is an integer between 2 and roughly $\log k$ ), the number of samples you need is $\Theta(\alpha k^{1 - 1/\alpha})$ .

Here is the cool part: The authors proved that the factor $\alpha$ is unavoidable. In previous studies, people thought they could hide this factor inside the math constants. But this paper shows that as you turn the dial higher, you must pay the price of collecting more samples, and that cost grows linearly with the dial setting. They built a new "estimator" (a counting method) that is efficient enough to hit this target, and they proved you can't do it with fewer samples.

The "Heavy Hiding" Game

How did they prove you can't do it with fewer samples? They invented a game of hide-and-seek.

Imagine a room with $k$ boxes. In the "easy" version, all boxes are empty. In the "hard" version, one box has a slightly heavier ball in it, but you don't know which box it is. The authors showed that if you don't look in enough boxes (specifically, if you look in fewer than $k \log k$ boxes), you simply cannot tell the difference between the empty room and the room with the hidden heavy ball. The heavy ball is so well-hidden that your samples look exactly the same as if nothing was there.

This "hidden coordinate" trick is the key to their proof. It shows that the difficulty isn't just about counting; it's about the sheer effort required to find a needle in a haystack when the needle is trying to hide.

The High-Order Shortcut

Finally, the paper looks at what happens when you turn the dial very high (when $\alpha$ is much larger than $\log k$ ).

At this extreme, the authors found a shortcut. When the dial is turned high enough, the "Rényi entropy" becomes almost identical to the "Min-entropy." It's like looking at a mountain from far away; the details blur, and it just looks like a single peak. Because they are so similar, you can use the same method you use for finding the "heavy ball" (Min-entropy) to estimate the high-order chaos. This means that for very high settings, the sample complexity jumps back up to $\Theta(k \log k)$ , just like the worst-case scenario.

The Bottom Line

This paper doesn't just guess; it provides a complete mathematical map.

It corrects a mistake: It proves that finding the most likely outcome (Min-entropy) is harder than previously thought, requiring $\Theta(k \log k)$ samples, not $\Theta(k / \log k)$ .
It maps the middle ground: It gives the exact formula for how many samples are needed as you turn the "chaos dial" up, showing that the cost grows linearly with the dial setting.
It connects the extremes: It shows that when the dial is turned high enough, the problem becomes the same as finding the worst-case scenario.

The authors have essentially drawn the boundaries of how much data we need to understand randomness, whether we are looking at the average, the worst-case, or anything in between. They've shown us that some mysteries require a lot more digging than others, and they've given us the exact number of shovels we need to dig them up.

Technical Summary: Tight Sample Bounds for Rényi and Min-Entropy Estimation

Problem Statement

The paper addresses the fundamental problem of estimating entropy from independent samples drawn from an unknown distribution $p$ over a finite alphabet $[k] = \{1, \dots, k\}$ . The goal is to determine the minimax sample complexity $S_\alpha(k, \epsilon, \delta)$ required to estimate the Rényi entropy $H_\alpha(p)$ to an additive error $\epsilon$ with failure probability at most $\delta$ .

The study focuses on two specific regimes:

Min-entropy ( $H_\infty$ ): The limit as $\alpha \to \infty$ , defined as $H_\infty(p) = -\log \|p\|_\infty$ , which measures worst-case predictability.
Growing-order Rényi entropy ( $H_\alpha$ ): The behavior of the sample complexity when the order $\alpha$ is not fixed but grows with the alphabet size $k$ , specifically in the regime $2 \le \alpha \le c_0 \log k$ .

While the sample complexity for Shannon entropy ( $\alpha=1$ ) is well-established as $\Theta(k/\log k)$ , and fixed-order integer $\alpha > 1$ was previously characterized as $\Theta_\alpha(k^{1-1/\alpha})$ , the dependence on $\alpha$ when it grows with $k$ and the exact complexity of min-entropy estimation remained unresolved.

Methodology

The authors employ distinct analytical techniques tailored to the structural differences between min-entropy (an extreme-value functional) and finite-order Rényi entropy (governed by multi-way collision probabilities).

1. Min-Entropy Estimation

Upper Bound: The authors analyze the plug-in estimator $\hat{H}_\infty = -\log \hat{p}_\star$ , where $\hat{p}_\star$ is the maximum empirical frequency. Unlike standard concentration bounds that treat all symbols uniformly, the proof utilizes a dyadic grouping of symbol probabilities. Symbols are partitioned into buckets based on their probability scale relative to the true maximum $p_\star$ . This allows for a refined union bound where the probability of a lighter symbol fluctuating to exceed the true maximum decays rapidly with the bucket level, yielding a distribution-sensitive concentration bound dependent on $1/p_\star$ rather than $k$ .
Lower Bound: A hypothesis testing framework is constructed using a hidden-heavy-coordinate mixture. The null hypothesis is the uniform distribution $U_k$ . The alternative hypothesis is a mixture of distributions where a single coordinate $j$ (chosen uniformly at random) has a slightly elevated probability $(1+\gamma)/k$ . The proof demonstrates that distinguishing this mixture from the uniform distribution requires $\Omega(k \log k)$ samples, as the likelihood ratio's second moment remains small below this threshold due to the uncertainty of the heavy coordinate's location.
Refutation of Prior Claims: The paper explicitly demonstrates that the Valiant–Valiant "Estimating the Unseen" framework, which relies on continuity with respect to relative earthmover distance, does not apply to min-entropy. The authors construct a counterexample showing that distributions can be arbitrarily close in relative earthmover distance while having min-entropies separated by a constant.

2. Growing-Order Rényi Entropy Estimation

Upper Bound: For integer $\alpha$ , the authors analyze the unbiased falling-factorial estimator for the power sum $P_\alpha(p) = \sum p_i^\alpha$ . The estimator is $\hat{P}_\alpha = \frac{1}{(n)_\alpha} \sum (N_i)_\alpha$ , where $N_i$ are empirical counts. The novelty lies in the variance analysis. Previous works bounded the relative error of $P_\alpha$ with constants absorbing $\alpha$ . Here, the authors explicitly track the dependence on $\alpha$ by classifying pairs of $\alpha$ -tuples by their overlap size. They exploit the fact that additive error in $H_\alpha$ permits a wider multiplicative window for $P_\alpha$ (specifically $e^{-(\alpha-1)\epsilon} \le \hat{P}_\alpha/P_\alpha \le e^{(\alpha-1)\epsilon}$ ), which is crucial for removing a factor of $\alpha$ from the bound.
Lower Bound: The lower bound construction also uses a hidden-heavy-coordinate mixture, but with a more delicate analysis involving Poissonization and truncated likelihood ratios. The alternative distributions have a heavy coordinate at a critical scale $k^{-1+1/\alpha}$ . To prove indistinguishability, the authors truncate the likelihood ratio at $\lfloor \alpha \rfloor$ to handle rare high-occupancy events that would otherwise dominate the second moment. This truncation, tied to the order $\alpha$ , allows them to show that the mixture remains statistically indistinguishable from the null up to $n \approx \alpha k^{1-1/\alpha}$ .

Key Contributions and Results

The paper provides complete characterizations of the sample complexity for the specified regimes, resolving previous ambiguities regarding the dependence on $\alpha$ .

1. Min-Entropy Complexity

The paper proves that estimating min-entropy to constant additive accuracy requires:
$S_\infty(k, \Theta(1), 1/3) = \Theta(k \log k)$
This result corrects a previously claimed $\Theta(k/\log k)$ characterization (based on the Valiant–Valiant framework) and establishes that min-entropy estimation is strictly harder than Shannon entropy estimation by a factor of $\Theta(\log^2 k)$ .

2. Growing-Order Rényi Entropy Complexity

For integer orders $2 \le \alpha \le c_0 \log k$ , the paper establishes a matching upper and lower bound:
$S_\alpha(k, \Theta(1), 1/3) = \Theta_{c_0}(\alpha k^{1-1/\alpha})$

Upper Bound: $O(\alpha k^{1-1/\alpha})$ , improving upon the previous best explicit bound of $O(\alpha^2 k^{1-1/\alpha})$ .
Lower Bound: $\Omega(\alpha k^{1-1/\alpha})$ , proving that the linear factor of $\alpha$ is statistically unavoidable when the order grows.
Real Orders: For real orders $1.001 \le \alpha \le c_0 \log k$ , the paper establishes the uniform lower bound $\Omega_{c_0}(\alpha k^{1-1/\alpha})$ .

3. High-Order Regime

The authors show that for sufficiently large $\alpha$ (specifically $\alpha > c_0 \log k$ ), the Rényi entropy $H_\alpha$ is uniformly close to min-entropy $H_\infty$ within a deterministic bound of $\log k / (\alpha - 1)$ . Consequently, the sample complexity in this high-order regime reverts to that of min-entropy:
$S_\alpha(k, \Theta(1), 1/3) = \Theta(k \log k) \quad \text{for } \alpha > c_0 \log k$

Significance and Claims

The paper claims to resolve the precise sample complexity landscape for entropy estimation across the transition from fixed-order to min-entropy regimes.

Correction of Min-Entropy Complexity: The primary significance is the correction of the min-entropy sample complexity from the previously claimed $\Theta(k/\log k)$ to $\Theta(k \log k)$ . The authors argue that the difficulty arises not from reconstructing unseen probability mass (as in Shannon entropy) but from the specific challenge of locating a hidden extreme coordinate among $k$ possibilities.
Optimality of the $\alpha$ Factor: The paper demonstrates that the linear dependence on $\alpha$ in the sample complexity for growing integer orders is tight. This clarifies that the quadratic dependence found in previous analyses was an artifact of the proof technique (specifically, the handling of relative error for power sums) rather than an inherent statistical limitation.
Limitations of General Frameworks: By showing that min-entropy fails the continuity condition required by the Valiant–Valiant framework, the paper delineates the boundaries of applying general symmetric property estimators to extreme-value functionals.
Open Problems: The authors modestly note that while the lower bound for real non-integer orders is established, a matching upper bound for non-integer $\alpha$ in the growing regime remains open. They also identify the need for adaptive estimators that can automatically transition between the collision-based regime and the min-entropy regime without prior knowledge of $\alpha$ .

In summary, the work provides a rigorous, unified characterization of entropy estimation complexity, highlighting the distinct statistical structures of average uncertainty (Shannon) versus worst-case predictability (min-entropy) and the specific costs introduced by growing the order of the entropy functional.