Asymptotics of the expected distance of a Binomial to its mean

Question

Let $X$ be Binomial with parameters $n$ and $p$. What upper bound depending on both $n$ and $p$ is there for $\mathbb E[|\frac{1}{n}X-p|]$?

Background: I need good control over the asymptotics (in $n$) of the expectation, uniformly in $p$.

Standard: Use the formula in terms of the cdf, then Hoeffding's inequality and the Gaussian integral to get $\mathbb E[|\frac{1}{n}X-p|]\le\sqrt{\frac{\pi}{2n}}$. This bound does not depend on $p$.

Advanced: Replace Hoeffding's inequality by the Chernoff-Hoeffding Theorem. This gives the bound $\mathbb E[|\frac{1}{n}X-p|]\le\int_0^1\exp(-nD(q\|p))\mathrm{d}q$. But how to proceed from here?

Answer 1

I did some research and came up with two bounds. Let $P=\frac{1}{n}X$ be the empirical success probability.

1. Using the Jensen's inequality and the variance we have $\mathbb E[|P-p|]\le\sqrt{\mathrm{Var}(P)}=\sqrt{p(1-p)/n}$.
2. The bound that I initially had in mind can be implemented using the results in this report. Specifically, with $\varphi(p)=\frac{1}{1-2p}\ln(\frac{1-p}{p})$ and $\varphi(0.5)=2$, we have $D(q\|p)\ge\varphi(p)(q-p)^2$. Substituting this bound in the integral in the question and computing the Gaussian integral gives $\mathbb E[|P-p|]\le\sqrt{\frac{\pi}{\varphi(p)n}}$.

Comparing $\sqrt{p(1-p)}$ with $\sqrt{\pi/\varphi(p)}$ yields that the first bound is better throughout.