Piotr Krysta

Tight Sample Bounds for Renyi and Min-Entropy Estimation

The 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.