Question

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! :-)

Answer 1

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$

Answer 2

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