You toss a fair coin with sides $K$ and $Z$ infinitely often. What is the probability of the event that the pattern $KKK$ occurs before $ZKZ$ ?
I did the following: Let $(Z_n)_{n\in\Bbb N_0}$ be i.i.d. with $\Bbb P (Z_1 = K) = 1/2 = P (Z_1 = Z)$. We define the Markov chain $X_n$ by $$X_n = (Z_n , Z_{n+1} , Z_{n+2})$$ and $\alpha := \text{Uniform}(\{K,Z\}^3)$ and the entry times $T_A := \inf\{n\geq 0 : X_n \in A\}$ for $A\subset \{K,Z\}^3$. Writing in short forms, we are interested in $$\Bbb P _\alpha( T_{KKK} < T_{ZKZ})$$ We can define the function $f(z) = P _z( T_{KKK} < T_{ZKZ})$ and calculate by the first step method
- $f(ZKZ) = 0$
- $f(KKK) = 1$
- $f(ZZZ) = f(ZZK)$
- $f(ZZK) = \frac 1 2 f (ZKK)$
- $f(ZKK) = \frac 1 2 + \frac 1 2 f(KKZ)$
- $f(KKZ) = \frac 1 2 f(ZKK)$
- $f(KZZ) = \frac 1 2 f(ZZZ) + \frac 1 2 f(ZZK)$
- $f(KZK) = \frac 1 2 f(ZKK)$
Combining 5. and 6. yields $f(KKZ) = \frac 1 3$ and this makes the full calculation of $f$ possible. Thus $$\Bbb P _\alpha( T_{KKK} < T_{ZKZ}) = \frac 1 8 \sum_{z\in \{K,Z\}^3} f(z) = \frac 5 {12}$$
Is there a more elegant way to solve this?
Edit: I really ask for different approaches (not only one different from mine)
There is another way. Inspirated by Probability of flipping coin one can do the following:
Define $f(z) = \Bbb P_z (T_{KKK} < T_{ZKZ})$.
Denote the kernel of the Markov chain $(X_{n \wedge T_{KKK} \wedge T_{ZKZ}})_n$ obtained by stopping the previous chain at the states ${KKK} , {ZKZ}$ by $\bar P$.
By Lebesgue dominated convergence theorem we can obtain (and since $T_{KKK} \wedge T_{ZKZ} < \infty$ a.s.) $$ \alpha \bar P^n f =\Bbb E_\alpha [ f(X_{n \wedge T_{KKK} \wedge T_{ZKZ}}) ] \to \Bbb E_\alpha [ f(X_{T_{KKK} \wedge T_{ZKZ}}) ] = \Bbb P_\alpha (T_{KKK} < T_{ZKZ})$$
$\alpha \bar P^n $ converges to a vector $\alpha^*$ with $\alpha^* (KKK) = \frac 5 {12}$, therefore $$\Bbb P_\alpha (T_{KKK} < T_{ZKZ}) = \frac 5 {12}$$