Deviations from the mean of a sum of independent, non-identically-distributed Bernoulli variables, continued
October 29, 2011
Continuing the investigation initiated here, and applying the same notation.
For every l, l >= ES, P(S ≥ l) is maximized when q1 = ··· = qn-mz = q = ES / (n – mz), and qn – mz + 1 = ··· = qn = 0, for some mz.
That is, in the terminology of Proposition 1, for all non-trivial cases, mo = 0, and thus the probability of deviation is maximized by some Bernoulli variable (rather than a shifted Bernoulli variable).
Let ES < l. Let the parameters q1, …, qn be as described in Proposition 1, with mo > 0. Let S’ = S – B1 – Bmo + 1 = S – 1 – Bmo + 1. Then S’ – mo + 1 is a Binomial variable with parameters n’ = n – mo – mz – 1 and q whose expectation is ES – mo – q = (ES – mo) n’ / (n’ + 1).
The density of a Binomial variable with parameters n’ and q is unimodal with a mode smaller or equal to max((n’ + 1) q – 1, 0). Therefore, the density of S’ is unimodal with mode smaller or equal to the maximum of mo – 1 and
mo – 1 + ES’ (n’ + 1) / n’ – 1 = mo – 1 + (ES – mo) – 1 = ES – 2.
Since by assumption ES < l (and therefore mo < l) the mode of the distribution of S’ is lower or equal to l – 2. Thus P(S’ = l – 2) > P(S’ = l – 1) and therefore, following the argument in the proof of Proposition 1, P(S” >= l) > P(S >= l), where S” = S’ + B’1 + B’mo + 1 and B’1 and B’mo + 1 are independent Bernoulli variables both with parameter 1/2. ¤
A similar argument proves
For every l, l > ES + 1, P(S ≥ l) is maximized when q1 = ··· = qn = ES / n.
That is, unless l ≤ ceil(ES), P(S >= l) is maximized by a Binomial variable with parameters n and ES / n. It turns out that the special case that motivated this investigation is indicative of the situation in a rather limited domain. For most cases, the same Bernoulli variable that maximizes the variance of the family under consideration also maximizes the probability of deviation.
Finally, the domain is limited but is not empty.
For l + 2 – 1 / l – (1 + 1 / l)l + 1 < ES, P(Sl >= l) > P(Sl + 1 >= l), where Sl is a Binomial with parameters l and ES / l, and Sl + 1 is a Binomial with parameters l + 1 and ES / (l + 1).
By direct comparison of (ES / l)l and (ES / (l + 1))l + 1 + (l + 1) (ES / (l + 1))l (1 – ES / (l + 1)). ¤
A numerical investigation shows that indeed in the range l – 1 < ES < l, the probability of deviation is maximized by Binomial variables with parameters n and ES / n for some finite n. The diagrams below illustrate the situation (generated for l = 10):
The solid thin lines correspond to a sum of 10 IID Bernoulli variables, while the dashed and dotted lines correspond to sums of 11 and 20 variables, respectively. The thick solid lines correspond to a Poisson variable – the limiting distribution as the number of IID Bernoulli variables in the sum increases indefinitely.
It is worth noting that the same line of argument used above can be used to show that shifted Binomials maximize the density values of sums of independent non-identically distributed Bernoulli variables, i.e., P(S = l).