# Polynomial Computation of the probability of a number of independent events

Suppose to have $n$ independent events $E_1, E_2,..., E_n$, where the probability of occurrence of event $E_i$ is $p_i$ (i.e., each event has its own probability of occurrence). We can easily define new events of type $N_k\equiv$"exactly $k$ events occur".

The probability of event $N_k$ can be computed as $$\Pr(N_k) = \sum_{I \in \mathcal{I_{n,k}}}\prod_{i \in I}p_i \prod_{i \notin I} (1-p_i)$$ where $\mathcal{I_{n,k}} = \lbrace I \subseteq \lbrace 1,2,\ldots,n \rbrace :|I|=k \rbrace$. However, this calculation requires exponential time w.r.t. $n$.

Is there an algorithm with polynomial time complexity w.r.t. $n$ to compute the probability of each $N_k$, for $k=0,1,...,n$?

You can use dynamic programming. For parameters $m,\ell$, define $$q_{m,\ell} = \sum_{I \in \cal I_{m,\ell}} \prod_{i \in I} p_i \prod_{i \in [m] \setminus I} (1-p_i).$$ This satisfies the recurrence $$q_{m,\ell} = p_m q_{m-1,\ell-1} + (1-p_m)q_{m-1,\ell}$$ with initial values $q_{0,0} = 1$ and $q_{m,\ell} = 0$ for $\ell < 0$ and $\ell > m$. This gives an $O(n^2)$ time algorithm.
The same idea can be expressed using generating functions: $$\prod_{i=1}^n (1-p_i + p_i x) = \sum_{k=0}^n \Pr(N_k) x^k.$$
• thank you very much! Can you confirm that by $[m]$ you mean all integers from 1 to $m$? – Corrado Nov 24 '17 at 10:06
• I think the following additional axioms must be added: $q_{m,0}=\prod_{i=1}^{m}(1-p_i)$ for $m>0$ and $q_{m,\ell}=0$ for $\ell>m$, then the problem is solved. – Corrado Nov 24 '17 at 14:47
• Alternatively, we can use $q_{m,-1} = 0$. – Yuval Filmus Nov 24 '17 at 14:51