Abstract:

We prove a Bernstein-type bound for the difference between the average of the negative log-likelihoods of independent categorical variables with infinitely many levels - that is, a countably infinite number of categories, and its expectation - namely, the Shannon entropy. The result holds for the class of discrete random variables with tails lighter than or of the same order as 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 within it. The new technique we develop allows us to obtain a uniform concentration inequality for categorical variables with a finite number of levels with the same optimal rate as in the literature, but with a much simpler proof.

2010 AMS Mathematics Subject Classification: Primary 60E15;

Keywords and phrases: Bernstein-type bound, categorical variables with infinitely many levels, concentration inequality, Shannon entropy