# Getting K heads out of N biased coins problem (formula generation ).

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?

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]

Let

$$P(x) = (q_1 + p_1 x)(q_2 + p_2 x) \cdots (q_n + p_n x)$$

with $q_i=1-p_i$. The coefficient of the term $x^k$ comes from picking, from each factor, $k$ terms of the form $p_i x$ and $n-k$ termns of the form $q_i$ . Hence

$$a_{n,k} = \sum_{S_{n,k}} \prod_{j\in S_{n,k}} p_j \prod_{ \ell \notin S_{n,k}} q_\ell$$ where $S_{n,k}$ are all the subsets of size $k$ of $\{1, 2 \cdots n\}$

I don't see if this can be simplified. To compute it recursively , divide the subsets into those which include $n$ and those which don't. Then

$$a_{n,k} = p_n a_{n-1,k-1} + (1-p_n) a_{n-1,k}$$

But, of course this could be obtained more straightforwardly by the probabilistic approach - which you have already used, probably.

$$P(X_1 + X_2 + \cdots +X_n=k)=\\=P(X_1 + X_2 + \cdots +X_{n-1}=k-1) P(X_n=1) +\\+ P(X_1 + X_2 + \cdots +X_{n-1}=k) P(X_n=0)$$