10

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 ?

sonu
  • 712
Kyuubi
  • 345
  • Do you know generating functions? This is easy with that. – Calvin Lin Jun 26 '13 at 05: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 05:22
  • 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 05:27
  • Shouldn't it be $P(n,k) = {n \choose k}Pi^{k}(1-Pi)^{n-k}$? – Sumeet Jun 26 '13 at 05: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 05:38

5 Answers5

7

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

M47145
  • 4,106
pranjuldb
  • 81
3

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

Calvin Lin
  • 68,864
2

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]

Vasu
  • 129
0

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$

bakuda
  • 26
-1

Let F(i,j) be the probability of finding exactly j heads when i biased coins are tossed. and P(i) be the probability of landing head when ith coin is tossed.
The recurrence relation for this problem would look like following : F(i, j) = F(i-1, j) * (1-P(i)) + F(i-1, j-1) * P(i) With the base cases being as written here :- F(1,0) = 1-P(1) and F(1,1) = P(1)

So now the problem reduces to finding value F(n, k) which would give us the probability of finding exactly k heads in n tosses. this can be extended to find at most k heads or atleast k heads also where we have to find the sum of solutions for all j in [0,k] and [k,n] respectively.

Anit Aggarwal
  • 23