2

What is the expected number of flips needed to flip a coin 10 times and have the outcome be alternating heads/tails (starting with heads, then tails, then heads etc...).

I wrote a c++ program and it gives me 2,730. Is this correct and how would you do this mathematically?

arslan sana
  • 31

1 Answers1

1

Let $x$ be the expected number of flips to get $(HT)^5$ and $y$ the expected number of further tosses required if we are starting with $XH$ where we cannot use part of $X$ to form the first part of the required run (eg $X$ is empty or ends in $H$).

The first toss is $H$ or $T$, so $x=\frac{1}{2}(1+y)+\frac{1}{2}(1+x)$. Hence $y=x-2$.

How consider the outcomes: $T,HH,(HT)T,(HT)HH,(HT)^2T,(HT)^2HH,\dots,(HT)^4T,(HT)^4HT,(HT)^4HH,(HT)^5$.

They give $$x=\frac{1}{2}(x+1)+\frac{1}{2^2}(y+2)+\frac{1}{2^3}(x+3)+\dots+\frac{1}{2^9}(x+9)+\frac{1}{2^{10}}(y+10)+\frac{1}{2^{10}}10$$ $$=\frac{1}{2}(x+1)+\frac{1}{2^2}x+\frac{1}{2^3}(x+3)+\dots+\frac{1}{2^9}(x+9)+\frac{1}{2^{10}}(x+8)+\frac{1}{2^{10}}10$$ $$=x\left(1-\frac{1}{1024}\right)+\left(\frac{1}{2}+\frac{3}{2^3}+\frac{2}{2^4}+\frac{5}{2^5}+\frac{4}{2^6}+\frac{7}{2^7}+\frac{6}{2^8}+\frac{9}{2^9}+\frac{18}{2^{10}}\right)$$ $$=x\left(1-\frac{1}{1024}\right)\frac{341}{256}$$ So finally $x=1364$.

$\textbf{Comments}$

This is easy to get wrong. I got it wrong, but fortunately @Did picked up the error (see comment below).

The video the OP refers to seems to be about 10 consecutive heads. That case is different because a single $T$ wrecks the run and puts you back to the start. In that case you can consider the outcomes $T,HT,HHT,HHHT,\dots,HHHHHHHHHT,HHHHHHHHHH$. The all but the last (which is a run of 10 heads) put you back to the start. So we have $$x=\frac{1}{2}(x+1)+\frac{1}{4}(x+2)+\dots+\frac{1}{1024}(x+10)+\frac{10}{1024}$$ giving $$\frac{1}{1024}x=\frac{1}{2}+2\left(\frac{1}{2}\right)^2+3\left(\frac{1}{2}\right)^3+\dots+10\left(\frac{1}{2}\right)^{10}+\frac{10}{1024}$$ giving $$x=2046$$

In both cases it is not too difficult to generalise to the case of $n$ flips.

Note that a run of 10 heads or a run of 10 tails are the hardest runs to get because a single wrong flip puts you back to the start, whereas if you are aiming for alternate heads and tails, an unwanted $H$ knocks out your run but gives the first element of a new run. So the 2730 from the $C^{++}$ must be some kind of error.

almagest
  • 18,380
  • 1
    "in either case a single wrong flip puts you back to the start" No, a single wrong flip after HTHT puts you back at the start but a single wrong flip after HTHTH puts you back at H. The mean number of flips to observe $(HT)^n$ is $\frac43(4^n-1)$ (if $n=5$, this is $1364$). – Did Jun 20 '16 at 12:50
  • Actually, now that Im re-watching the video, I think he was calculating the expected # of flips to get 10 heads in a row OR 10 tails in a row OR 10 alternating heads/tails. So would the answer for that be 2046? Im also getting a different answer for 10 consecutive heads in my program. This is strange because I've tested by program against other coin-flip scenarios, and the answer always came up correct. – arslan sana Jun 21 '16 at 01:26
  • @arslansana Is there a reason why you stayed silent when asked for explanations about the specific model you had in mind? – Did Jun 21 '16 at 06:15
  • Sorry what? I clearly explained in OP that im asking about HTHTHT... starting with heads. Re-read my OP. – arslan sana Jun 21 '16 at 06:19
  • I e-mailed the guy form the video and he said that the answer for alternating Heads/Tails should be 2,046, as should be any specific run of 10 flips. My revised c++ program for this also gives me 2,046. – arslan sana Jun 24 '16 at 04:14
  • Unfortunately, the video guy is wrong. Suppose the required flips were HTHTHTHTHH. Suppose you got the first nine correct but then T instead of H, so you had HTHTHTHTHT. Far from being back at the start you have HTHTHTHT, so you only need the next two correct to be done. That is dramatically different from the situation with ten H, where a wrong flip after nine H puts you back at the start. – almagest Jun 24 '16 at 05:35