厘清了瑞尼熵与最小熵估计的采样下界，揭示其复杂度远高于香农熵。
Tight Sample Bounds for Renyi and Min-Entropy Estimation
- 通过分组集中与最大频率估计，实现对最小熵的高效估算。
- 证明最小熵需Θ(k log k)样本，比香农熵多出log²k倍采样量。
- 适用于信息论、数据压缩及隐私保护中的熵分析场景。
从样本中估计熵是信息论与性质测试的基础问题。香农熵在k符号字母表上可用Θ(k/log k)样本达到常数精度。最小熵仅依赖最可能符号，二者均为阶α的瑞尼熵H_α的特例。本文刻画了最小熵与瑞尼熵（k和整数α>1）的采样复杂度；下界对非整数α≥1.001也成立。证明最小熵估计的样本复杂度为Θ(k log k)，上界利用最大经验频率与分组集中；下界基于隐藏重符号构造。因此，最小熵所需样本量比香农熵多Θ(log²k)倍，纠正了此前误判为Θ(k/log k)的结论。对每个整数2≤α≤c₀ log k，给出匹配的固定精度界Θ_{c₀}(αk^{1-1/α})。先前结果仅给出Ω_α(k^{1-1/α})和O_{c₀}(α²k^{1-1/α})。上界分析基于α阶碰撞的无偏下降阶乘估计器，下界由隐藏重坐标构造，表明因子α不可避免。对实数1.001≤α≤c₀ log k，给出统一下界Ω_{c₀}(αk^{1-1/α})。此外，因0≤H_α(p)−H_∞(p)≤log k/(α−1)，当α为log k的充分大倍数时，最小熵可统一逼近H_α。结合最小熵界，高阶情形下样本复杂度为Θ_ε(k log k)。
原文摘要 · Abstract (English)
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 $Θ(k/\log k)$ samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-$α$ R'{e}nyi entropy, $H_α$. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for $k$ and integer $α>1$; our lower bounds also hold for noninteger $α\ge1.001$. We prove that min-entropy estimation to constant additive accuracy has sample complexity $Θ(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 $Θ(\log^2 k)$ more samples than Shannon entropy and corrects a previously stated $Θ(k/\log k)$ characterization. For every integer $2\leα\le c_0\log k$, we prove the matching fixed-accuracy bound $Θ_{c_0}(αk^{1-1/α})$. Previous results gave $Ω_α(k^{1-1/α})$ for fixed integer $α>1$ and $O_{c_0}(α^2k^{1-1/α})$ for all integer $α>1$. Our upper bound analyzes an unbiased falling-factorial estimator based on $α$-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor $α$ is unavoidable. For every real $1.001\leα\le c_0\log k$, we prove the uniform lower bound $Ω_{c_0}(αk^{1-1/α})$. Finally, since $0\le H_α(p)-H_\infty(p)\le\log k/(α-1)$, min-entropy uniformly approximates $H_α$ when $α$ is a sufficiently large multiple of $\log k$. Combining this reduction with our min-entropy bounds gives $Θ_\varepsilon(k\log k)$ sample complexity in the high-order regime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。