# Probability of Outcomes Algorithm

I have a probability problem, which I need to simulate in a reasonable amount of time. In it's simplified form, I have 30 unfair coins each with a different known probability. I then want to ask things like "what is the probability that exactly 12 will be heads?", also "what is the probability that AT LEAST 5 will be tails?".

I know basic probability theory, so I know I can enumerate all (30 choose x) possibilities, but that's not particularly scalable. The worst case (30 choose 15) has over 150 million combinations. Is there a better way to approach this problem from a computational standpoint?

Any help is greatly appreciated, thanks! :-)

-

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