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 λ∈[0,1) by (1-λ)⁻¹, whereas for p∈(0,1) this function tends to (1-λ)-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-λ)-1/2. We prove this conjecture for every n, p∈[0,1] and λ∈[0,1). The proof bounds the derivative of the moment generating function in λ, 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-λ)-1/2-1 on the moment generating function of half the likelihood-ratio statistic. A second reduction gives from it the bound (2(1-λ)-1/2-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 λ∈(0,1), this bound is below the bound (1-λ)⁻⁽ᵏ⁻¹⁾ that the second reduction gives from Agrawal's bound (1-λ)⁻¹. For the probability that this relative entropy exceeds ε, the Chernoff bound from (2(1-λ)-1/2-1)ᵏ⁻¹ is e-nε times a factor of order (nε)(k-1)/2, whereas that from (1-λ)⁻⁽ᵏ⁻¹⁾ has a factor of order (nε)ᵏ⁻¹.