A clean upper bound for the expectation of a function of a binomial random variable 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)$.
 A: 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.
A: 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.
A: 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$. 
