# Probability that $010$ is present in an $n$-length binary sequence

Imagine a memoryless source that outputs 0's and 1's with probabilities $$P_X(0)$$ and $$P_X(1)$$. For example, $$P_{X^2}(00)=P_X(0)P_X(0)$$.

How would you calculate the probability that the sequence $$010$$ is present in an $$n$$-length binary sequence?

What I have thought so far is that,

$$P[010 \text{ is in an } n\text{-length sequence}]=(n-3)P_X(0)^{\#0}P_X(1)^{\#1}$$

I am sure that I have to multiply the probabilities $$P_X(0)$$ and $$P_X(1)$$ by $$n-3$$, because I need to take into consideration all the possible combinations in which $$010$$ can appear (e.g. $$\{010...x\}$$,$$\{x010...x\}$$,etc.). But I am not sure about the number of zeros $$\#0$$ and the number of ones $$\#1$$.

• This is not clear. Are you considering the universe of binary sequences generated by, say, the repeated tosses of a (possibly unfair) coin? Something else?
– lulu
Jun 2, 2021 at 17:15
• You seem to have a lot of double counting problems. If the sequence starts $01010$ aren't you counting it twice? Jun 2, 2021 at 17:19
• To your question: You'll need to work recursively to avoid double counting. I suggest starting from the fact that every sufficiently long "good" sequence must end in one of $1,00, 110$.
– lulu
Jun 2, 2021 at 17:22
• @BrianMoehring My comment was pretty vague. In the given problem, I'd divide the good sequences into $4$ types, according to whether they end in $11,01,00$ or $10$. I haven't written it out, but I think that's good enough...after all, the only banned action is to add a $0$ to the type ending in $01$. For longer 'forbidden' blocks, you'd need to consider more endings.
– lulu
Jun 2, 2021 at 17:46
• Should note that the posted solution, from @Onir, follows a more or less similar methodolgy to the one I am sketching.
– lulu
Jun 2, 2021 at 17:52

Let $$a(00,n), a(01,n), a(10,n), a(11,n)$$ be the probability we get a sequence that doesn't contain $$010$$ and end in each of the finishes.

We get:

$$a(00,n+1)=p(a(00,n) + a(10,0))$$

$$a(01,n+1) = (1-p)(a(00,n)+a(10,n))$$

$$a(10,n+1) = pa(11,n)$$

$$a(11,n+1) = (1-p)(a(01,n) + a(11,n))$$

We can write this as:

$$\begin{pmatrix} p & 0 & p & 0 \\ 1-p & 0 & 1-p & 0 \\ 0 & 0 & 0 & p \\ 0 & 1-p & 0 & 1-p \\ \end{pmatrix} \begin{pmatrix} a(00,n) \\ a(01,n) \\ a(10,n)\\ a(11,n) \end{pmatrix} = \begin{pmatrix} a(00,n+1) \\ a(01,n+1) \\ a(10,n+1)\\ a(11,n+1) \end{pmatrix}$$

When $$n=2$$ the values are $$(p^2,p(1-p),(1-p)p,(1-p)^2)$$. Hence we have:

$$\begin{pmatrix} p & 0 & p & 0 \\ 1-p & 0 & 1-p & 0 \\ 0 & 0 & 0 & p \\ 0 & 1-p & 0 & 1-p \\ \end{pmatrix}^{n-2} \begin{pmatrix} p^2 \\ p(1-p)\\ (1-p)p\\ (1-p)^2 \end{pmatrix} = \begin{pmatrix} a(00,n) \\ a(01,n) \\ a(10,n)\\ a(11,n) \end{pmatrix}$$

If the matrix happens to be diagonalizable you can get explicit formulas, even if it isn't you can expect to put it in a good form. You can also use exponentiation by squaring for rapid computations.

• Oh, there is $p$ and $1-p$ ? I need to change the transition matrix then. Jun 2, 2021 at 17:50
• "When $n=2$ all the values are $1$"? Jun 2, 2021 at 19:27
• Oh I forgot to remove that part. Jun 2, 2021 at 19:28
• When $n=2$, don't we have $a_2(0,0)=p^2,\ a_2(0,1)=p(1-p),$ etc? Jun 2, 2021 at 19:32
• Yes, thank you. Jun 2, 2021 at 19:36