A clean upper bound for the expectation of a function of a binomial random variable

Question

I wonder if there is a closed-form, or clean upper bound of this quantity: $\mathbb{E}[|X/n-p|]$, where $X\sim B(n,p)$.

Answer 1

This is the mean absolute deviation (MAD) for a binomial distribution, divided by $n$. The expectation is hence $$2 \, (1-p)^{n+1-\lceil np \rceil} \, p^{\lceil np \rceil} \, \binom{n-1}{\lceil np \rceil-1} \;.$$ See this paper (Berend & Kontorovich 2013, doi: 10.1016/j.spl.2013.01.023) for bounds and a reference for the above expression.

Answer 2

Here is a confident guess, without a proof.

The normal approximation of the binomial distribution gives the estimate $$ f(n,p) = \frac{\sqrt{2pq}}{\sqrt{\pi n}}.$$

Now, experimentally, for any fixed $n$ the maximum of $$ \frac{\mathbb{E}\, |X/n-p\,|}{f(n,p)}$$ occurs at $p=\frac1{2n}$, where it equals $$ c(n) = 2^{-n+1/2} (2n-1)^{n-1/2} n^{-n+1/2}\sqrt{\pi}.$$ Note that $c(1)=\sqrt{\pi/2}$ and $c(n)$ is decreasing with limit $c(\infty)=\sqrt{\pi/e}$.

If this is true, then a simple bound, sharp within a constant, is $$\mathbb{E}\, |X/n-p\,|\le c(n)\,f(n,p) \le \frac{\sqrt{pq}}{\sqrt{n}}.$$

A proof would show that there is a local maximum at each $p=\frac{2k+1}{2n}$ then identify $k=1$ as the largest. It shouldn't be impossibly difficult.

Hmmm, I just realised that $$\mathbb{E}\, |X/n-p\,|\le \sqrt{\mathbb{E}\, (X/n-p)^2} = \frac{\sqrt{pq}}{\sqrt{n}},$$ so the only interesting thing is that it is quite sharp.

Answer 3

It follows from so-called global central limit theorems (see e.g. Corollary 1, part 1), on page 2 of "Download preview PDF.") that $$\bigg|E\Big|\frac Xn-p\Big|-\sqrt\frac2\pi\,\sqrt{\frac{pq}n}\bigg|<\frac Cn$$ for some absolute real constant $C$ and all natural $n$.