Cross posting from the riggie thread. Someone brought up the probability of hitting 100 heads/tails in a row in a million flips. I was curious as to was it actually what and posted this:

The reasoning behind that being that each individual streak is 1/2^100, and there are 990,000 opportunities to hit such a streak. Well, 2/2^100, but who's counting.

However, thinking about this some more, this doesn't seem right. Using the same logic, a "streak" of 1 head (WLOG) would be (1/2)*1,000,000 = 500k to 1 on. That seems way too short.

What am I missing here? Thanks!

Nice avatar!

That wouldn't be 500k to 1, it would be 500k as in (50 million)% lol. The reason that happens is you're overcounting the ways to get more than one success. The actual chance would be 1-.5^1000000 as in pretty much 100%.

When it comes to a streak of 100, it's tricky because the series of 100 aren't independent. If you get a tails on the 50th flip, that doesn't only kill one streak, it prevents any streak from starting earlier than flip #51.

If we were talking about <200 flips then there would be an amazingly simple inclusion-exclusion formula, but with 1M flips the possibility of separate successful streaks thwarts it.

Instead, you can use one of the formulas provided in this paper, or since you're talking about p=.5 flips, there is also the formula involving higher-order Fibonacci numbers. Yet another solution is a matrix method (markov chains). You've got options!

Anyway, if it has to be Heads, the answer is 1 in 2.53555 * 10^24

If it can be H or T, then since P(H) is so low, P(H or T) is basically 2x that, so 1 in 1.268 * 10^24

Thank you for the response Heehaww, will be sure to check out those links also.

Edit: please ignore basic arithmetic errors in OP lol.

Sorry I went blind or something, my program said 2.53555 not 2.555

And if one knows in advance that the answer will be low, the inclusion-exclusion method is plenty accurate even when not exact. Here, it agrees with my matrix answer to 15+ decimal places: https://www.wolframalpha.com/input/?...F2%5E101%29%29

ETA: what's remarkable about applying inclusion-exclusion to streaks is that the alternating series is cut very short compared to normal. For probabilities of at least length r you're completely done after one subtraction (as shown above). For exact lengths you're done after a double-subtraction followed by an addition. In other applications you'd need to add/subtract as many terms as there are overcounted intersections. If streaks behaved the same way and you flipped 200 times, you'd need to add/subtract 101 terms. But they don't, so we only need 2 terms. Sorcery!