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