I have a probability problem, which I need to simulate in a reasonable amount of time. In its simplified form, I have 30 unfair coins each with a different known probability of being heads. I then want to answer such questions as *what is the probability that exactly 12 will be heads?* and *what is the probability that AT LEAST five will be tails?*


I know basic probability theory, so I know that I can enumerate all ${{30} \choose x}$ possibilities, but that's not efficient. The worst case—${{30} \choose {15}}$—exceeds 150 million combinations. Is there a better computational approach to this problem?



Discrete probability algorithms
Suppose the probability for getting head is $p\_i$ for $i$th coin.


You can easily (and economically) compute the probabilities of exactly $k$ heads using the recursive relation -


$H\_{n,k}=p\_nH\_{n-1,k-1}+(1-p\_n)H\_{n-1,k}$




---


Explanation follows.


Let $H\_{n,k}$ be the probability of getting exactly $k$ heads using the first $n$ coins. For answering the type of questions you want to solve, all you need is a list of $H\_{n,k}$'s.


Note that $H\_{n,k}=\sum\_{\left[over\ e\_i's\in\{0,1\},\sum\_i^n e\_i=k\right]}\prod\_{i=1}^n p\_i^{e\_i}(1-p\_i)^{1-e\_i}$


The sum (as you mentioned) contains $n\choose k$ entries.


However note that $H\_{n,k}=p\_nH\_{n-1,k-1}+(1-p\_n)H\_{n-1,k}$


So you can recursively build up the $H\_{n,k}$'s which should be simple since there are only a few of them. (To be precise, for $N$ coins, there are $N(N+3)/2$ many of $H\_{n,k}$'s since $n\in \{1,...,N\}$ and $k\in \{0,...,n\}$).


As a base for the recursive relation, you can use the following (obvious) identities.


* $H\_{n,k}=0$ for $k\gt n$
* $H\_{n,0}=\prod\_{i=1}^n(1-p\_i)$
* $H\_{n,n}=\prod\_{i=1}^np\_i$


