Skip to main content
1 of 3
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

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)=e^{-1/2}\sqrt{\pi}$.

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.

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147