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