Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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$
share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.