I'm trying to figure out an algorithm to compute the probability of obtaining at least k successes after N independent events that have different probabilities of success, i.e., the probability of obtaining at least k heads on N coin flips where each flip has its own probability of heads.
I think this is called a Poisson Binomial distribution and I suspect the solution may involve dynamic programming, but I need help getting started.
Best Answer
Indeed this is a Poisson Binomial distribution; let the number of successes be denoted by $X$. Let $p_1,\ldots,p_n$ be the probabilities of success for each of the flips. Denote by $[n]$ the set $\{1,2,\ldots,n\}$ and let $F_k = \{A\subset [n]: |A|=k\}$. Then the probability of having exactly $k$ successes is given by $$ \mathbb P(X=k) = \sum_{A\in F_k}\prod_{i\in A}p_i\prod_{j\in A^c}(1-p_j). $$ So the probability of having at least $k$ successes is given by $$ \mathbb P(X\geqslant k) = \sum_{\ell = k}^n \sum_{A\in F_\ell}\prod_{i\in A}p_i\prod_{j\in A^c}(1-p_j). $$ Note that $|F_k| = \binom nk=\frac{n!}{(n-k)!k!}$ and so $\sum_{k=0}^n |F_k|=2^n$, so computing $\mathbb P(X\geqslant k)$ in this manner may not be computationally feasible. Instead there is the recursive formula $\mathbb P(X=0) = \prod_{i=1}^n (1-p_i)$ and $$ \mathbb P(X=k) = \frac1k \sum_{i=1}^k (-1)^{i-1}\mathbb P(X=k-i)\sum_{j=1}^n \left(\frac{p_j}{1-p_j}\right)^i, k>0, $$ which is derived in this paper: https://www.jstor.org/stable/2683639