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