Finite-Sample Concentration of the Multinomial in Relative Entropy

DOI10.1109/TIT.2020.2996134MaRDI QIDQ5138810zbMATH OpenFDO

Authors Rohit Agrawal

Publication date 4 December 2020

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

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

zbMATH Keywords

discrete likelihood-ratio statisticfinite-sample boundsKullback-Leibler divergencemoment generating functionmoments of empirical divergencerelative entropy

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Coding theorems (Shannon theory) (94A24)

Abstract: We show that the moment generating function of the Kullback-Leibler divergence (relative entropy) between the empirical distribution of $n$ independent samples from a distribution $P$ over a finite alphabet of size $k$ (i.e. a multinomial distribution) and $P$ itself is no more than that of a gamma distribution with shape $k-1$ and rate $n$. The resulting exponential concentration inequality becomes meaningful (less than 1) when the divergence $varepsilon$ is larger than $(k-1)/n$, whereas the standard method of types bound requires $$, thus saving a factor of order $log(n/k)$ in the standard regime of parameters where $nggk$. As a consequence, we also obtain finite-sample bounds on all the moments of the empirical divergence (equivalently, the discrete likelihood-ratio statistic), which are within constant factors (depending on the moment) of their asymptotic values. Our proof proceeds via a simple reduction to the case $k=2$ of a binary alphabet (i.e. a binomial distribution), and has the property that improvements in the case of $k=2$ directly translate to improvements for general $k$. In particular, we conjecture a bound on the binomial moment generating function that would almost close the quadratic gap between our finite-sample bound and the asymptotic moment generating function bound from Wilks' theorem (which does not hold for finite samples).

Cited in

(3)

• Optimal non-asymptotic concentration of centered empirical relative entropy in the high-dimensional regime
• Minimum information dependence modeling
• Estimation of discrete distributions in relative entropy, and the deviations of the missing mass

This page was built for publication: Finite-Sample Concentration of the Multinomial in Relative Entropy

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