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

### September 29, 2011

Let *B _{i}, i = 1, …, n* be independent Bernoulli variables with parameters

*q*, respectively. Let

_{i}, i = 1, …, n*S*be their sum. For convenience, assume

*q*. I wish to bound tightly from above the probability that

_{1}≥ q_{2}≥ ··· ≥ q_{n}*S*is greater or equal to some

*l*, having the bound depend solely on

*.*

**E**S = q_{1}+ ··· + q_{n}Clearly, if *l ≤ ES*, then the tightest bound is *1*. This is attained by setting *q _{1} = ··· = q_{l} = 1*.

This example shows that while the variance of *S* is maximized by setting *q _{i} = ES / n, i = 1, ···, n*, at least for some values,

*l*,

*P(S ≥ l)*is maximized by having the

*B*not identically distributed.

_{i}##### Proposition 1:

For every *l*, *P(S ≥ l)* is maximized when *q _{1} = ··· = q_{mo} = 1, q_{mo+1} = ··· = q_{n-mz} = q, and q_{n-mz+1} = ··· = q_{n} = 0*, for some

*m*and

_{o}*m*, and for

_{z}*q = (*.

**E**S – m_{o}) / (n – m_{o}– m_{z})##### Proof:

Assume that *1 > q _{i} > q_{j} > 0*. Let

*S’ = S – B*. Then

_{i}– B_{j}*P(S ≥ l) = P(S’ ≥ l) + p _{1} (q_{i} + q_{j} – q_{i} q_{j}) + p_{2} q_{i} q_{j}*,

where *p _{1} = P(S’ = l – 1)* and

*p*. Thus, keeping

_{2}= P(S’ = l – 2)*q*fixed, but varying the proportion between them,

_{i}+ q_{j}*P(S ≥ l)*is a linear function of

*q*. Unless

_{i}q_{j}*p*,

_{1}= p_{2}*P(S ≥ l)*will be increased by varying

*q*– with a maximum either when they are equal or when one of them is zero or one.

_{i}and q_{j}Therefore, *P(S ≥ l)* cannot be at a maximum if there exist *1 > q _{i} > q_{j} > 0*, unless

*p*. But in that case, the same probability can be achieved by setting the parameter of

_{1}= p_{2}*B*to be

_{i}*q’*(if

_{i}= 0*q*(otherwise), and the parameter of

_{i}+ q_{j}< 1) or q’_{i}= 1*B*to be

_{j}*q’*. Therefore, in that case, there would exist a set of parameters,

_{j}= q_{i}+ q_{j}– q’_{i}*q’*, that would achieve that same probability but with fewer parameters that are not equal to zero or one. Thus, in the set of parameter settings maximizing

_{1}, …, q’_{n}*P(S ≥ l)*, there exists a solution – namely the one which maximizes the number of parameters with extreme values (zeros and ones) – in which there is only one non-extreme value. ¤

The next step is to investigate which specific parameter setting correspond to various combinations of *l* and * ES*.