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


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]



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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.