A sharp estimate of the binomial mean absolute deviation with applications

We give simple, sharp non-asymptotic bounds on the mean absolute deviation (MAD) of a Bin(n,p) random variable. Although MAD is known to behave asymptotically as the standard deviation, the convergence is not uniform over the range of pp and fails at the endpoints. Our estimates hold for all p∈[0,1]p∈[0,1] and illustrate a simple transition from the “linear” regime near the endpoints to the “square root” regime elsewhere. As an application, we provide asymptotically optimal tail estimates of the total variation distance between the empirical and the true distributions over countable sets.