Expert: Sherry Wallin - 2/26/2011

Question
QUESTION: I created a method to solve this problem and many similar, more complicated problems as well but I do not know weather or not there are other ways to solve this problem as well(in a reasonable amount of time. Also, if I really did discover a new way to solve this problem, what do I do next?

You flip a coin 20 times. What is the probability of at least 5 heads IN A ROW. I capitalized in a row because this is a very easy problem to solve otherwise. To solve this problem you could wright out all the possibilities (over a million) and count up the number of successes or you could use my method. I want to know if my method is original or if someone else has thought up a way to solve this problem. Explaining how my method works would be very difficult without diagrams so I only wish to know weather or not there are other ways to solve this problem.
I asked this question on another website and recieved several answers but none of them were quite correct. The answer to this problem is 119,164/1,048,576. Which is about 11.36%.
Thank you for your time. Your help is greatly appreciated.

ANSWER: Samuel~

Before I invest any amount of time I would like for you to show me what method you used! I'm not quite ready to believe that you wrote out all the possibilities and counted up the number of successes.

Here is a commentary on how I would approach this problem. First of all in the first 4 tosses you will never see 5 heads in a row, so you don't need to examine the first 4 tosses just the remaining 16 tosses (those probabilities are all 0). So for starters, what is the p(5 heads in a row in the 1st 5 tosses)? How many ways can you get 5 heads in a row when tossing the coin five times? Yes there is only one way to do this but out of how many possibilities? The first toss is 1 out of 2 and the 2nd toss is 1 out of 2, the 3rd toss is 1 out of 2, the 4th toss is 1 out of 2, and the 5th toss there is 1 out of 2 possibilities. Ok, how many ways can you get 0 heads? Yes 1 way, where all 5 tosses are tails. How many ways can you get 1 head? There are 5 ways [(10000),(01000),(00100),(00010),(00001)] where a 1 indicates a success (a head) and 0's indicate failures (tails). How many ways in 5 tosses can you get 2 heads? I am not going to list them but there are 10. How many ways in 5 tosses can you get 3 heads? Again I won't list them but there are 10 ways to throw 3 heads out of 5 tosses. And then how many ways can you get 4 heads, there are 5 ways [(11110),(01111),(10111),(11011),(11101)]. These are just permutations and cycles from abstract algebra. And finally how many ways can you get all heads (which we already decided is just one way). So how many total possibilities are there for 5 tosses? 1 + 5 + 10 + 10 + 5 + 1 = 32. Does this number surprise you? Hopefully it doesn't because the p(getting a head) = (1/2) and in 5 tosses it would be (1/2)^5 = 1/32! Thus there are 32 different ways to toss a coin 5 times. This is simply 5C0 + 5C1 + 5C2 + 5C3 + 5C4 + 5C5. So out of all those ways to toss a coin 5 times only 1 results in a success so the p(5 heads in a row in 5 tosses) = 1/32 or (1/2)^5. Keep this value as part of a sum.

Now consider 6 tosses. How many ways in 6 tosses could you get 5 heads in a row? Yes, there are only two ways, either 1,2,3,4,5 or 2,3,4,5,6. The total number of ways to toss 6 coins is: 6C0 + 6C1 + 6C2 + 6C3 + 6C4 + 6C5 + 6C6 = 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64 which by the way is (1/2)^6. So you have 2 out of 64 ways to get 5 heads in a row in 6 tosses of the coin. Keep this value as part of the sum. This means you have 2/64 = 1/32 ways to get 5 heads in a row with 6 tosses. [You now have 1/32 + 1/32 as your running sum].

         ****Do you know Pascal's Triangle??
The 1 + 5 + 10 + 10 + 5 + 5 + 1 and 1 + 6 + 15 + 20 + 15 + 6 + 1 are numbers coming from the 6th row and the 7th row of his triangle:

         1
         1       1
         1      2      1
        1      3       3     1
     1      4      6      4      1
  1     5     10      10     5      1 **** this is the 6th row so this is (a+b)^6
1    6     15     20     15      6     1 **** this is the 7th row so this is (a+b)^7

recall that each row represents (a+b)^n where n = 0,1,2,..

Now what about 7 tosses? How many ways can you get 5 heads in a row? 1,2,3,4,5 or 2,3,4,5,6 or 3,4,5,6,7 or 3 ways. Let's go one step further and look at 8 tosses. How many ways can you get 5 heads in a row? 1,2,3,4,5 or 2,3,4,5,6 or 3,4,5,6,7 or 4,5,6,7,8 or 4 ways. Do you see the pattern here? Each time you add a toss you get one more possibility for a series of 5 heads in a row. You can make a table to track this:

n > 4      # of ways to get 5 heads in a row with n tosses        P(5 heads in a row with n tosses)
 5          1          1/32 = 1*(1/2)^5
 6          2          2/64 = 2*(1/2)^6
 7          3          3/128 = 3*(1/2)^7
 8          4          4/256 = 4*(1/2)^8
...          ...          ...
20          16          16/1048576 = 16*(1/2)^20
 n          n-4          ^ (n-4)*(1/2)^n
         | add these, this is your answer

Unless I've keyed something in wrong, I get .1249828339 for an answer.

Math Prof

---------- FOLLOW-UP ----------

QUESTION: Thank you, your answer was very helpful. The method I used was similar to your method, but not quite the same. When I first tried to solve a problem similar to this, I wrote out all of the lines and and counted up those with the desire number of repeats. This took a very long time and before I finished I realized that once a line reached its desired number of repeats it could be "ended" because every line that stemed from it in later trials would also be successful. In each trial an ended line yeilds two more successful lines because a coin flip has two possibilities. It later occured to me that a similar method could be used to predict the number of each "type" of line (no repeats, one repeat, two repeats, ect.) in one trail from the number of each type of line in the last trial. For example, a line with no repeats produces a line with one repeat and a line with no repeats and a line with one repeat produces a line with no repeats and a line with two repeats. The probability of in this example can be found by adding up the number of successful lines and deviding by the total number of lines (2^20). My method works, but it is obviously easier to use the method that you used to solve this particular problem. I got the wrong answer because of a mistake in typing the numbers into my calculator.
    It may be much easier to use the method that you used to solve this particulat problem, but I still believe that variations of my method may be useful in solving more complicated problems, for example, solve the same problem but rather than finding the probability of 5 repeats of tails, find the probability of 5 repeats of either heads or tails. The to this problem is not the same as twice the answer to the last problem because the line HHHHHTTTTT or any line with five repeats of both heads or tails is only one succussful line, not two. I have methods that would also work when the probability of each outcome is not even, for example, find the probability that a series of events with the following probabilities occurs in 10 trials P(event 1)=1/10, P(event 2)=2/5, and    P(event 3)=3/8. I can also find the probability that one of multible series of event occurs in however many trials, the probablity that more than one series of events occurs in however many trails, the probablity that some series of events occor or other series of events occur and a third series of events occors in however many trials, or the probablity that some series of events occur and others do not in however many trials. Are there already methods for solving all of thease problems? Thank you for your help.

Answer
Hi, I have no clue. There comes a point in your mathematical maturity where you feel confident that you will be able to reason out a solution with the knowledge you have. What I presented to you was just that, a way to conquer the problem with the tools I've acquired. I am sure there are probably more efficient methods but I have never been one to memorize these things, I prefer to just be able to use logic to figure them out, hope this doesn't disappoint you.

Math Prof

Kudos to you for figuring out a way that works for you too.


****Perhaps I don't quite know what your question is? I thought I had answered your question. If you are asking about your method you will need to write up your proposal clearer and maybe in a word doc or something like that so I can analyze it for you. If this is what you want to pursue send me your contact info and I will write you back with contact info.

Math Prof