Deviations from the mean of a sum of independent, non-identically-distributed Bernoulli variables
September 29, 2011
Let Bi, i = 1, …, n be independent Bernoulli variables with parameters qi, i = 1, …, n, respectively. Let S be their sum. For convenience, assume q1 ≥ q2 ≥ ··· ≥ qn. I wish to bound tightly from above the probability that S is greater or equal to some l, having the bound depend solely on ES = q1 + ··· + qn.
Clearly, if l ≤ ES, then the tightest bound is 1. This is attained by setting q1 = ··· = ql = 1.
This example shows that while the variance of S is maximized by setting qi = ES / n, i = 1, ···, n, at least for some values, l, P(S ≥ l) is maximized by having the Bi not identically distributed.
Proposition 1:
For every l, P(S ≥ l) is maximized when q1 = ··· = qmo = 1, qmo+1 = ··· = qn-mz = q, and qn-mz+1 = ··· = qn = 0, for some mo and mz, and for q = (ES – mo) / (n – mo – mz).
Proof:
Assume that 1 > qi > qj > 0. Let S’ = S – Bi – Bj. Then
P(S ≥ l) = P(S’ ≥ l) + p1 (qi + qj – qi qj) + p2 qi qj,
where p1 = P(S’ = l – 1) and p2 = P(S’ = l – 2). Thus, keeping qi + qj fixed, but varying the proportion between them, P(S ≥ l) is a linear function of qi qj. Unless p1 = p2, P(S ≥ l) will be increased by varying qi and qj – with a maximum either when they are equal or when one of them is zero or one.
Therefore, P(S ≥ l) cannot be at a maximum if there exist 1 > qi > qj > 0, unless p1 = p2. But in that case, the same probability can be achieved by setting the parameter of Bi to be q’i = 0 (if qi + qj < 1) or q’i = 1 (otherwise), and the parameter of Bj to be q’j = qi + qj – q’i. Therefore, in that case, there would exist a set of parameters, q’1, …, q’n, 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 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.
October 4, 2011 at 4:24 am
Interesting post, Yoram, looking forward to the continuation. Was this inspired by a real-life problem?
October 7, 2011 at 11:42 am
Hi Arkadas,
Thanks for your interest.
This is connected in some way to my 2008 EJS paper, Rigorous LCB for the expectation of a positive r.v..
In that paper I assumed that a sample from a set of IID r.v.’s is available. I have been trying (on-and-off) to extend the treatment to handling a sample from a set of independent non-ID r.v.’s. The real life application would be similar to the one in the paper – survey sampling – but would allow handling stratified sampling.
October 9, 2011 at 3:29 pm
Thanks, Yoram. I’ve read your paper (skipping the proofs), and learned quite a bit. It looks like a fundamental contribution—I am surprised that there are still research opportunities on such basic problems. This also got me curious about the original studies on Iraq war casualties, I’ve just checked the Wikipedia page, which was huge.
October 13, 2011 at 8:51 am
I am also rather perplexed with the fact that basic questions are still open while the journals are filled with esoteric papers.
I was half expecting the editor of EJS to return my paper saying that I was covering some well-known ground, but clearly he was unfamiliar with such prior work. Also, I guess Mark var der Laan – a well respected Berkeley professor – would not have put forward his rather absurd argument in the note I refer to in paper had he been aware that a rigorous finite sample LCB can be constructed.
I would still not be that surprised if it turns out that a similar result was published before, but even if this is the case, the mere fact that two active academic statisticians were not aware of such existing work is puzzling.
The area of independent but not identically distributed variables also seems to be under-researched, I think. It is a natural extension of the classical IID setup. Again, maybe I am just not aware of existing literature, but even if this is the case, it is surprising that it is not part of the standard textbook material.
October 29, 2011 at 12:49 pm
[...] the investigation initiated here, and applying the same [...]