On Agrawal's Conjecture for the Moment Generating Function of the Binomial Relative Entropy

For a binomial count $B$ of $n$ trials, the likelihood-ratio statistic for the hypothesis that the success probability equals $p$ is $2n$ times the relative entropy between the Bernoulli distributions with parameters $B/n$ and $p$. Agrawal bounded the moment generating function of half this statistic at $\lambda\in[0,1)$ by $(1-\lambda)^{-1}$, whereas for $p\in(0,1)$ this function tends to $(1-\lambda)^{-1/2}$ as $n$ grows. He conjectured that the one-sided statistic, which equals $n$ times the relative entropy when $B/n$ exceeds $p$ and zero otherwise, has moment generating function at most $(1-\lambda)^{-1/2}$. We prove this conjecture for every $n$, $p\in[0,1]$ and $\lambda\in[0,1)$. The proof bounds the derivative of the moment generating function in $\lambda$, a sum over the values of $B$. It compares this sum with an integral or bounds it directly, by analytic estimates and interval arithmetic, which encloses every value of a function on ranges of its arguments. A reduction of Agrawal then gives the bound $2(1-\lambda)^{-1/2}-1$ on the moment generating function of half the likelihood-ratio statistic. A second reduction gives from it the bound $(2(1-\lambda)^{-1/2}-1)^{k-1}$ on the moment generating function of $n$ times the relative entropy between the empirical distribution of $n$ samples from a distribution on $k$ symbols and that distribution. For $\lambda\in(0,1)$, this bound is below the bound $(1-\lambda)^{-(k-1)}$ that the second reduction gives from Agrawal's bound $(1-\lambda)^{-1}$. For the probability that this relative entropy exceeds $\varepsilon$, the Chernoff bound from $(2(1-\lambda)^{-1/2}-1)^{k-1}$ is $e^{-n\varepsilon}$ times a factor of order $(n\varepsilon)^{(k-1)/2}$, whereas that from $(1-\lambda)^{-(k-1)}$ has a factor of order $(n\varepsilon)^{k-1}$.