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!)

To make this method work, the HHH and TTT states (that we had gotten along the way three heads--or tails--in a row) need to be broken down further, and understood that they exclude the case(s) where both HHH and TTT have been achieved.  Explicitly,

• H means neither HHH nor TTT has been achieved and the sequence ends in H. (understood that the preceding toss is not H)
• HH means neither HHH nor TTT has been achieved and the sequence ends in HH.
• T means neither HHH nor TTT has been achieved and the sequence ends in T.
• TT means neither HHH nor TTT has been achieved and the sequence ends in TT.
• HHHH means HHH has been achieved, TTT has not been achieved and the sequence ends in any number of H's.
• HHHT means HHH has been achieved, TTT has not been achieved and the sequence ends in a single T.
• HHHTT means HHH has been achieved, TTT has not been achieved and the sequence ends in TT.
• TTTT means TTT has been achieved, HHH has not been achieved and the sequence ends in any number of T's.
• TTTH means TTT has been achieved, HHH has not been achieved and the sequence ends in a single H.
• TTTHH means TTT has been achieved, HHH has not been achieved and the sequence ends in HH.

Given the above definitions, the transition probabilities are:

 p(i + 1, hhhh) = .5 * (p(i, hhhh) + p(i, hhht) + p(i, hhhtt)) + .5 * p(i, hh)
 p(i + 1, hhht) = .5 * (p(i, hhhh))
 p(i + 1, hhhtt) = .5 * p(i, hhht)
 p(i + 1, hh) = .5 * p(i, h)
 p(i + 1, h) = .5 * (p(i, t) + p(i, tt))
 p(i + 1, t) = .5 * (p(i, hh) + p(i, h))
 p(i + 1, tt) = .5 * p(i, t)
 p(i + 1, tttt) = .5 * (p(i, tttt) + p(i, ttth) + p(i, ttthh)) + .5 * p(i, tt)
 p(i + 1, ttth) = .5 * (p(i, tttt))
 p(i + 1, ttthh) = .5 * (p(i, ttth))

The results come out:

i    h     hh     hhhh   hhht   hhhtt     t     tt    tttt  ttth   ttthh
 1 0.5000 0.0000 0.0000 0.0000 0.0000 0.5000 0.0000 0.0000 0.0000 0.0000
 2 0.2500 0.2500 0.0000 0.0000 0.0000 0.2500 0.2500 0.0000 0.0000 0.0000
 3 0.2500 0.1250 0.1250 0.0000 0.0000 0.2500 0.1250 0.1250 0.0000 0.0000
 4 0.1875 0.1250 0.1250 0.0625 0.0000 0.1875 0.1250 0.1250 0.0625 0.0000
 5 0.1563 0.0938 0.1563 0.0625 0.0313 0.1563 0.0938 0.1563 0.0625 0.0313
 6 0.1250 0.0781 0.1719 0.0781 0.0313 0.1250 0.0781 0.1719 0.0781 0.0313
 7 0.1016 0.0625 0.1797 0.0859 0.0391 0.1016 0.0625 0.1797 0.0859 0.0391
 8 0.0820 0.0508 0.1836 0.0898 0.0430 0.0820 0.0508 0.1836 0.0898 0.0430
 9 0.0664 0.0410 0.1836 0.0918 0.0449 0.0664 0.0410 0.1836 0.0918 0.0449
10 0.0537 0.0332 0.1807 0.0918 0.0459 0.0537 0.0332 0.1807 0.0918 0.0459
11 0.0435 0.0269 0.1758 0.0903 0.0459 0.0435 0.0269 0.1758 0.0903 0.0459
12 0.0352 0.0217 0.1694 0.0879 0.0452 0.0352 0.0217 0.1694 0.0879 0.0452
13 0.0284 0.0176 0.1621 0.0847 0.0439 0.0284 0.0176 0.1621 0.0847 0.0439
14 0.0230 0.0142 0.1542 0.0811 0.0424 0.0230 0.0142 0.1542 0.0811 0.0424
15 0.0186 0.0115 0.1459 0.0771 0.0405 0.0186 0.0115 0.1459 0.0771 0.0405
16 0.0151 0.0093 0.1375 0.0730 0.0385 0.0151 0.0093 0.1375 0.0730 0.0385
17 0.0122 0.0075 0.1292 0.0688 0.0365 0.0122 0.0075 0.1292 0.0688 0.0365
18 0.0099 0.0061 0.1210 0.0646 0.0344 0.0099 0.0061 0.1210 0.0646 0.0344
19 0.0080 0.0049 0.1130 0.0605 0.0323 0.0080 0.0049 0.1130 0.0605 0.0323
20 0.0065 0.0040 0.1054 0.0565 0.0302 0.0065 0.0040 0.1054 0.0565 0.0302
21 0.0052 0.0032 0.0980 0.0527 0.0283 0.0052 0.0032 0.0980 0.0527 0.0283
22 0.0042 0.0026 0.0911 0.0490 0.0263 0.0042 0.0026 0.0911 0.0490 0.0263
23 0.0034 0.0021 0.0845 0.0455 0.0245 0.0034 0.0021 0.0845 0.0455 0.0245
24 0.0028 0.0017 0.0784 0.0423 0.0228 0.0028 0.0017 0.0784 0.0423 0.0228
25 0.0022 0.0014 0.0725 0.0392 0.0211 0.0022 0.0014 0.0725 0.0392 0.0211
26 0.0018 0.0011 0.0671 0.0363 0.0196 0.0018 0.0011 0.0671 0.0363 0.0196
27 0.0015 0.0009 0.0621 0.0336 0.0181 0.0015 0.0009 0.0621 0.0336 0.0181
28 0.0012 0.0007 0.0573 0.0310 0.0168 0.0012 0.0007 0.0573 0.0310 0.0168
29 0.0010 0.0006 0.0529 0.0287 0.0155 0.0010 0.0006 0.0529 0.0287 0.0155
30 0.0008 0.0005 0.0488 0.0265 0.0143 0.0008 0.0005 0.0488 0.0265 0.0143
31 0.0006 0.0004 0.0451 0.0244 0.0132 0.0006 0.0004 0.0451 0.0244 0.0132
32 0.0005 0.0003 0.0416 0.0225 0.0122 0.0005 0.0003 0.0416 0.0225 0.0122
33 0.0004 0.0003 0.0383 0.0208 0.0113 0.0004 0.0003 0.0383 0.0208 0.0113
34 0.0003 0.0002 0.0353 0.0192 0.0104 0.0003 0.0002 0.0353 0.0192 0.0104
35 0.0003 0.0002 0.0325 0.0177 0.0096 0.0003 0.0002 0.0325 0.0177 0.0096
36 0.0002 0.0001 0.0300 0.0163 0.0088 0.0002 0.0001 0.0300 0.0163 0.0088
37 0.0002 0.0001 0.0276 0.0150 0.0081 0.0002 0.0001 0.0276 0.0150 0.0081
38 0.0001 0.0001 0.0254 0.0138 0.0075 0.0001 0.0001 0.0254 0.0138 0.0075
39 0.0001 0.0001 0.0234 0.0127 0.0069 0.0001 0.0001 0.0234 0.0127 0.0069

Where for line 10:

States HHHH, HHHT and HHHTT have probabilities 0.1807, 0.0918, 0.0459, adding up to .3184, which is the total probability that HHH will have been achieved, but not TTT. The same probabilities hold for TTT but not HHH.

The probability that nothing (neither TTT nor HHH) has been achieved is the total probability of states H, HH, T and TT: 0.0537, 0.0332, 0.0537, 0.0332, adding up to  .1738.

These probabilities, .3184, .3184 and .1738 add to .8106, leaving .1894 as the probability of both TTT and HHH having been accomplished. The .3184 + .1894 for a given TTT or HHH gives .5078 as the probability of each of those, disregarding whether the other has been achieved.  The .1738 of having achieved neither, divided by the 1-.5078 probability of not having achieved TTT gives the .3531 probability of having had neither, given not having the one.

Corrected typos.

 

Edited on June 13, 2004, 2:18 pm

Posted by Charlie on 2004-06-13 13:49:52