I threw a coin n times, and never got three tails in a row. I calculated the odds of this event, and found out they were just about even; 50%-50%. How many times did I throw the coin?

A second question: what were the chances of having not gotten three heads in a row either?

(In reply to Markov chain solution - 2nd part by Old Original Oskar!)

You say
P(i+1,HH)=0.5xP(i,HH)
but I assume you mean
P(i+1,HH)=0.5xP(i,H)

There's a problem overall in the interaction of the T's and H's. Each next generation's probability of having completed a TTT depends in part on the previous generation's ending in TT, which in turn depends on the generation-before-that's ending in T, in which you include only the previous generation's H and HH.  However, even sequences that had completed their H's can go on to complete their T's.  The H and HH values include only those that have not completed their H's.

The problem arises from the mixed type of definition: H and HH refer to terminal single and pair values, while HHH refers to triples anywhere within the sequence, and similarly for T, TT and TTT.

If you carry your calculations for many generations you will see that P(i,TTT) approaches 1/2 and P(i,HHH) approaches 1/2, when they should each approach 1.

i    h       hh       hhh        t       tt      ttt
 1 0.500000 0.000000 0.000000 0.500000 0.000000 0.000000
 2 0.250000 0.250000 0.000000 0.250000 0.250000 0.000000
 3 0.250000 0.125000 0.125000 0.250000 0.125000 0.125000
 4 0.187500 0.125000 0.187500 0.187500 0.125000 0.187500
 5 0.156250 0.093750 0.250000 0.156250 0.093750 0.250000
 6 0.125000 0.078125 0.296875 0.125000 0.078125 0.296875
 7 0.101563 0.062500 0.335938 0.101563 0.062500 0.335938
 8 0.082031 0.050781 0.367188 0.082031 0.050781 0.367188
 9 0.066406 0.041016 0.392578 0.066406 0.041016 0.392578
10 0.053711 0.033203 0.413086 0.053711 0.033203 0.413086
11 0.043457 0.026855 0.429688 0.043457 0.026855 0.429688
12 0.035156 0.021729 0.443115 0.035156 0.021729 0.443115
13 0.028442 0.017578 0.453979 0.028442 0.017578 0.453979
14 0.023010 0.014221 0.462769 0.023010 0.014221 0.462769
15 0.018616 0.011505 0.469879 0.018616 0.011505 0.469879
16 0.015060 0.009308 0.475632 0.015060 0.009308 0.475632
17 0.012184 0.007530 0.480286 0.012184 0.007530 0.480286
18 0.009857 0.006092 0.484051 0.009857 0.006092 0.484051
19 0.007975 0.004929 0.487097 0.007975 0.004929 0.487097
20 0.006452 0.003987 0.489561 0.006452 0.003987 0.489561
21 0.005219 0.003226 0.491555 0.005219 0.003226 0.491555
22 0.004223 0.002610 0.493168 0.004223 0.002610 0.493168
23 0.003416 0.002111 0.494473 0.003416 0.002111 0.494473
24 0.002764 0.001708 0.495528 0.002764 0.001708 0.495528
25 0.002236 0.001382 0.496382 0.002236 0.001382 0.496382
26 0.001809 0.001118 0.497073 0.001809 0.001118 0.497073
27 0.001463 0.000904 0.497632 0.001463 0.000904 0.497632
28 0.001184 0.000732 0.498084 0.001184 0.000732 0.498084
29 0.000958 0.000592 0.498450 0.000958 0.000592 0.498450
30 0.000775 0.000479 0.498746 0.000775 0.000479 0.498746
31 0.000627 0.000387 0.498986 0.000627 0.000387 0.498986
32 0.000507 0.000313 0.499179 0.000507 0.000313 0.499179
33 0.000410 0.000254 0.499336 0.000410 0.000254 0.499336
34 0.000332 0.000205 0.499463 0.000332 0.000205 0.499463
35 0.000269 0.000166 0.499565 0.000269 0.000166 0.499565
36 0.000217 0.000134 0.499648 0.000217 0.000134 0.499648
37 0.000176 0.000109 0.499716 0.000176 0.000109 0.499716
38 0.000142 0.000088 0.499770 0.000142 0.000088 0.499770
39 0.000115 0.000071 0.499814 0.000115 0.000071 0.499814

In fact, by these lights, the .413 observed for p(10,ttt) indicates you have not reached the approximately 50% mark, and in fact would only approach that after larger numbers of tosses.

Posted by Charlie on 2004-06-13 00:40:26