Chernoff-type Concentration of Empirical Probabilities in Relative Entropy
arXiv:2003.08614 · doi:10.1109/TIT.2020.3034539
Abstract
We study the relative entropy of the empirical probability vector with respect to the true probability vector in multinomial sampling of categories, which, when multiplied by sample size , is also the log-likelihood ratio statistic. We generalize a recent result and show that the moment generating function of the statistic is bounded by a polynomial of degree on the unit interval, uniformly over all true probability vectors. We characterize the family of polynomials indexed by and obtain explicit formulae. Consequently, we develop Chernoff-type tail bounds, including a closed-form version from a large sample expansion of the bound minimizer. Our bound dominates the classic method-of-types bound and is competitive with the state of the art. We demonstrate with an application to estimating the proportion of unseen butterflies.
arXiv commentcorrected a numerical error
References in corpus (5)
- Goodness-of-fit tests via phi-divergences
- Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
- Maximum Likelihood Estimation of Functionals of Discrete Distributions
- Confidence regions for the multinomial parameter with small sample size
- Finite-Sample Concentration of the Multinomial in Relative Entropy