What are communicating classes for this Markov chain?

Question

I am not sure what are communicating classes for a Markov chain represented by the following transition matrix

$$ P = \begin{pmatrix} 0 & \frac12 & \frac12 & 0 & 0 \\ 0&0&1&0&0 \\ 0 & 1 & 0 & 0 & 0 \\ 0&0&0&\frac12 & \frac12 \\ 0&0&0&0&1 \end{pmatrix} $$

I thought that the communicating classes are $\{2,3\}$, $\{5\}$, and $\{4\}$. State 1 is not a communicating class itself because there is no way to return to 1 after leaving 1.

My professor said that the communicating classes are: $\{1\}$, $\{2,3\}$, and $\{4,5\}$. I do not understand why $\{1\}$ and $\{4,5\}$ are communicating classes. How it is possible for $\{4,5\}$ be a communicating class when it is not possible to reach state 4 from state 5?

Answer 1

I will use (and briefly defend) the definition in Karlin and Taylor's First Course in Stochastic Processes, where:

• State $j$ is accessible from state $i$ if $P_{ij}^n > 0$ for some $n \ge 0$: if it is possible to reach $j$ from $i$ in some nonnegative number of steps.
• States $i$ and $j$ communicate if either is accessible from the other.
• The communicating classes are the equivalence classes of this relation.

Under this definition, the communicating classes are $\{1\}$, $\{2,3\}$, $\{4\}$, and $\{5\}$. (There is not really any doubt that $4$ and $5$ should not be in a communicating class together: state $4$ is not accessible from state $5$.)

Meanwhile, I understand your reluctance to consider $\{1\}$ a communicating class: state $1$ can only reach itself in $0$ steps, not in any positive number of steps. Some sources do modify the definition of "accessible" to require $n>0$, and in that case state $1$ should not be accessible from state $1$.

This is the wrong choice: with that choice, communicating is no longer an equivalence relation, and the communicating classes no longer partition the state space. You will not get as useful a summary of the accessibility relation by looking at a partial order of communicating classes, because some states will be missing from the picture entirely.