# Probability of getting 'k' heads with 'n' coins

This is an interview question.( http://www.geeksforgeeks.org/directi-interview-set-1/)

Given $n$ biased coins, with each coin giving heads with probability $P_i$, find the probability that on tossing the $n$ coins you will obtain exactly $k$ heads. You have to write the formula for this (i.e. the expression that would give $P (n, k)$).

I can write a recurrence program for this, but how to write the general expression ?

• Do you know generating functions? This is easy with that. – Calvin Lin Jun 26 '13 at 5:15
• I came up with some thing like F(i, x, k) = Pi * F(i+1, x+1, k) +f(i+1, x, k) for all i from 1 to n-k and F(i,k,k) = Pi – Kyuubi Jun 26 '13 at 5:22
• Shouldn't it be $P(n,k) = {n \choose k}Pi^{k}(1-Pi)^{n-k}$? – Sumeet Jun 26 '13 at 5:27
• Can you enumerate all $k-$subsets of $n$? Given any $k-$subset, what's the probability that those corresponding coins show heads and the rest show tails? – Calvin Lin Jun 26 '13 at 5:27
• @CalvinLin : Thats what i tried to do with that recurrence relation. Enumerate all k subset. F(i,x,k) is the probability of getting k heads, given x heads have already occurred till coin i. – Kyuubi Jun 26 '13 at 5:38

Consider the function

$[ (1-P_1) + P_1x] \times [(1-P_2) + P_2 x ] \ldots [(1-P_n) + P_n x ]$

Then, the coefficient of $x^k$ corresponds to the probability that there are exactly $k$ heads.

The coefficient of $x^k$ in this polynomial is $\sum_{k-\mbox{subset} S} [\prod_{i\in{S}} \frac{1-p_i}{p_i} \prod_{j \not \in S} p_j]$

You can use Dynamic Programming as $N$th turn's outcome is mutually independent to $N-1$th and there are two possible cases here :

1. $K$ heads already came in $N-1$ turns
2. $K-1$ heads already came in $N-1$ turns

$dp[i][j]$ : probability of getting $j$ heads in $i$ trials.

So, $dp[n][k] = dp[n - 1][k]\cdot (1 - P[n]) + dp[n - 1][k - 1]\cdot p[n]$

Let us say p = Pi, and q = 1 - Pi. Then the probability of a given sequence, e.g., 100010..., in which k heads appear in n flips e.g pqqqpq... can be given by $$p^k.q^{n-k}$$ There are a total of $2^n$ possible sequences. Only some of these give k heads and n - k tails. Their number is $$\frac{n!}{k! (n-k)!} = {n \choose k}$$ Since any one or another of these sequences will do, the probability that exactly k heads occur in n flips would be $${n \choose k}p^k.q^{n-k}$$ [Source]

• As per OP p is different for different tossing of the coin. – Biswanath Apr 16 '17 at 18:59

For exactly k heads in tossing of n biased coins - there are $^nC_k$ possible sets of coins which must be heads while the others are tails, we hence sum over all these sets.
Let S be a set such that $S \subseteq \{1,2,3,\dots,n\}$ and $|S|=k$, then,
$P(n,k) = \Sigma_{\vee S} \> p_{i_1}p_{i_2}\dots p_{i_k} (1-p_{j_1})(1-p_{j_2})\dots(1-p_{j_{n-k}})$ for $i_{1},i_{2},\dots,i_{k} \in S$ and $j_{1},j_{2},\dots,j_{n-k} \not \in S$