Concentration inequalities for the empirical distribution of discrete distributions: beyond the method of types
Authors:
- 18 November 2019
- journal article
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 9 (4) , 813-850
Abstract
We study concentration inequalities for the Kullback–Leibler (KL) divergence between the empirical distribution and the true distribution. Applying a recursion technique, we improve over the method of types bound uniformly in all regimes of sample size $n$ and alphabet size $k$, and the improvement becomes more significant when $k$ is large. We discuss the applications of our results in obtaining tighter concentration inequalities for $L_1$ deviations of the empirical distribution from the true distribution, and the difference between concentration around the expectation or zero. We also obtain asymptotically tight bounds on the variance of the KL divergence between the empirical and true distribution, and demonstrate their quantitatively different behaviours between small and large sample sizes compared to the alphabet size.
Keywords
This publication has 14 references indexed in Scilit:
- Boundary Crossing Probabilities for General Exponential FamiliesMathematical Methods of Statistics, 2018
- Maximum Likelihood Estimation of Functionals of Discrete DistributionsIEEE Transactions on Information Theory, 2017
- On the concentration of the missing massElectronic Communications in Probability, 2013
- Bernstein polynomials and learning theoryJournal of Approximation Theory, 2004
- Real Analysis2000
- The method of types [information theory]IEEE Transactions on Information Theory, 1998
- The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz InequalityThe Annals of Probability, 1990
- Boundary Crossing Problems for Sample MeansThe Annals of Probability, 1988
- Sanov Property, Generalized $I$-Projection and a Conditional Limit TheoremThe Annals of Probability, 1984
- Negative Association of Random Variables with ApplicationsThe Annals of Statistics, 1983