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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.