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$.
 A: 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.
