5

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.

Navin
  • 2,605

3 Answers3

5

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.

lulu
  • 70,402
  • 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
  • Yes i was about to point out that.after one more throw if again head comes it will violate the condition of getting odd number of throws. – Navin Jan 20 '17 at 11:15
  • Right. The logic is "to get odd after $n+1$ I have to either get odd after $n$ and then throw $T$ or get even after $n+1$ and then throw $H$". Sanity check: it should be clear that for large $n$, $P_{n+1}=P_n$ which indeed follows from the corrected recursion. – lulu Jan 20 '17 at 11:17
  • I didnot have the idea of using recursion.It is quite handy for small n.but i am very weak in solving the recursive functions.Can you please throw some light on it. – Navin Jan 20 '17 at 11:21
  • Well, with a machine it's easy to compute these even for respectably large $n$. I don't see a way of getting a simple closed formula out of it, but of course that might be possible. It ought to be possible to prove that $P_n$ tends to $\frac 12$...for example $P_{2000}=.49979182$. Annoyingly, I had a simple proof of this for the incorrect recursion. Can't seem to see it using the correct one. – lulu Jan 20 '17 at 11:26
  • Note: I just solved the recursion. Not a lot of insight to offer...I just looked at the table of values, spotted a pattern, then verified that the recursion held. Note: there was a small bug in my implementation, so in fact $P_{2000}=.49987503$. Doesn't change anything else that I printed. – lulu Jan 20 '17 at 12:00
  • @lulu How do you get 2n+3 in the denominator? Shouldn't it be 2n+1? What am I missing? – Autonomous Sep 08 '17 at 06:31
  • @ParagS.Chandakkar My recursion starts by computing $P_{n+1}$. The probability of the last one being $H$ is $\frac 1{2n+3}$ by assumption. If I am throwing $n+1$ coins, how might I get an odd number of heads? Well, either I get an odd number on the first $n$ and a $T$ on the last (first term) or an even number on the first $n$ and a $H$ on the last. Either way I get a term involving $P_n$ times a term involving $\frac 1{2n+3}$. – lulu Sep 08 '17 at 10:37
  • @lulu My problem is with the assumption. Let me try to explain. Problem says, "If n biased coins are tossed, coin m will show up heads with probability $\frac{1}{2m+1}$". So by this logic, the probability of the last coin to show up heads would be $\frac{1}{2n+1}$. So, if there was only one coin, then $P_1 = \frac{1}{3}$ that matches what you have written. However, if we consider $2n+3$ in denominator, then $P_1 = \frac{1}{5}$, which is not right. – Autonomous Sep 08 '17 at 14:01
  • 1
    @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 09 '17 at 10:48
5

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

leonbloy
  • 63,430
  • 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
0

Here is an interesting solution from https://imomath.com/index.php?options=585 , Problem 2:

Let

$$f(x)=\prod\limits_{k=1}^{n}\left(1-\frac{1}{2k+1}+\frac{x}{2k+1}\right)=a_0+a_1x+a_2x^2+\dots+a_nx^n$$

Then $a_k$ is the probability of getting exactly k heads when these n coins are tossed.

Note that $f(1)=a_0+a_1+a_2+a_3+\dots$, $f(-1)=a_0-a_1+a_2-a_3+\dots$, so the probability of getting an odd number of heads is equal to:

$$a_1+a_3+\dots=\frac{f(1)-f(-1)}{2}=\frac{1}{2}\left[1-\prod\limits_{k=1}^{n}\left(1-\frac{2}{2k+1}\right)\right]=\frac{1}{2}\left(1-\frac{1}{3}\frac{3}{5}\dots\frac{2n-1}{2n+1}\right)=\frac{n}{2n+1}$$

auntyellow
  • 579