pr.probability - Probability of Outcomes Algorithm

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'sin{0,1},sum_i^n e_i=kright]}prod_{i=1}^n p_i^{e_i}(1-p_i)^{1-e_i}$

The sum (as you mentioned) contains $nchoose 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 $nin {1,...,N}$ and $kin {0,...,n}$).

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

• $H_{n,k}=0$ for $kgt n$


• $H_{n,0}=prod_{i=1}^n(1-p_i)$


• $H_{n,n}=prod_{i=1}^np_i$