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

 Coin tossing (Posted on 2004-06-11)
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 | 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.5351610    274    149     81    504    1024   0.4921911    504    274    149    927    2048   0.4526412    927    504    274   1705    4096   0.4162613   1705    927    504   3136    8192   0.3828114   3136   1705    927   5768   16384   0.3520515   5768   3136   1705  10609   32768   0.3237616  10609   5768   3136  19513   65536   0.2977417  19513  10609   5768  35890  131072   0.2738218  35890  19513  10609  66012  262144   0.2518219  66012  35890  19513 121415  524288   0.2315820 121415  66012  35890 223317 1048576   0.2129721 223317 121415  66012 410744 2097152   0.1958622 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.2148410      0    110     68    178    1024  0.1738311      0    178    110    288    2048  0.1406312      0    288    178    466    4096  0.1137713      0    466    288    754    8192  0.0920414      0    754    466   1220   16384  0.0744615      0   1220    754   1974   32768  0.0602416      0   1974   1220   3194   65536  0.0487417      0   3194   1974   5168  131072  0.0394318      0   5168   3194   8362  262144  0.0319019      0   8362   5168  13530  524288  0.0258120      0  13530   8362  21892 1048576  0.0208821      0  21892  13530  35422 2097152  0.0168922      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

 Search: Search body:
Forums (0)