Lets say we have n coins and probability of Coin i to fall heads is f(i) . Find the probability of getting even number of heads when all the n coins are tossed.

f(i) = 1 / (2i + 3)

Here n is large, of the order of 1e5, so efficient approach is required.

I tried to analyse the brute force case but that would be too much i.e. If I calculate for 2 success, 4, 6..., it might take years to run.

Then I thought of applying Linearity of Expectation somehow but couldn't come up with anything which could help. ​​

  • $\begingroup$ With a large number of flips the probability will approach $\frac 12$ regardless of the bias. $\endgroup$ – Doug M Jan 25 '18 at 19:01

There is a simple recurrence equality which is provable by induction.

Deduce one from the fact that (denoting $H_n$ the $n$-th instance of your problem) $$P(H_n) = p_n\cdot P(\neg H_{n-1})+ (1-p_n) \cdot P(H_{n-1})$$

This allows you to iteratively compute $P(H_n)$. Simplify this to a closed form.

  • $\begingroup$ Forgive me if I missed by a mile but is it (n + 5) / (2n + 3)? Thanks. $\endgroup$ – Kunwar Singh Jan 25 '18 at 20:11
  • $\begingroup$ @KunwarSingh For $n=1$ the Formula is wrong. Can you find the starting Value and simplify the recurrence to a linear recurrence equation ($P(H_1):=P_1=?$ and $P_n=a(n) + b(n)P_{n-1}$)? $\endgroup$ – AlexR Jan 25 '18 at 20:52
  • $\begingroup$ Got it, its (n + 3) / (2n + 3)! $\endgroup$ – Kunwar Singh Jan 25 '18 at 22:29

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.