7
$\begingroup$

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 ?

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

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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]

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

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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