# Probability of getting an odd number of heads if n biased coins are tossed once.

The question is basically to find out the probability of getting odd number of heads when $n$ biased coins,with $m^{th}$ coin having probability of throwing head equal to $\frac{1}{2m+1}$ ($m=1,2,\cdots,n$) are tossed once.The results for each coin are independent.

If we consider first that only one head turns up.The probability then is equal to $$\sum_{m=1}^{n} [\frac{1}{2m+1} \prod_{k=1,k \neq m}^{n} (1-\frac{1}{2k+1})]$$ which seems very difficult to evaluate.It gets more complicated if we increase the number of heads.I couldnot find out a simple way to do this.Any suggestion would be highly appreciated.Thanks.

We work recursively. Let $P_n$ denote the answer if there are $n$ coins. Of course $P_1=\frac 13$. Considering the toss of the last coin we see that $$P_{n+1}=P_n\times \left(1-\frac 1{2n+3}\right)+(1-P_n)\times \frac 1{2n+3}=P_n\times \left(1-\frac 2{2n+3}\right)+\frac 1{2n+3}$$

This can be solved in closed form. We get $$P_n=\frac n{2n+1}$$

Not a lot of insight to offer on that...I just looked at the table, saw the pattern, then mechanically showed that the expression satisfied the recursion. Of course, the simplicity of the final form suggests that there might be a direct argument for it.

• Thanks for your answer.But what exactly do you mean by $P_n$ .Since you have written $P_1=3$ i think you mean by the probability of nth coin showing head.What is then the objective of finding $P_{n+1}$. It is already known. – Navin Jan 20 '17 at 10:59
• I defined it. $P_n$ is the answer to your question if there are $n$ coins. That is, $P_n$ is the probability that the toss of $n$ of your biased coins will yield an odd number of $H's$. – lulu Jan 20 '17 at 11:00
• Sorry i got it. – Navin Jan 20 '17 at 11:04
• Note: there's was an algebraic error in my recursion. I'll correct it now. – lulu Jan 20 '17 at 11:12
• @ParagS.Chandakkar Well, what's my last coin? It is $P_{n+1}$. So, the probability that is comes up $H$ is $\frac 1{2(n+1)+1}=\frac 1{2n+3}$. – lulu Sep 9 '17 at 10:48

A note for solving lulu's recursion

We have $$P_{n+1}=P_n \left(1-\frac 2{2n+3}\right)+\frac 1{2n+3}= P_n \frac{2n+1}{2n+3} + \frac 1{2n+3}$$

with $P_0 =0$

Multiplying by $2n+3$:

$$P_{n+1} (2n+3)=P_{n+1}(2 (n+1)+1)=P_n \left({2n+1}\right)+1$$

Calling $A_n = P_n (2n+1)$ this gives

$$A_{n+1}=A_n+1$$

with $A_0=0$. Of course, this implies $A_n=n$ and hence

$$P_n = \frac{n}{2n+1}$$

• Thank you. Try as I might, I can't see this simple form directly. As a probability I mean. Surely there's some way to avoid the recursion altogether. – lulu Jan 20 '17 at 12:14
• The recursion method looks fine to me. – leonbloy Jan 20 '17 at 12:26