3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thank you very much! Can you confirm that by $[m]$ you mean all integers from 1 to $m$? $\endgroup$ – Corrado Nov 24 '17 at 10:06
  • $\begingroup$ Yes, that's right. $\endgroup$ – Yuval Filmus Nov 24 '17 at 10:09
  • $\begingroup$ 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. $\endgroup$ – Corrado Nov 24 '17 at 14:47
  • $\begingroup$ Alternatively, we can use $q_{m,-1} = 0$. $\endgroup$ – Yuval Filmus Nov 24 '17 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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