[Math] Getting K heads out of N biased coins problem (formula generation ).

polynomialsprobability

Problem-

Given a set of coins $n$ with each coin $i$ having $P_i$ probability to give heads. Find the probability of getting $k$ heads, when all coins are tossed together.

Hi I have solved this problem recursively and and also generate the polynomial in which the coefficient of the $x^k$ is the required probability but I am not able to find a general formula for this coefficient

$$[(1−P)1)+P_1x]\cdot[(1−P_2)+P_2x]\cdots[(1−P_n)+P_nx]$$

What will be the coefficient of $x^k$ in above polynomial?

Best Answer

You can use Dynamic Programming as Nth turn's outcome is mutually independent to N-1th 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]*(1 - P[n]) + dp[n - 1][k - 1]*p[n]

Related Question