# Estimating Renyi Entropy of Discrete Distributions

arXiv: https://arxiv.org/abs/1408.1000 · HTML: https://mlsanity.com/paper/1408.1000/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Aug 2014.

## Built on by (most cited first, 4 of 4)

- [Locally differentially private estimation of nonlinear functionals of discrete distributions](https://mlsanity.com/paper/2107.03940/) (2021)
- [On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood](https://mlsanity.com/paper/2210.06728/) (2022)
- [A hybrid analysis of LBSN data to early detect anomalies in crowd dynamics](https://mlsanity.com/paper/2312.08092/) (2023)
- [Entropy Equivalence Testing](https://mlsanity.com/paper/2605.23225/) (2026)

## Abstract (arXiv)

It was recently shown that estimating the Shannon entropy H(rm p) of a discrete k-symbol distribution rm p requires Theta(k/log k) samples, a number that grows near-linearly in the support size. In many applications H(rm p) can be replaced by the more general R'enyi entropy of order α, Hα(rm p). We determine the number of samples needed to estimate Hα(rm p) for all α, showing that α < 1 requires a super-linear, roughly k1/α samples, noninteger α>1 requires a near-linear k samples, but, perhaps surprisingly, integer α>1 requires only Theta(k1-1/α) samples. Furthermore, developing on a recently established connection between polynomial approximation and estimation of additive functions of the form sumx f(rm px), we reduce the sample complexity for noninteger values of α by a factor of log k compared to the empirical estimator. The estimators achieving these bounds are simple and run in time linear in the number of samples. Our lower bounds provide explicit constructions of distributions with different R'enyi entropies that are hard to distinguish.