Deviations from the mean of a sum of independent, non-identically-distributed Bernoulli variables, continued

Continuing the investigation initiated here, and applying the same notation.

Proposition 2:

For every l, l >= ES, P(S ≥ l) is maximized when q₁ = ··· = q_n-mz = q = ES / (n – m_z), and q_{n – mz + 1} = ··· = q_n = 0, for some m_z.

That is, in the terminology of Proposition 1, for all non-trivial cases, m_o = 0, and thus the probability of deviation is maximized by some Bernoulli variable (rather than a shifted Bernoulli variable).

Proof:

Let ES < l. Let the parameters q₁, …, q_n be as described in Proposition 1, with m_o > 0. Let S’ = S – B₁ – B_{mo + 1} = S – 1 – B_{mo + 1}. Then S’ – m_o + 1 is a Binomial variable with parameters n’ = n – m_o – m_z – 1 and q whose expectation is ES – m_o – q = (ES – m_o) 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 m_o – 1 and

m_o – 1 + ES’ (n’ + 1) / n’ – 1 = m_o – 1 + (ES – m_o) – 1 = ES – 2.

Since by assumption ES < l (and therefore m_o < 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’₁ + B’_{mo + 1} and B’₁ and B’_{mo + 1} are independent Bernoulli variables both with parameter 1/2. ¤

A similar argument proves

Proposition 3:

For every l, l > ES + 1, P(S ≥ l) is maximized when q₁ = ··· = q_n = 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.

Proposition 4:

For l + 2 – 1 / l – (1 + 1 / l)^{l + 1} < ES, P(S_l >= l) > P(S_{l + 1} >= l), where S_l is a Binomial with parameters l and ES / l, and S_{l + 1} is a Binomial with parameters l + 1 and ES / (l + 1).

Proof:

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).

Advertisement