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 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.
$$

StackExchange Computer Science Q#84327, answer score: 3