An Effective Bernstein-type Bound on Shannon Entropy over Countably Infinite Alphabets

2021/06/23 by Zhao, Yunpeng
#60E15 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR)

paper · doi:10.48550/arxiv.2106.12149

Abstract

We prove a Bernstein-type bound for the difference between the average of negative log-likelihoods of independent discrete random variables and the Shannon entropy, both defined on a countably infinite alphabet. The result holds for the class of discrete random variables with tails lighter than or on the same order of a discrete power-law distribution. Most commonly-used discrete distributions such as the Poisson distribution, the negative binomial distribution, and the power-law distribution itself belong to this class. The bound is effective in the sense that we provide a method to compute the constants in it.

Related

• An Optimal Uniform Concentration Inequality for Discrete Entropies on Finite Alphabets in the High-dimensional Setting
• An entropy functional bounded from above by one
• The Harmonic Entropy Estimator: Minimax Optimality and Semiparametric Efficiency for Infinite Alphabets
• Shannon Entropy Estimation in ∞-Alphabets from Convergence Results
• Necessary and Sufficient Conditions for Characterizing Finite Discrete Distributions with Generalized Shannon's Entropy