Mean absolute deviations for binomial random variables

Update: thanks to Yihong Wu for pointing out a typo in the statement of the result, which then took me months to get around to fixing.

I came across this paper in the Annals of Probability:

Mean absolute deviations of sample means and minimally concentrated binomials
Lutz Mattner

It contains the following cute lemma, which I didn’t know about before. Let S_n have binomial distribution with parameters (n,p). Let b(n,k,p) = \mathbb{P}(S_n = k). The first two parts of the lemma are given below.

Lemma. We have the following:

  1. k_0 \in \arg\max_{k \in \{0,\ldots, n\}} b(n,k,p) if and only if k_0 \in \{0,\ldots, n\} and (n+1)p - 1 \le k_0 \le (n+1) p.
  2. (De Moivre’s mean absolute deviation equality) \sum_{k=0}^{n} |k - np| b(n,k,p) = 2 v (1-p) \max_{k \in \{0,\ldots, n-1\}} b(n-1,k,p), where v is the unique integer between np < v \le np + 1.

The second part, which was new to me (perhaps I’ve been too sheltered), is also in a lovely paper from 1991 by Persi Diaconis and Sandy Zabell : “Closed Form Summation for Classical Distributions: Variations on a Theme of De Moivre,” in Statistical Science. Note that the sum in the second part is nothing more than \mathbb{E}|S_n - np|. Using this result, De Moivre proved that \lim_{n \to \infty} \mathbb{E}|S_n/n - p| \to 0, which implied (to him) that

if after taking a great number of experiments, it should be perceived that the happenings and failings have been nearly in a certain proportion, such as of 2 to 1, it may safely be concluded that the probabilities of happening or failing at any one time assigned will be very near in that proportion, and that the greater the number of experiments has been, so much nearer the truth will the conjectures be that are derived from them.

Diaconis and Zabell show the origins of this lemma, which leads to De Moivre’s result on the normal approximation to the binomial distribution. As for the proof of the L_1 convergence, they call the proof in the p = 1/2 case “simple but clever, impressive if only because of the notational infirmities of the day.” De Moivre’s proof was in Latin, but you can read a translation in their paper. A simple proof for rational p was given by Todhunter in 1865.

For those with an interest in probability with a dash of history to go along, the paper is a fun read.


5 thoughts on “Mean absolute deviations for binomial random variables

  1. Weird, I recognize one of those names. Persi Diaconis spoke at that conference Robbie was at MSRI for.

    I do not understand any other words in this post.

  2. Pingback: more binomial MADness « An Ergodic Walk

Comments are closed.