Wikipedia:Reference desk/Archives/Mathematics/2014 December 17

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 17

Coin flipping

If a coin has 50% chance of landing "tails" when flipped, and I flip it 25 times in a row, what are the chances that I never get 4 (or more) consecutive "tails"? What is the formula by which I can calculate this? --Theurgist (talk) 14:53, 17 December 2014 (UTC)

The number of sequences is a(29)=14564533 where a(n) is the nth Tetranacci number, so the probability is 14564533/2²⁵ or about 43%. See (sequence A000078 in the OEIS) for formulas. --RDBury (talk) 00:10, 18 December 2014 (UTC)

Why 29? From the OESIS page: "a(n) = number of compositions of n-3 with no part greater than 4". 25+3=28. Is 29 used to correct for heads/tails symmetry? --46.9.44.66 (talk) 21:52, 19 December 2014 (UTC)

Look a bit further down. "a(n+4) = number of 0-1 sequences of length n that avoid 1111." --RDBury (talk) 01:47, 20 December 2014 (UTC)

Ah, thanks! --NorwegianBlue ^talk 11:40, 20 December 2014 (UTC)

Polynacci numbers, followup question

I attempted to find the answer to Theurgist's question using elementary probability calculations before RDBury's answer. I tried to separate the problem into individual cases (a sequence of heads that begins at position 1, a sequence of heads that begins at position 2, etc), but soon realized that I was unable to make the "separate" cases non-overlapping. I also realized that the question could easily be answered by brute force calculation, and have now written a small program that does so, and which confirms RDBury's answer. Experimenting a little with variations of the program, I find that an analogous approach holds true for sequences of 2, 3, 5 and 6 tails. The number of sequences of 25 coin tosses with no runs of more than 1 tail is fibonacci_number(25+2), the sequences with no runs of more than 2 tails is tribonacci_number(25+3), the sequences with no runs of more than 3 tails was the original question, the number of sequences with no runs of more than 4 tails is pentanacci_number(25+5), the number of sequences with no runs of more than 5 tails is hexanacci_number(25+6). I assume that this holds true in general. My question: Is there some intuitive or easily proven reason why this is so? --NorwegianBlue ^talk 19:39, 20 December 2014 (UTC)

• I found a nice explanation: [1]. --NorwegianBlue ^talk 10:53, 21 December 2014 (UTC)