# Probability of getting even heads in n biased coin tosses with different pi for each coin

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. ​​

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

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.
• @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}$)? – AlexR Jan 25 '18 at 20:52