The problem is as follows:
Let $X_1, X_2, \ldots$ be a sequence of i.i.d. Bernoulli random variables with $\Pr[X_i = 1] = p$, and $\Pr[X_i = 1] = 1-p$. What is the probability of observing:
a)"00" before "11"
b)"000" before "111"
The question is in context of a discrete time Markov Chain.
For part a, I am totally lost as to how to take into account the condition, namely, "before" in the Markov chain.
I think I need to find
$$\Pr[X_{n+k+2} = 1, X_{n + k + 1} = 1|X_{n+1} = 0, X_{n} = 0]$$ for all $k > 1$.
Then $\Pr[X_{n+k+2} = 1, X_{n + k + 1} = 1|X_{n} = 0, X_{n+1} = 0] = \Pr[X_{n+k+2} = 1, X_{n + k + 1} = 1, X_{n+1} = 0, X_{n} = 0] / \Pr[X_{n+1} = 0, X_{n} = 0]$
Since all the $X$s are iid, therefore the probability that $``00"$ comes before $``11"$, is simply:
$\Pr[X_{n+k+2} = 1, X_{n + k + 1} = 1, X_{n+1} = 0, X_{n} = 0] / \Pr[X_{n+1} = 0, X_{n} = 0] = p * p * (1-p)*(1-p) / (1-p)^2 = p^2$
I am not sure about my answer since it did not rely on Markov chains, and it seems to be too trivial. Please assist!
I would define a Markov chain $Y$ on the states $$\{ 00, 11, 01, 10 \}$$ with transition probabilities given by $p$ or $q =1-p$ according to the original Markov chain: so for example $$\overbrace{00 \mapsto 00}^{p}, \ \ \overbrace{00 \mapsto 01}^{1-p}, \ \ \overbrace{01 \mapsto 10}^{p} \ \ \ldots $$ So it's just the Markov chain of the "couples". Now the first question asks what the probability is of hitting $00$ before $11.$ Clearly this depends on where you start $Y$. If you start it from $00$ the probability is $1$, whereas it's $0$ if you start from $11$. So we are left with two cases. If we denote with $\tau_i$ the first hitting time of the state $i$ we find: $$ \mathbb{P}_{01}(\tau_{00} < \tau_{11}) = p^2 + pq \cdot p^2 + (pq)^2 \cdot p^2 + \cdots = \frac{p^2}{1-pq}$$where the $pq$ appearing in the above fromula i the probability of the cycle $01 \mapsto 10 \mapsto 01$. On the other side we see that $$\mathbb{P}_{10}(\tau_{00} < \tau_{11}) = p + qp \cdot p + (qp)^2 \cdot p + \cdots = \frac{p}{1-pq}. $$ Now we have to compute the overall probability. We have to fix a distribution on the initial condition of $Y$. From the definition of $X_i$ we can immediately find the probability of $X_0X_1$ being one of the states of $Y$. Thus we get: $$\mathbb{P}(\tau_{00} < \tau_{11}) = \mathbb{P}(X_0X_1 = 00) + \mathbb{P}(X_0X_1 = 01)\mathbb{P}_{01}(\tau_{00} < \tau_{11}) + \mathbb{P}(X_0X_1 = 10)\mathbb{P}_{10}(\tau_{00} < \tau_{11}) \\ = p^2 + pq \cdot \frac{p^2 + p}{1-pq} = \frac{p^2(1 + q)}{1 - pq}.$$
For the case of the triples I would procede analogously.