I posted earlier about the mean absolute deviation (MAD) of a binomial variable with parameters . Here’s a little follow-up with plots. This is a plot of versus for different values of .
The first is for . Looks beautifully scalloped, no? As we’d expect, the MAD is symmetric about 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.
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 samples from a Bernoulli variable with parameter , then the empirical distribution (unnormalized) is . So 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.