The improved sample-independent MGF bound for binomial KL divergence

For a binomial experiment with sample size nn, success probability pp, empirical proportion B/nB/n, and moment-generating-function parameter x[0,1)x\in[0,1), define the binary Kullback–Leibler divergence by

D((u,1u)(v,1v))=uloguv+(1u)log1u1v.D\bigl((u,1-u)\mathbin\Vert(v,1-v)\bigr)=u\log\frac{u}{v}+(1-u)\log\frac{1-u}{1-v}.

The improved binomial MGF conjecture. The function

f(x)=21x1f(x)=\frac{2}{\sqrt{1-x}}-1

is a sample-independent upper bound for the MGF of the binomial KL divergence; equivalently, for every positive integer nn, p[0,1]p\in[0,1], and x[0,1)x\in[0,1),

E[exp(xnD((Bn,1Bn)(p,1p)))]21x1,\operatorname*{E}\left[\exp\left(xnD\left(\left(\frac{B}{n},1-\frac{B}{n}\right)\mathbin\Vert(p,1-p)\right)\right)\right]\leq \frac{2}{\sqrt{1-x}}-1,

where BBinomial(n,p)B\sim\operatorname{Binomial}(n,p). This would improve the existing bound 1/(1x)1/(1-x) and remain compatible with the asymptotic bound 1/1x1/\sqrt{1-x}, which is not valid uniformly for all finite samples.

Sources & referencesView supporting material

Primary source

Rohit Agrawal, “Finite-Sample Concentration of the Multinomial in Relative Entropy”, arXiv:1904.02291 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.