Estimating Renyi Entropy of Discrete Distributions

DOI10.1109/TIT.2016.2620435MaRDI QIDQ2979075zbMATH OpenOpenAlexFDO

Authors Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, Himanshu Tyagi

Publication date 2 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.1000

Mathematics Subject Classification ID

Measures of information, entropy (94A17)

Abstract: It was recently shown that estimating the Shannon entropy $H(mp)$ of a discrete $k$-symbol distribution $mp$ requires $Theta(k/logk)$ samples, a number that grows near-linearly in the support size. In many applications $H(mp)$ can be replaced by the more general R'enyi entropy of order $alpha$, $H_{a}lpha(mp)$. We determine the number of samples needed to estimate $H_{a}lpha(mp)$ for all $alpha$, showing that $alpha<1$ requires a super-linear, roughly $k^{1/alpha}$ samples, noninteger $alpha>1$ requires a near-linear $k$ samples, but, perhaps surprisingly, integer $alpha>1$ requires only $Theta(k^{1-1/alpha})$ samples. Furthermore, developing on a recently established connection between polynomial approximation and estimation of additive functions of the form $su{m}_{x}f({mp}_x)$, we reduce the sample complexity for noninteger values of $alpha$ by a factor of $logk$ 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.

Cited in

(12)

• Statistical estimation of the entropy of discrete random variables with a large number of outcomes
• Estimation of Rényi entropy for lifetime uncertainty
• Asymptotic Properties of the Plug-in Estimator of the Discrete Entropy Under Dependence
• Correcting convexity bias in function and functional estimate
• Rényi's residual entropy: a quantile approach
• Concentration of the collision estimator
• Properties of Shannon and Rényi entropies of the Poisson distribution as the functions of intensity parameter
• Threshold selection using Rényi's entropy
• Time-efficient quantum entropy estimator via samplizer
• scientific article; zbMATH DE number 7467644 (Why is no real title available?)
• Range (Rényi) entropy queries and partitioning
• Renyi entropy estimation revisited

This page was built for publication: Estimating Renyi Entropy of Discrete Distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2979075)