# probability of a large sub-sequence within a huge sequence

You toss a fair coin one million times. What is the probability of getting at least one sequence of six heads followed by six tails?

-
Here's a way to get a ballpark estimate. You know how to get the probability that tosses $1$ through $12$ don't give you six heads followed by six tails. Let's call it $q$. The probability that tosses $13$ through $24$ don't give that result is also $q$. So is the probability for tosses $25$ through $36$. And so on. So the probability that none of these sequences of $12$ gives a $6,6$ is $q^{[100000/12]}$. That's a bit of an over estimate of the chances of not getting a $6,6$, since it doesn't account for, say, tosses $2$ through $13$. For practical purposes, it might be good enough to divide by $12$ to get an estimate of the probability that you never get your $6,6$.
Here's another idea. The probability you get your $6,6$ in $1000000$ tosses is the probability you get it in $999999$ tosses, plus the product of the probability you don't get it in $999999$ tosses and the probability that you do get it in the last $12$ tosses. This lets you set up a recurrence equation, which maybe you can solve.