%0 Journal Article %1 agrawal2019multinomial %A Agrawal, Rohit %D 2019 %K bounds probability readings stats %T Multinomial Concentration in Relative Entropy at the Ratio of Alphabet and Sample Sizes %U http://arxiv.org/abs/1904.02291 %X We show that the moment generating function of the Kullback-Leibler divergence between the empirical distribution of $n$ independent samples from a distribution $P$ over a finite alphabet of size $k$ (e.g. 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 $> 1n \binomn+k-1k-1 (k-1)/n \cdot łog(1 + n/(k-1))$, thus saving a factor of order $łog(n/k)$ in the standard regime of parameters where $nk$. Our proof proceeds via a simple reduction to the case $k = 2$ of a binary alphabet (e.g. a binomial distribution), and has the property that improvements in the case of $k = 2$ directly translate to improvements for general $k$.

@article{agrawal2019multinomial, abstract = {We show that the moment generating function of the Kullback-Leibler divergence between the empirical distribution of $n$ independent samples from a distribution $P$ over a finite alphabet of size $k$ (e.g. 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 $\varepsilon > \frac{1}{n} \cdot \log{\binom{n+k-1}{k-1}} \geq (k-1)/n \cdot \log(1 + n/(k-1))$, thus saving a factor of order $\log(n/k)$ in the standard regime of parameters where $n\gg k$. Our proof proceeds via a simple reduction to the case $k = 2$ of a binary alphabet (e.g. a binomial distribution), and has the property that improvements in the case of $k = 2$ directly translate to improvements for general $k$.}, added-at = {2020-02-16T19:54:45.000+0100}, author = {Agrawal, Rohit}, biburl = {https://www.bibsonomy.org/bibtex/29d611969cd40c4d7d462c64722e8ff39/kirk86}, description = {[1904.02291] Multinomial Concentration in Relative Entropy at the Ratio of Alphabet and Sample Sizes}, interhash = {92700d01848dad7cba8562b94d4f02ff}, intrahash = {9d611969cd40c4d7d462c64722e8ff39}, keywords = {bounds probability readings stats}, note = {cite arxiv:1904.02291}, timestamp = {2020-02-16T19:54:45.000+0100}, title = {Multinomial Concentration in Relative Entropy at the Ratio of Alphabet and Sample Sizes}, url = {http://arxiv.org/abs/1904.02291}, year = 2019 }