Coin Tosses and Probabilities

Flipping a coin 200 times in a row, what is the probability of getting, at any point, 6 heads in a row?

Disclaimer: I hate probability calculations. I’ve never felt myself to be any good at it. So there is certainly a chance I’m wrong. But even if I’m wrong, what follows below the fold certainly seems interesting.

Let Q(n) be the probability of getting at least one streak of 6 heads in a row in n many coin flips.

Clearly Q(0) = 0, since there is no way to flip 0 coins and get 6 heads in a row. The same logic tells us that Q(0) = Q(1) = Q(2) = Q(3) = Q(4) = Q(5) = 0. For 6 flips, Q(6), each flip has to come up heads. Each flip as 1/2 probability of being heads, so Q(6) = (1/2)*(1/2)*(1/2)*(1/2)*(1/2)*(1/2) = (1/2)⁶ = 1/64.

Q(7) is not as straightforward, and begins to suggest the complexity of the problem. Flipping 7 times in a row, either the first 6 or the last 6 must be all heads to get the desired streak of 6. Either way, the middle five flips must all come up heads. This occurs with probability (1/2)⁵. To complete the streak, the first flip -or- the last flip must come up heads. The only way neither could be heads is if both were tails. The probability of the first and last flip both being tails is (1/2)*(1/2) = 1/4. Therefore, the probability of not that, or rather, the probability that at least one of the two flips is a head, is 1 – 1/4 = 3/4. For the streak to happen, both events must occur – the middle five must all be heads, and at least one of the first and last flips must be heads. Thus Q(7) = (1/2)⁵*(3/4) = 3/128.

The complicating issue here was that the two possible stretches of 6 were joined, intersecting in those middle five flips. The two events, the first 6 all being heads and the last 6 all being heads, were not independent. As we flip more and more times, on our way to Q(200), the coupling of these events grows.

The key then, I believe, is to reframe the experiment in terms of independent events. Allow me to explain.

Suppose you’re flipping. You flip 41 times, without getting the desired streak of 6 heads. And then suddenly you get 6 heads in a row. If all you’re looking for is to get that 6 heads in a row … why would you keep flipping? You’d stop there.

We’ll call this E41, the event where you flip 41 times without success, and then BAM, get 6 heads in a row. In general then, En is the event where you flip n many times without success, and then BAM, 6 heads in a row.

The question of whether or not you get 6 heads in a row somewhere in your 200 flips is then more accurately described as, while flipping, whether or not an E0, E1, E2, …, or E194 event occurs. Any way of flipping 200 times that results in at least one string of 6 heads in a row can be described by one, and only one, of these events. And only one of those events can occur. They are completely independent of each other. There’s no way to flip a coin any number of times so that both of them can occur.

And this is very nice. Because if A and B are two completely independent events, the probability of at least one of them happening, P(A or B) is given by the sum of the two probabilities. The probability of getting 6 heads in tossing 200 times is therefore the sum of the probabilites of getting any of the En events. Q(200) = P(E0) + P(E1) + … + P(E194).

In general, we have this equation,

If there is a flaw in this, it is assuming the above is true. It makes sense that it would be true, that you could view the original problem in this new way, but if there is a problem, it is certainly right here.

Assuming that it isn’t an issue, notice that the above also gives us

As such, we can say that

The question then becomes, what is P(En)?

E0 is basically just tossing 6 heads all in a row. The probability of this is (1/2)⁶, or P(E0) = 1/64.

For En, consider flipping n times, then flipping 6 heads. H for heads, T for tails, W for whatever, En would look like: [WW ... (n times) ... WW][HHHHHH]. But we do not want any strings of 6 heads other than the one on the tail. So to prevent intersection with the -whatever- string, we force the last W to be a tails. En becomes [WW ... (n-1 times) .. W][T][HHHHHH]. If that tails were a heads, [WW ... (n-1 times) .. W][H][HHHHHH], there would be a string of 6 heads before the one on the tail, and this would actually be an E[n-1] event.

So we know that En looks like [WW ... (n-1 times) .. W][T][HHHHHH], with no string of 6 heads in that n-1 many whatevers. What’s the probability of this occuring? The probability of getting the 6 heads is (1/2)⁶, as we’ve discussed. The probability of getting that tails is (1/2). The probability of tossing n-1 times and -not- getting and 6 heads in a row? If Q(n-1) is the probability of flipping n-1 times and getting *at least* one 6 head streak, the probability of getting -no- 6 head streak is 1 – Q(n-1). Remember, P(A) + P(not A) = 1. It is guaranteed that either the event will happen, or it won’t.

This leads us to the equation

Substituting that into our previous equation yeilds

This is a very simple recurrence relation, all things considered. Just to check, letting n = 0, that gives Q(7) = (1/128)(1 – Q(0)) + Q(6) = 1/128 + 1/64 = 3/128, which agrees with our previous calculation of Q(7).

Now, the relation is solvable for general Q(n), but the solution looks really nasty, and I can’t figure out a way to write it so it looks nice enough to post here. Barring actually getting the solution for Q(n), you can still use the above to calculate Q(n) sequentially. Doing so, we find that Q(200) is approximately 0.800932, or just over 80%.

It certainly seems reasonable and convicing, if not completely correct : ) So … that’s all I’ve got.