2
$\begingroup$

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)$?

$\endgroup$
3
  • 1
    $\begingroup$ Isn't there a standard theory to get going with this, by computing $P^n$? $\endgroup$
    – T_M
    Jun 25 '20 at 13:50
  • $\begingroup$ 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. $\endgroup$ Jun 25 '20 at 13:52
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Daniel
    Jun 25 '20 at 14:00
2
$\begingroup$

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}

$\endgroup$
5
  • $\begingroup$ Thanks! In the last equation do you use the law of total probability? Or the markov property (or rather a consequence of the markov property)? $\endgroup$ Jun 25 '20 at 15:48
  • 1
    $\begingroup$ 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\}$). $\endgroup$
    – Math1000
    Jun 25 '20 at 17:58
  • $\begingroup$ Thanks again, you're amazing! $\endgroup$ Jun 25 '20 at 18:08
  • $\begingroup$ Oh I had one more question, why exactly do we have $P(X_\tau=A)=\frac{P_{CA}}{P_{CA}+P_{CE}}$? $\endgroup$ Jun 26 '20 at 9:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – Math1000
    Jun 26 '20 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.