# Computing $\lim_n P(X_n=A|X_0=C)$ of a Markov chain

Suppose that $$(X_n)_{n\geq1}$$ is markov chain with state space $$S=\{A,B,C,D,E \}$$ with the following transition matrix $$P = \left( \begin{matrix} 0.6 & 0.4 & 0 & 0 & 0 \\ 0.3 & 0.7 & 0 & 0 & 0 \\ 0.2 & 0 & 0.4 & 0 & 0.4 \\ 0.2 & 0.2 & 0.2 & 0.2 & 0.2 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} \right)$$

I want to find the following probability $$\lim_nP(X_n=A|X_0=C)$$

I found that $$C_A=\{A,B\}$$ is a communicating class with both $$A,B$$ recurrent states. There is only one way to get from state $$C$$ to state $$A$$ and that happens with probability $$p_{AB}=0.2$$. I also know that once we hit the set $$C_A$$ this can be seen as an irreducible markov chain on state space $${A,B}$$ and the one step probabilities will converge to $$\pi_A=\frac{3}{7},\pi_B=\frac{4}{7}$$. How to combine this to find $$\lim_nP(X_n=A|X_0=C)$$?

• Isn't there a standard theory to get going with this, by computing $P^n$?
– T_M
Jun 25 '20 at 13:50
• Well you can find the invariant distribution by solving $\pi P=\pi$. But you can only use the limiting statements (that the transition proabilities will converge to $\pi$) if the markov chain satisfies certain conditions, for example irreducebility of the chain which we don't have here. Jun 25 '20 at 13:52
• You should check the probability of hitting $\{A,B\}$ before $E$; in a sense, you can first identify the class $\{A,B\}$ as a single state an evaluate this probability, whose value we call $p$. After that, using the Markov property we get $\lim_n P(X_n =A | X_0 = C) = p \pi(A)$. Jun 25 '20 at 14:00

Let $$\tau=\inf\{n>0: X_n\ne C\mid X_0=C\}$$. First we compute \begin{align} \mathbb P(X_\tau = A) &= \frac{P_{CA}}{P_{CA}+P_{CE}}\\ &= \frac{\frac15}{\frac15+\frac25}\\ &= \frac13 \end{align} (we can ignore the self-transitions from state $$C$$ to itself). Then, conditioned on the event $$\{X_\tau=A\}$$, we have $$\{X_{\tau+n} : n=0,1,\ldots\}$$ as an irreducible Markov chain on $$\{A,B\}$$, with transition matrix given by the submatrix obtained by taking the rows and columns of $$P$$ corresponding to states $$A$$ and $$B$$. You have already computed the stationary distribution for this Markov chain - so the limiting probability of $$\mathbb P(X_n=A\mid X_0=C)$$ is obtained by multiplying: \begin{align} \lim_{n\to\infty}\mathbb P(X_n=A\mid X_0=C) &= \lim_{n\to\infty} \mathbb P(X_{\tau+n}=A\mid X_\tau = A)\cdot \mathbb P(X_\tau = A)\\ &= \frac37\cdot\frac13\\ &=\frac17. \end{align}
• I suppose to be more rigorous you could add that the hitting time of state $A$ is a stopping time, and so the strong Markov property applies (as far as justifying the claim that $\{X_{\tau+n}:n=0,1,\ldots\}$, conditioned on $\{X_\tau = A\}$ is a Markov chain on $\{A,B\}$). Jun 25 '20 at 17:58
• Oh I had one more question, why exactly do we have $P(X_\tau=A)=\frac{P_{CA}}{P_{CA}+P_{CE}}$? Jun 26 '20 at 9:52
• @Keep_On_Cruising The distribution of $\tau$ is geometric with parameter $1-P_{CC}$, that is, $\mathbb P(\tau = k) = P_CC^{k-1}(1-P_CC)$ for $k=1,2,\ldots$. Conditioned on $\{\tau=k\}$, it is clear to see that $X_k$ takes value $A$ with probability $\frac{P_{CA}}{P_{CA}+P_{CE}}$ and value $E$ with $\frac{P_{CE}}{P_{CA}+P_{CE}}$. Since this is true for every value of $k$, it is true for $X_\tau$ as well. Jun 26 '20 at 16:04