2

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.

Community
  • 1
teoh
  • 21

1 Answers1

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!

Community
  • 1
combo
  • 1,257
  • 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. – teoh Jan 15 '17 at 05:20
  • I don't have a twitter, but you can reach me at stefantj [at] stanford.edu – combo Jan 16 '17 at 16:18