Everything is in the title, basically. We flip a coin 10 times. What is the probability of at least 5 consecutive heads? I thought it was like this: Those 5 heads can start at spots 1-6 in 10 flips, so there are 6 possibilities. The rest of times, we can get anything, so there are 2^5 possibilities. That means 6*2^5 in total (favorable outcomes) Total outcomes: 2^10 so P=(6*2^5)/(2^10) However, this is supposedly not correct. Can someone tell me why and provide the solution? Thanks.
Hi Biotic! (try using the X^{2} button just above the Reply box ) No, you're double-counting … for example, you've counted 10 heads 6 times! :yuck: Try again!
1. The problem statement, all variables and given/known data Everything is in the title, basically. We flip a coin 10 times. What is the probability of at least 5 consecutive heads? 2. Relevant equations 3. The attempt at a solution I thought it was like this: Those 5 heads can start at spots 1-6 in 10 flips, so there are 6 possibilities. The rest of times, we can get anything, so there are 2^5 possibilities. That means 6*2^5 in total (favorable outcomes) Total outcomes: 2^10 so P=(6*2^5)/(2^10) However, this is supposedly not correct. Can someone tell me why and provide the solution? Thanks.
Ok, so i did it manually counting separatelly for 5,6,7,8,9 and 10 consecutive heads. For example, when 5 heads start from flip no. 1, 6th flip can only be tails and the rest can be anything - which is 2^{4} possibilities, the same when heads are at the end. But when they are in the middle, the first flip befpre and after have to be tails (to maintain only 5 in a row) - this means 2^{3} possibilities. In total, for 5 in a row, 64. Using the same method on other number of consecutive heads ther is a total of 112 favorable outcomes which is correct. However, is there a less kindergartenish way to do this?
Do you know about Markov chains? If so, you can model this using a Markov chain with states 0,1,2,...,10, where at the end of toss n we are in state k if we have just finished a run of k heads in a row. The one-step transition probabilities are P(0 --> 0) = 1/2, P(0 --> 1) = 1/2, and for i >= 1, P(i --> 0) = 1/2 (we get tails), P(i --> i+1) = 1/2 (we get another head to add to the run). You want to know the probability of reaching states 5,6,7,8, 9 or 10 at least once by toss n = 10. We can model this by amalgamating states 5,6,7,8,9,10 into a single absorbing state (end) and compute the probability that we are in state 'end' at toss n = 10. In the modified chain the transition probabilities are as before for i = 0,1,2,3, but P(4 --> 0) = 1/2, P(4 --> end) = 1/2 and P(end --> end) = 1. You get the answer forming the 6x6 transition matrix P = (P(i --> j)) and then taking the 10th matrix power P10 = P^10 (= P*P* ... *P, which is matrix multiplication 9 times); the element P10(0,end) is the required probability. The answer will be P(0,end) = Prob{>= 1 run of 5 or more} = 7/64. RGV
The answer is related to the "Fibonacci n-step numbers", where n=5 in your case. See http://mathworld.wolfram.com/Fibonaccin-StepNumber.html
If all are head, only one event, but you're counting it 6 times. At least 5. Isolated group of 5,6,7,8,9 &10
A bit simpler is to go back to the idea you had in the original post. 2^5=32 possibilities is the correct number for a sequence of 5 or more heads starting with the first flip. This is incorrect for a sequence starting at flip #2 to flip #6. Rhetorical question: What does it mean for a sequence to start at (for example) flip #2? The answer is that the first flip must have been tails. You have already accounted for the first six flips being heads in that 2^5 possibilities for a sequence of five or more heads starting at flip #1. This the total number of possibilities is 2^5 + 5*2^4 = 112.
To get this in painful detail, you can follow my journey through these three posts on marknelson.us. The middle article details the path to the answer. (Note: the board does not allow me to post links. If you go to marknelson.us and search on "heads", the three articles in question will pop up) Innumeracy, Revisited 20 Heads In a Row - What Are the Odds? A Big Problem That Doesn't Need a BigNum - Mark
I looked at "Innumeracy, Revisited". The calculation is wrong. It treats events as independent (overlapping sequences of tosses) that aren't. However, for the purposes of that web page it is not serious since the calculated 61% is therefore an upper bound. A (poor) lower bound can be obtained by only considering non-overlapping sequences, i.e. 50,000 trials of 20 tosses each. For the present problem the number of tosses happens to be twice the run length of interest. As DH showed, that makes it much easier. That's because there's no room for two separated runs of length n in 2n tosses. For n heads in a row in 2n tosses we have chances of (n+2)/2^(n+1). With n=5 that's 7/64.
>The calculation is wrong. That's why there are three articles instead of one :-) The second article is the one with the correct calculation. - Mark
A good way to visualize all the possibilities is to think of the possibilities in sets, where the run of at least five consecutive heads starts at some toss, n, and a set includes all possibilities for some n. The sets of permutations can be specified by placing the first head of the run of at least five consecutive heads at some place, n, right after a tail (excluding n=1), where the sets are ordered for n=1,2,3,4,5, and 6 in the following way: H, H, H, H, H, ..., ..., ..., ..., ... respresents the set of all combinations whose runs of at least five consecutive heads start with the first toss. The following five tosses can occur in any way; consequently, there are 2x2x2x2x2 = 32 ways these can occur. T, H, H, H, H, H, ..., ..., ..., ... represents the set of all combinations whose runs of at least five consecutive heads start with the second toss. The following four tosses can occur in any way; consequently, there are 2x2x2x2 = 16 ways these can occur. ..., T, H, H, H, H, H, ..., ..., ... represents the set of all combinations whose runs of at least five consecutive heads start with the third toss. The first toss can occur in two ways, and the last three can occur in any way; consequently, there are 2x2x2x2 = 16 ways these can occur. ..., ..., T, H, H, H, H, H, ..., ... represents the set of all combinations whose runs of at least five consecutive heads start with the fourth toss. The first two tosses can occur in any way, and the last two can occur in any way; consequently, there are 2x2x2x2 = 16 ways these can occur. ..., ..., ..., T, H, H, H, H, H, ... represents the set of all combinations whose runs of at least five consecutive heads start with the fifth toss. The first three tosses can occur in any way, and the last one can occur in two ways; consequently, there are 2x2x2x2 = 16 ways these can occur. ..., ..., ..., ..., T, H, H, H, H, H represents the set of all combinations whose runs of at least five consecutive heads start with the sixth toss. The first four tosses can occur in any way; consequently, there are 2x2x2x2 = 16 ways these can occur. By adding 32 + 16 + 16 + 16 + 16 + 16, it then follows that there are 112 distinct combinations (permutations; order matters) of ten tosses, each with a run of at least five consecutive heads. Also, there are 2x2x2x2x2x2x2x2x2x2 = 1024 ways a coin can be tossed ten times. Therefore, the probability of getting a run of at least five consecutive heads in ten tosses of a coin is 112/1024 = .109375 or 10.9375 %. Keep in mind that probability is a fancy term for the long term relative frequency of an event of a random phenomenon and is what one would tend to observe in a very long series of trials. If anyone is so inclined to verify this, try tossing a coin one thousand times and recording the number of sets of ten tosses out of one hundred where there were runs of at least five consecutive heads. If possible, schedule a coin toss event and have a group of friends, classmates, etc. carry out sets of ten tosses simultaneously to expedite this otherwise slow process. Then report back with your numbers.