Rényi 熵估算样本复杂度研究获紧确界限

abeirami · x · 2026-08-19

论文《Tight Sample Bounds for Renyi and Min-Entropy Estimation》研究了 Rényi 熵和最小熵估算的样本复杂度。研究证明了估算最小熵至常数加性精度的样本复杂度为 $\Theta(k\log k)$，比香农熵需要多 $\Theta(\log^2 k)$ 个样本，纠正了之前 $\Theta(k/\log k)$ 的错误结论。对于整数阶 $\alpha$ ($2 \le \alpha \le c0 \log k$)，研究给出了匹配的上下界 $\Theta(\alpha k^{1-1/\alpha})$，并证明了因子 $\alpha$ 是不可避免的。