I posted earlier about the mean absolute deviation (MAD) of a binomial variable $S_n$ with parameters $(n,p)$. Here’s a little follow-up with plots. This is a plot of $\mathbb{E}|S_n - np|$ versus $p$ for different values of $n$.

The first is for $n = 10$. Looks beautifully scalloped, no? As we’d expect, the MAD is symmetric about $p = 1/2$ and monotonically increasing for the first half of the unit interval. Unfortunately, it’s clearly not concave (although it is piecewise concave), which means I have to do a bit more algebra later on. When $n = 100$ the scallops turn into a finely serrated dome. By the time you get to $n = 1000$ the thing might as well be concave for all that your eye can tell. But you would be deceived. Like a shark’s skin, the tiny denticles can abrade your proof, damaging it beyond repair. Why do I care about this? If you take $n$ samples from a Bernoulli variable with parameter $p$, then the empirical distribution (unnormalized) is $(n - S_n, S_n)$. So $\frac{1}{n} \mathbb{E}|S_n - np|$ is the expected total variational distance between the empirical distribution and its mean. More generally, the expected total variational distance for finite-alphabet distributions is a sum of MAD terms.

1. Juergen Dollinger says:
• Anand Sarwate says: