Pith. sign in

REVIEW 5 minor 29 references

Estimating min-entropy from samples requires Θ(k log k) samples, and Rényi entropy of order α requires Θ(α k^(1−1/α)) for growing integer α.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 19:25 UTC pith:22QYMZMT

load-bearing objection The paper genuinely settles min-entropy sample complexity at Θ(k log k) and growing-order Rényi at Θ(α k^{1−1/α}); the proofs are long but the main machinery checks out.

arxiv 2607.16966 v1 pith:22QYMZMT submitted 2026-07-18 cs.IT cs.CCcs.LGmath.ITmath.STstat.TH

Tight Sample Bounds for Renyi and Min-Entropy Estimation

Arman Adibi , Piotr Krysta This is my paper
classification cs.IT cs.CCcs.LGmath.ITmath.STstat.TH MSC 94A1762G0562C20
keywords min-entropy estimationRényi entropysample complexityfalling-factorial estimatorcollision statisticsempirical maximumproperty testingPoissonization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Min-entropy estimation at constant additive accuracy has sample complexity Θ(k log k), a Θ(log^2 k) factor more than Shannon entropy, and this paper proves both the upper and lower directions. For Rényi entropy of integer order α between 2 and c0 log k, it proves the tight bound Θ_{c0}(α k^(1−1/α)), exposing a previously hidden factor of α. The min-entropy result corrects a prior Θ(k/log k) claim by showing the standard relative-earthmover continuity argument does not apply to min-entropy. If the bounds hold, entropy estimation in large-alphabet settings—cryptography, property testing, randomness testing—has a precise sample-cost target, and growing-order Rényi entropy is genuinely harder than any fixed-order analysis suggested.

Core claim

The paper's central claim is that worst-case min-entropy estimation is not as cheap as Shannon entropy estimation: with constant additive error and constant failure probability, n = Θ(k log k) samples are necessary and sufficient. The upper bound comes from the empirical maximum bp⋆, with a dyadic grouping of probability scales that controls overtaking by light symbols; the lower bound comes from a distribution chosen uniformly among k coordinates slightly heavier than the rest, which forces an extra log k search cost. For integer Rényi orders, the paper shows the minimax rate is Θ_{c0}(α k^(1−1/α)) throughout 2 ≤ α ≤ c0 log k: an unbiased falling-factorial collision estimator achieves it, a

What carries the argument

Two mechanisms carry the argument. For min-entropy, the plug-in estimator −log max_i(N_i/n) is analyzed via dyadic buckets of symbols by probability scale; bucket sizes are bounded by normalization and upper-tail probabilities decay fast, giving a O(1/p⋆) prefactor. For Rényi entropy, the unbiased falling-factorial estimator bPα = (n)_α^(−1) Σ_x (N_x)_α represents an average of α-way collision indicators; organizing the variance by how many sample positions two indicator tuples share yields the O(α k^(1−1/α)) upper bound. The lower bound's key device is a hidden-coordinate mixture with heavy mass at scale a = k^(−1+1/α), compared against a product-Poisson baseline with a likelihood ratio tru

Load-bearing premise

The Rényi lower bound's load-bearing step is the truncation of occupancy counts at ⌊α⌋: the proof must show that the discarded tail of the mixture likelihood ratio is negligible and that the truncated second moment is ≤ 10^(−6); if that cutoff fails anywhere in 1.001 ≤ α ≤ c0 log k, the Ω(α k^(1−1/α)) lower bound does not follow.

What would settle it

Directly compute the exact, untruncated χ² divergence between the two hidden-heavy-coordinate Poisson mixtures for k = 10^4, α = 8, B = e^4, and n = α k^(1−1/α)/4. If the divergence is bounded below by a positive constant rather than vanishing, then the occupancy cutoff ⌊α⌋ discards a non-negligible part of the evidence and the lower-bound argument would need revision.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Min-entropy estimation requires Θ(log^2 k) more samples than Shannon entropy estimation, so worst-case predictability is strictly costlier to assess than average uncertainty.
  • The α factor in the Rényi bound is intrinsic: any estimator that hides α in fixed-order constants misses a linear-order penalty that appears as soon as α grows with k.
  • In the high-order regime α ≥ 1 + 2 log k/ε, an ε/2-accurate min-entropy estimator becomes an ε-accurate Rényi entropy estimator, giving Θ(k log k) sample complexity there as well.
  • The failure of relative-earthmover continuity means generic histogram-reconstruction estimators cannot be applied to min-entropy; extreme-value estimators need dedicated concentration arguments.
  • For real noninteger orders 1.001 ≤ α ≤ c0 log k, the uniform lower bound Ω(α k^(1−1/α)) holds, though the matching upper bound remains open.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the truncation analysis is robust, similar truncated likelihood ratios could give tight lower bounds for other extreme-value statistics, such as estimating the size of the largest atom or the support of a near-uniform distribution, where a hidden-coordinate search cost should reappear.
  • The dyadic-concentration upper bound for the empirical maximum is distribution-dependent and may extend to countable alphabets or heavy-tailed sources, giving local sample complexities governed by 1/p⋆ rather than ambient alphabet size.
  • A natural next step is an adaptive estimator that chooses between the collision regime and the empirical-maximum regime based on α; the paper supplies both rates but no unified algorithm.
  • The k log k benchmark suggests practical min-entropy testers should expect a logarithmic search overhead relative to Shannon-entropy tests, which could inform sequential or de-randomized procedures that first locate candidate heavy coordinates.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper determines the minimax sample complexity of estimating min-entropy and integer-order Rényi entropy over k-symbol alphabets to constant additive accuracy. It proves that min-entropy estimation requires Θ(k log k) samples, in contrast with Θ(k/log k) for Shannon entropy, and explains why the Valiant–Valiant relative-earthmover framework does not apply to min-entropy. For integer orders 2 ≤ α ≤ c0 log k it proves the matching fixed-accuracy rate Θ_{c0}(α k^{1−1/α}) by analyzing a falling-factorial collision estimator and a hidden-heavy-coordinate lower bound; for real orders 1.001 ≤ α ≤ c0 log k it proves the uniform lower bound Ω_{c0}(α k^{1−1/α}). It further transfers the min-entropy bounds to the sufficiently high-order regime α ≳ log k. The proofs use dyadic concentration for the empirical maximum (Section 4), a tuple-overlap variance decomposition for the collision estimator (Section 5), an exact χ² computation for the min-entropy lower bound (Section 7), and a Poissonized truncated likelihood-ratio argument for the Rényi lower bound (Section 8).

Significance. If the results hold, they close genuine gaps left by fixed-order notation. Previous work hid the α dependence in Θ_α(·), and the claimed Θ(k/log k) rate for min-entropy rested on an inapplicable theorem; the paper shows this explicitly with a concrete counterexample in Section 3.2. The main technical contributions are substantial: the dyadic grouping in Section 4 replaces a crude k-factor by 1/p⋆; the light–heavy split in Section 5.4 removes one factor of α relative to prior variance analyses; the exact χ² formula in Lemma 7.5 is a clean, checkable computation; and the hidden-heavy-coordinate construction with truncation at ⌊α⌋ in Section 8 is a novel way to obtain the linear α factor in the lower bound. The proofs are detailed, internally consistent, and derived from first principles, with explicit constants (e.g., C0 = 10^6 in Lemma 5.4). The paper also responsibly states its limitations: the noninteger lower bound is not claimed sharp, and the ε-dependence is not optimized. I see no circularity or unsupported reliance on prior work; Appendices A and B carefully extract the α-dependence from [1] and [2]. The paper is likely to be influential in property testing and information th

minor comments (5)
  1. [Abstract and Section 2] Editorial: 'lower bound also hold' should be 'lower bound also holds'; 'non-integers' should be 'non-integer values'. These do not affect content.
  2. [§8.1 vs §2.2] The accuracy parameter is denoted ϵ in Section 8.1 but ε in Theorem 2.2 and Section 5. Unify the notation to avoid confusion, especially since the same symbol appears in the final bound n ≥ Cϵ α k^{1−1/α}/ε².
  3. [§5.4, Regime 1] The line 'because ∀η: 2≤e^{−η}+e^η' is correct but terse. The inequality (2−e^{−η}) ≤ e^η follows immediately from e^η+e^{−η}≥2; a one-line expansion would improve readability.
  4. [Appendix A] The notation conflict (Δ for accuracy, ε for confidence) is acknowledged in Section A.1, but the appendix remains hard to follow. Consider renaming the accuracy to ε_acc or ρ to align with the main text.
  5. [§9 and Remark 8.1] The noninteger lower bound is stated for fixed ε∈(0,1) with constants C_ε = c1 ε². The paper later notes that the ε-dependence is not optimized; this is fine, but the theorem statement in Section 8.1 could explicitly say that the bound is not claimed to be tight in ε.

Circularity Check

0 steps flagged

No significant circularity: the main bounds are derived from first principles via standard probabilistic arguments, with prior work used only for comparison and context.

full rationale

The paper's central claims — the min-entropy Θ(k log k) bound and the growing-order Rényi Θ(α k^{1−1/α}) bound — are derived directly from explicit constructions and self-contained probabilistic analyses. The min-entropy upper bound follows from a dyadic concentration argument for the empirical maximum (Section 4), and the lower bound from a hidden-heavy-coordinate Le Cam reduction with an exact chi-squared second-moment calculation (Sections 7.2–7.5). The Rényi upper bound analyzes the falling-factorial collision estimator with explicit overlap-variance bounds and a light–heavy regime split (Section 5), while the lower bound uses a distinct hidden-coordinate mixture, Poissonization, and a truncated likelihood-ratio second-moment argument (Section 8). Prior works [1, 2, 4, 19, 24] are cited for comparison, standard facts, or to contextualize previous bounds; Appendices A and B extract constants from those works but are not inputs to the paper's main theorems. No target result appears as an assumption, no fitted parameter is renamed as a prediction, and no load-bearing self-citation chain forces the conclusions. The most delicate technical step, the truncation at ⌊α⌋ in Lemma 8.5, is proven rather than assumed, and the uniformity check over 1.001 ≤ α ≤ c0 log k is carried out explicitly. Accordingly, the honest finding is no significant circularity.

Axiom & Free-Parameter Ledger

4 free parameters · 6 axioms · 0 invented entities

No data-fitted model parameters or new ontological entities are introduced. The hidden-heavy-coordinate distributions are lower-bound test families, not postulated entities. The listed constants are universal proof constants chosen by hand to make the bounds uniform; they do not affect the claimed asymptotic rates.

free parameters (4)
  • C0 (batch-size constant) = 10^6
    Chosen large enough in Eq. (2) to make the variance/Chebyshev bounds in Lemma 5.4 and Regime 2 hold; any sufficiently large universal constant works.
  • B (alternative heavy-factor) = e^4
    Chosen in Section 8.2 so the Rényi entropy gap exceeds 2ε for every ε<1; does not affect the asymptotic rate.
  • C* (lower-bound threshold constant) = min{1, 1/(8c0(1+B^2)), e^{-40}/(eB), e^{-40}/(2eB^2)}
    Chosen in Section 8.5 to make the truncation and second-moment bounds uniform over 1.001≤α≤c0 log k; depends only on c0.
  • cγ (min-entropy lower-bound constant) = 1/(4γ²)
    Chosen in Lemma 7.6 so the χ² diagonal term decays below the k log k scale; depends only on the fixed separation γ.
axioms (6)
  • standard math Standard Chernoff/union/Chebyshev/Cauchy–Schwarz inequalities (Fact D.1)
    Used throughout; classical results, not proved from scratch.
  • standard math Le Cam's reduction for separated priors (Lemma 6.1)
    Standard testing lower-bound tool; cited to Tsybakov.
  • standard math Poissonization: Poisson-split counts are independent Poisson (Fact D.12)
    Used in the Rényi lower bound to compare mixture laws.
  • standard math Power-sum lower bound Pα(p)≥k^{1−α} (Fact D.10)
    Used in variance bounds; follows from Jensen/power-mean inequality.
  • standard math Hellinger tensorization and Poisson affinity (Facts D.5, D.6)
    Used to compare true and idealized mixture experiments in Section 8.7.
  • domain assumption i.i.d. sampling model from unknown p∈Δ_k with minimax accuracy (Section 3.1)
    Problem formulation; all results are within this model.

pith-pipeline@v1.3.0-alltime-deepseek · 42702 in / 24643 out tokens · 214805 ms · 2026-08-01T19:25:22.237186+00:00 · methodology

0 comments
read the original abstract

Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a $k$-symbol alphabet using $\Theta(k/\log k)$ samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-$\alpha$ R'{e}nyi entropy, $H_\alpha$. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for $k$ and integer $\alpha>1$; our lower bounds also hold for noninteger $\alpha\ge1.001$. We prove that min-entropy estimation to constant additive accuracy has sample complexity $\Theta(k\log k)$. The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires $\Theta(\log^2 k)$ more samples than Shannon entropy and corrects a previously stated $\Theta(k/\log k)$ characterization. For every integer $2\le\alpha\le c_0\log k$, we prove the matching fixed-accuracy bound $\Theta_{c_0}(\alpha k^{1-1/\alpha})$. Previous results gave $\Omega_\alpha(k^{1-1/\alpha})$ for fixed integer $\alpha>1$ and $O_{c_0}(\alpha^2k^{1-1/\alpha})$ for all integer $\alpha>1$. Our upper bound analyzes an unbiased falling-factorial estimator based on $\alpha$-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor $\alpha$ is unavoidable. For every real $1.001\le\alpha\le c_0\log k$, we prove the uniform lower bound $\Omega_{c_0}(\alpha k^{1-1/\alpha})$. Finally, since $0\le H_\alpha(p)-H_\infty(p)\le\log k/(\alpha-1)$, min-entropy uniformly approximates $H_\alpha$ when $\alpha$ is a sufficiently large multiple of $\log k$. Combining this reduction with our min-entropy bounds gives $\Theta_\varepsilon(k\log k)$ sample complexity in the high-order regime.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references

  1. [1]

    Estimating R´ enyi entropy of discrete distributions.IEEE Transactions on Information Theory, 63(1):38–56,

    Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. Estimating R´ enyi entropy of discrete distributions.IEEE Transactions on Information Theory, 63(1):38–56,

  2. [2]

    R´ enyi entropy estimation revisited

    Maciej Obremski and Maciej Skorski. R´ enyi entropy estimation revisited. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 81 of LIPIcs, pages 20:1–20:15. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2017

    2017

  3. [3]

    Private and communication-efficient algorithms for entropy estimation

    Gecia Bravo-Hermsdorff, R´ obert Busa-Fekete, Mohammad Ghavamzadeh, Andres Munoz Med- ina, and Umar Syed. Private and communication-efficient algorithms for entropy estimation. Advances in Neural Information Processing Systems, 35:15382–15393, 2022

    2022

  4. [4]

    Towards more efficient R´ enyi entropy estimation.Entropy, 25(2):185, 2023

    Maciej Skorski. Towards more efficient R´ enyi entropy estimation.Entropy, 25(2):185, 2023

    2023

  5. [5]

    Entropy testing and its application to testing bayesian networks.Advances in Neural Information Processing Systems, 37:132977–133006, 2024

    Cl´ ement L Canonne and Joy Q Yang. Entropy testing and its application to testing bayesian networks.Advances in Neural Information Processing Systems, 37:132977–133006, 2024

    2024

  6. [6]

    The complexity of estimating R´ enyi entropy

    Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. The complexity of estimating R´ enyi entropy. InProceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1855–1869, 2015

    2015

  7. [7]

    Claude E. Shannon. A mathematical theory of communication.Bell System Technical Journal, 27:379–423, 623–656, 1948

    1948

  8. [8]

    Ralph V. L. Hartley. Transmission of information.Bell System Technical Journal, 7(3):535–563, 1928. 71

    1928

  9. [9]

    On measures of entropy and information

    Alfr´ ed R´ enyi. On measures of entropy and information. InProceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 547–561. University of California Press, 1961

    1961

  10. [10]

    Salil P. Vadhan. Pseudorandomness.Foundations and Trends in Theoretical Computer Science, 7(1–3):1–336, 2012

    2012

  11. [11]

    Bennett, Gilles Brassard, Claude Cr´ epeau, and Ueli M

    Charles H. Bennett, Gilles Brassard, Claude Cr´ epeau, and Ueli M. Maurer. Generalized privacy amplification.IEEE Transactions on Information Theory, 41(6):1915–1923, 1995

    1915

  12. [12]

    How to recycle random bits

    Russell Impagliazzo and David Zuckerman. How to recycle random bits. InProceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS, pages 248–253, 1989

    1989

  13. [13]

    McKay, Mary L

    Meltem S¨ onmez Turan, Elaine Barker, John Kelsey, Kerry A. McKay, Mary L. Baish, and Mike Boyle. Recommendation for the entropy sources used for random bit generation. NIST Special Publication 800-90B, National Institute of Standards and Technology, 2018

    2018

  14. [14]

    An inequality on guessing and its application to sequential decoding.IEEE Transactions on Information Theory, 42(1):99–105, 1996

    Erdal Arikan. An inequality on guessing and its application to sequential decoding.IEEE Transactions on Information Theory, 42(1):99–105, 1996

    1996

  15. [15]

    Generalized cutoff rates and R´ enyi’s information measures.IEEE Transactions on Information Theory, 41(1):26–34, 1995

    Imre Csisz´ ar. Generalized cutoff rates and R´ enyi’s information measures.IEEE Transactions on Information Theory, 41(1):26–34, 1995

    1995

  16. [16]

    van Oorschot and Michael J

    Paul C. van Oorschot and Michael J. Wiener. Parallel collision search with cryptanalytic applications.Journal of Cryptology, 12(1):1–28, 1999

    1999

  17. [17]

    Estimation of entropy and mutual information.Neural Computation, 15(6):1191– 1253, 2003

    Liam Paninski. Estimation of entropy and mutual information.Neural Computation, 15(6):1191– 1253, 2003

    2003

  18. [18]

    Estimating entropy on m bins given fewer than m samples.IEEE Transactions on Information Theory, 50(9):2200–2203, 2004

    Liam Paninski. Estimating entropy on m bins given fewer than m samples.IEEE Transactions on Information Theory, 50(9):2200–2203, 2004

    2004

  19. [19]

    Estimating the unseen: An n/logn -sample estimator for entropy and support size, shown optimal via new CLTs

    Gregory Valiant and Paul Valiant. Estimating the unseen: An n/logn -sample estimator for entropy and support size, shown optimal via new CLTs. InProceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC, pages 685–694, 2011

    2011

  20. [20]

    The power of linear estimators

    Gregory Valiant and Paul Valiant. The power of linear estimators. InProceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 403–412, 2011

    2011

  21. [21]

    Estimating the unseen: Improved estimators for entropy and other properties.Journal of the ACM, 64(6):37:1–37:41, 2017

    Gregory Valiant and Paul Valiant. Estimating the unseen: Improved estimators for entropy and other properties.Journal of the ACM, 64(6):37:1–37:41, 2017

    2017

  22. [22]

    Minimax estimation of functionals of discrete distributions.IEEE Transactions on Information Theory, 61(5):2835– 2885, 2015

    Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions.IEEE Transactions on Information Theory, 61(5):2835– 2885, 2015

    2015

  23. [23]

    Minimax rates of entropy estimation on large alphabets via best polynomial approximation.IEEE Transactions on Information Theory, 62(6):3702–3720, 2016

    Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation.IEEE Transactions on Information Theory, 62(6):3702–3720, 2016

    2016

  24. [24]

    Quantum query complexity of entropy estimation.IEEE Transactions on Information Theory, 65(5):2899–2921, 2019

    Tongyang Li and Xiaodi Wu. Quantum query complexity of entropy estimation.IEEE Transactions on Information Theory, 65(5):2899–2921, 2019. 72

    2019

  25. [25]

    Cambridge university press, 2017

    Michael Mitzenmacher and Eli Upfal.Probability and computing: Randomization and proba- bilistic techniques in algorithms and data analysis. Cambridge university press, 2017

    2017

  26. [26]

    Tsybakov.Introduction to Nonparametric Estimation

    Alexandre B. Tsybakov.Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, 2009

    2009

  27. [27]

    Cambridge university press, 1952

    Godfrey Harold Hardy, John Edensor Littlewood, and George P´ olya.Inequalities. Cambridge university press, 1952

    1952

  28. [28]

    Oxford University Press, 1992

    Andrew D Barbour, Lars Holst, and Svante Janson.Poisson approximation. Oxford University Press, 1992. 73

    1992

  29. [2017]

    Conference version appeared in SODA 2015

    2015