The average time before the first appearance of a sequence of a length 3 of Bernoulli r.v. Let $\{X_n,n \geq 1\}$  be i.i.d. random variables of Bernoulli distribution with parameter $p \in (0,1)$.
Let $\tau_{ijk}:=\inf\{n\geq 3: (X_{n-2}, X_{n-1}, X_n) = (i,j,k)\}$ with $i,j,k \in \{0,1\}$.
How can I calculate $\mathbb{E}[\tau_{111}], \mathbb{E}[\tau_{100}]$ or any other?
If I wanted to calculate $\mathbb{E}[\tau_{111}|(X_2, X_1, X_0) = (1,1,1)] $, I would apply the following theorem for the Markov chain $\{Z_n\}_{n\geq 2}:=(X_{n-2}, X_{n-1}, X_n)$ on finite state space (8 states $(0,0,0);(0,0,1)...$):
"An irreducible Markov chain ${Z_n}$ has at most one invariant distribution $\pi(z)$. It certainly has one if it is finite. And $\forall$ $ z $ $\pi(z)=\frac{1}{\mathbb{E}[T_z|Z_0=z]},$ where $T_z:=\inf\{n\geq 1: Z_n=z\} $."
The invariant distribution here is $\pi(z)=\frac{1}{8} \forall z$, so $\mathbb{E}[\tau_{111}|(X_2, X_1, X_0) = (1,1,1)] = \mathbb{E}[\tau_{ijk}|(X_2, X_1, X_0) = (i,j,k)] = 8 $.
Though it doesn't give any clues on how to calculate $\mathbb{E}[\tau_{111}]$.
 A: Denote $\mathbb{E}[\tau_{111}] = E$. Then,
$$
E = \mathbb{E}[\tau_{111}|X_0 = 0]\cdot \frac12 + \mathbb{E}[\tau_{111}|X_0 = 1]\cdot \frac12 = (E+1)\cdot \frac12 + \mathbb{E}[\tau_{111}|X_0 = 1]\cdot \frac12.
$$
Further,
$$
\mathbb{E}[\tau_{111}|X_0 = 1] = \mathbb{E}[\tau_{111}|X_0 = 1,X_1=0]\cdot \frac12 + \mathbb{E}[\tau_{111}|X_0 = 1,X_1 = 1]\cdot \frac12\\ = (E+2)\cdot \frac12 + \mathbb{E}[\tau_{111}|X_0 = 1,X_1 = 1]\cdot \frac12.
$$
Similarly,
$$
\mathbb{E}[\tau_{111}|X_0 = 1,X_1 = 1] = (E+3)\cdot \frac12 + \mathbb{E}[\tau_{111}|X_0 = 1,X_1 = 1, X_2 = 1]\cdot\frac12
= \frac{E}2 + 3. 
$$
Combining these equalities,
$$
E = \frac{E}2 + \frac12 + \frac{E}4 + \frac12 +\frac{E}8 + \frac34,
$$
whence $E = 14$ ($\tau_{111}$ is obviously bounded by $3$ times a geometric random variable, so $E<\infty$).

Actually, we could arrive at the same result sooner if took for granted that $\mathbb E[T_z| Z_0=z] = 8$. Indeed, conditioning, as above, on the first step, we get
$$
E[T_z| Z_0=z] = 1\cdot \frac 12 + (E+1)\cdot \frac12 = 8,
$$
whence $E=14$.
