# Probability that a bit sequence does not appear in a sequence

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)$$