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?
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 |
solution
