I have 20 independent events with unequal probabilities and need to programmatically determine the probability of exactly x of the events occurring. Are there any elegant solutions to this type of problem?

Here's an example of a case: I want to know the probability of 3 events occurring: prob of event 1 = 0.432, prob of event 2 = 0.012, prob of event 3 = 0.001, prob of event 4 = 0, prob of event 5 = 0, prob of event 6 = 0.012...

  • $\begingroup$ What are the probabilities and what is the value of $x$? $\endgroup$ – barak manos Nov 17 '16 at 17:15
  • $\begingroup$ Do you know about probability generating functions? Those could give a very elegant way of doing it. $\endgroup$ – Hugo Berndsen Nov 17 '16 at 17:15
  • $\begingroup$ @HugoBerndsen, I do not, do you have a good resource to learn about them? $\endgroup$ – Danneskjöld Nov 17 '16 at 17:23
  • $\begingroup$ @barakmanos, I added an example to my question. $\endgroup$ – Danneskjöld Nov 17 '16 at 17:23
  • $\begingroup$ You can split it into disjoint cases (each case consisting of $3$ events), calculate the probability of each case (a product of the $3$ events of that case), and add up the results. For $3$ out of $20$ events, you have $1140$ cases. I might be able to give you a Python script. $\endgroup$ – barak manos Nov 17 '16 at 17:33

Well, if I understand your comments correctly, you have Bernoulli variables. So they either happen or do not happen with a certain chance $p_i$.

The not-elegant but straightforward way is to use a convolution, specifically if $X_i$ is the stochastic variable for the $i^\text{th}$ event, with \begin{equation} P(X_i=1)=p_i \qquad \text{and} \qquad P(X_i=0)=q_i=(1-p_i). \end{equation} The chance that $n$ of the events happen is written as \begin{equation} P(\sum_i X_i=n)=\sum_{S} \prod_{i\in S} p_i, \end{equation} where $S$ are all selections of subsets of length $n$ from your set of events.

The elegant way could use probability generating functions. These are power series defined as \begin{equation} G(z)=P(X=0)+P(X=1)z +P(X=2)z^2 +\ldots \end{equation} For your Bernoulli problem this is pretty easy: \begin{equation} G(z)_i=(1-p_i)+p_i z \end{equation} This is then the probability generating function for the $i^\text{th}$ event. This function can now basically be seen as a nice way to group your chances. But now the nice part comes in. If you want to calculate probabilities for the sum of stochastic variables, you can just take the product of their probability generating functions!

So, you now get \begin{equation} G(z)_{\text{sum}} = \prod_i G(z)_i = \prod_i \left((1-p_i)+p_iz\right). \label{gener} \end{equation}

Now you have found the PGF for the sum. The only thing you still have to do is find your probabilities back from the sum. So, you have a power series and you need the coefficients. You can do this by taking derivatives: \begin{equation} P(\sum_i X_i=n)=\frac{1}{n!} G^{(n)}(0)_{\text{sum}}, \end{equation} where you thus have to take the $n$th derivative of the previous function. You can do this by using a product rule.

Does this help? I hope that you at least found it interesting. You can read more about it at this site.


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.