In a problem I'm working on, I have Bernoulli random variables $X_1,X_2,\dots,X_k$ ($k$ is odd) and I am interested in their sum $Y = \sum_{i=1}^k X_i$. In this problem, $P(X_i=1) = p_i$ and $P(X_i=0) = 1-p_i$. Each $X_i$ is independent, but not all are identically distributed, so $Y$ follows a Poisson Binomial Distribution. Assume a lower bound $\alpha>0.5$ on $\{p_i\}_{i=1}^k$.

I am interested in the upper bound of $P(Y < \frac{k}{2})$. Two existing questions address a similar problem, with the first link bounding the tail probabilities using the Binomial Distribution. However, I couldn't find any sources online that explained more about this bounding technique.

Any reference material regarding bounding the PBD with the Binomial Distribution would be greatly appreciated.


1 Answer 1


I've updated my answer to this question to include the formal statement and proof. The work is currently under (non-blind) review, but when the bibliographical information is available I'll add that as well (might be a few months). I hope this helps!

  • $\begingroup$ Thanks Stefan - I'm happy to talk more about this! I can't comment on your answer that you linked because I don't have enough reputation points, but if you could follow then message me on Twitter, I'll give you my email and we can chat. $\endgroup$
    – teoh
    Commented Jan 15, 2017 at 5:20
  • $\begingroup$ I don't have a twitter, but you can reach me at stefantj [at] stanford.edu $\endgroup$
    – combo
    Commented Jan 16, 2017 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.