Probability of long identical substring

Question

You have a string of $20,000$ consecutive bits. Each bit is either a $1$ or a $0$ and has a $0.5$ chance of being either.

Calculate the probability that there is at least one substring of at least $34$ consecutive $1$'s or $0$'s.

its not a binomial so i cant normally approximate it.

Answer 1

Hints

Here is an outline of one approach.

1. What if the substring contains exactly 34 1's, can you find it's likelihood?
2. What would it be for 34 0's? For either 34 1's, or 34 0's?
3. What if it were 35, how would this change your answer?
4. Can you generalize 34 and 35 above to $n$?
5. Sum from $n = 34$ to $n = 20000$?

Update

Here is an approach.

Pick string of 0's or 1's -- 2 ways to do that

Pick the starting place for your string (any one of $n=20,000$ bits except for the last 33) -- $20,000-33$ ways to do that

Pick the elements in the string, leaving others free -- 2^{n-34}

Total possible strings = 2^n

$$ Prob = \dfrac{2 \cdot (n-33) \cdot 2^{n-34}}{2^n} = \dfrac{n-33}{2^{33}} = p_{34} $$

Notice this overcounts the 35-long strings, subtract $p_{35}$ and now you didn't count the 36-strings, so use inclusion exclusion:

$$ p_{34} - p_{35} + p_{36} \pm + p_{20,000} $$