Probability – Probability of Getting ‘k’ Heads with ‘n’ Coins

probability

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 ?

Best Answer

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

Related Question