All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Coin tossing (Posted on 2004-06-11) Difficulty: 3 of 5
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?

See The Solution Submitted by Federico Kereki    
Rating: 3.6667 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 3 of 25 |

The total number of sequences of n coin tosses is 2^n.  Of these a certain number of ways meet the criterion of not having any three tails in a row.  A sequence of n tosses can be formed from a sequence of n-1 tosses, plus an added toss.

We can categorize the sequences that meet the criterion as (1) ending in no tails (that is, ending in heads), (2) ending in one tail, (3) ending in two tails in a row.

For one coin toss there is 1 way of ending in no tails (just H), and 1 way of ending in tails (just T). 

From there on, in going from n-1 to n tosses in the sequence, the number of ways of ending in no tails is the total of all the categories of solution for n-1, as to each of these we can append a heads.

In step n, the number of ways of ending in one tail is equal to the number of ways in the preceding generation of having no tails.  The number of successful ways of ending in two tails is the number of ways in the preceding generation of having one tail.  (Again counting only the ways that meet the criterion.)

So we can get the following table for values of n from 1 to 22:


 n ways/0T ways/1T ways/2T tot  all comb  prob
 1      1      1      0      2       2   1.00000
 2      2      1      1      4       4   1.00000
 3      4      2      1      7       8   0.87500
 4      7      4      2     13      16   0.81250
 5     13      7      4     24      32   0.75000
 6     24     13      7     44      64   0.68750
 7     44     24     13     81     128   0.63281
 8     81     44     24    149     256   0.58203
 9    149     81     44    274     512   0.53516
10    274    149     81    504    1024   0.49219
11    504    274    149    927    2048   0.45264
12    927    504    274   1705    4096   0.41626
13   1705    927    504   3136    8192   0.38281
14   3136   1705    927   5768   16384   0.35205
15   5768   3136   1705  10609   32768   0.32376
16  10609   5768   3136  19513   65536   0.29774
17  19513  10609   5768  35890  131072   0.27382
18  35890  19513  10609  66012  262144   0.25182
19  66012  35890  19513 121415  524288   0.23158
20 121415  66012  35890 223317 1048576   0.21297
21 223317 121415  66012 410744 2097152   0.19586
22 410744 223317 121415 755476 4194304   0.18012

Each "ways/0T" is the total ("tot") from the preceding row. "ways/1T" is "ways/0T" from the preceding row. "ways/2T" is "ways/1T from the preceding row. "tot" is the total for 0T, 1T and 2T from the same row, "all comb" is 2^n. The probability is the quotient of the last two.

The probability reaches about 1/2 at n=10. So this is the first answer.

For the second problem we might as well make a similar table, though we really need the answer only for n=10.

We need to keep categorize the "ways" that the successful (meeting the criteria) sequences of tosses come out by whether they end in a single or a double occurrence of whichever type of flip they end in. In step n, there's a single occurrence for the total of the successful sequences in step n-1, and there's a double occurrence for each single occurrence in step n-1. For step 1 there are two sequences, both single occurrence: H and T.

The table looks like:

 1      0      2      0      2       2  1.00000
 2      0      2      2      4       4  1.00000
 3      0      4      2      6       8  0.75000
 4      0      6      4     10      16  0.62500
 5      0     10      6     16      32  0.50000
 6      0     16     10     26      64  0.40625
 7      0     26     16     42     128  0.32813
 8      0     42     26     68     256  0.26563
 9      0     68     42    110     512  0.21484
10      0    110     68    178    1024  0.17383
11      0    178    110    288    2048  0.14063
12      0    288    178    466    4096  0.11377
13      0    466    288    754    8192  0.09204
14      0    754    466   1220   16384  0.07446
15      0   1220    754   1974   32768  0.06024
16      0   1974   1220   3194   65536  0.04874
17      0   3194   1974   5168  131072  0.03943
18      0   5168   3194   8362  262144  0.03190
19      0   8362   5168  13530  524288  0.02581
20      0  13530   8362  21892 1048576  0.02088
21      0  21892  13530  35422 2097152  0.01689
22      0  35422  21892  57314 4194304  0.01366

The column of zeros remains from keeping the same columns as before.  In no instance is there an ending with zero occurrences, as both heads and tails count.

From the table we see that at n=10, the probability of having gotten neither 3 heads nor 3 tails in a row is about 17%  (it's 178/1024).

Edited on June 11, 2004, 3:51 pm
  Posted by Charlie on 2004-06-11 15:50:05

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information