Discrete probability algorithms

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?

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$

Dynamic programming (and/or Stackoverflow) is your friend. You can easily calculate the probabilities of all the outcomes of the first coin flip, and you can easily move from the probabilities of all the outcomes of the first n coin flips to the probabilities of all the outcomes of the first n+1 coin flips (it's a linear transformation).