Find the probability that a bit sequence $X$ of length $2k$ does not appear in a randomly generated bit sequence of length $n\geq 2k$.
If for the general case it is hard, let's solve it for the case where it includes $k$ zeros and $k$ ones, consequently. For instance, when $k=2$, $X=0011$.
My effort: It sounds like it is related to this question and we need to use a Markov chain to derive the probability. Overlapping is one of the problems. I think we should use inclusion and exclusion to solve this.
An approximate method:
If there are 2 characters (0,1), there can be $2^{2k}$ different number of ways you can generate a sequence like X of length 2k (let us call it a substring) with all such sequences equally likely to appear in a larger sequence.
Thus the probability that a sequence X would appear out of the $2^{2k}$ different ways is $\frac{1}{2^{2k}}$.
Another bit sequence of length n can be split into $[\lfloor{\frac{n}{2k}}\rfloor]$ blocks of substrings of length $2k$.
The probability that a substring other than the desired X happens in any block is $(1-\frac{1}{2^{2k}})$.
Now define the the random variable $T$, the number of times such substring X should occur where $t = 0,1,... $$\lfloor{\frac{n}{2k}}\rfloor$.
Take a case when $T = 2$, this substring should occur twice and the rest of the $[\lfloor{\frac{n}{2k}}\rfloor - T]$ blocks should be other substrings of length 2k other than the desired for which we calculated the probability a couple of steps above. For $N = 100$ and $2k = 6$, you will have $16$ blocks with $6$ strings each. You check the desired substring in each of these blocks. Then shift 1 character and check from $2-7,8-12,...$ and again shift 1 character from $3-8, 9-13,....$ This you do it till you shift 6 times then you get to the original sequence $7-12,13-18,...$ Now you have in a way scanned all the $96$ characters in $16$ blocks $6$ times to cover all consecutive appearances. One way you could accommodate is to multiply (the probability of finding substring) by $2k$ which in this case is $6$.
Now we can safely assume these appearances of substrings to be a Binomial Distribution.
Thus
$$P( T = t) =\left({\lfloor{\frac{n}{2k}}\rfloor\choose t} {(2k*\frac{1}{2^{2k}})}^t {(1-2k*\frac{1}{2^{2k}})}^{\lfloor{\frac{n}{2k}}\rfloor-t}\right)$$
$$P( T = 0) =\left({(1-k*\frac{1}{2^{2k-1}})}^{\lfloor{\frac{n}{2k}}\rfloor}\right)$$