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