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$
    – SBK
    Jun 25, 2020 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, 2020 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$ Jun 25, 2020 at 14:00

1 Answer 1

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, 2020 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, 2020 at 17:58
  • $\begingroup$ Thanks again, you're amazing! $\endgroup$ Jun 25, 2020 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, 2020 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, 2020 at 16:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .