Algorithm for identifying Markov chain communicating classes

Question

Let $P$ be a transition matrix of a time-homogeneous Markov chain with at least one closed communication class.

Is there an algorithm / optimization problem that outputs the identification of the communication classes? For example, if $$P=\left(\begin{matrix} 0.5 &0 &0.5 &0 \\ 0 &0.5 &0 &0.5 \\ 0.5 &0 &0.5 &0 \\ 0 &0.5 &0 &0.5 \end{matrix}\right)$$ Then the output will be $(1,3),(2,4)$.

Thank you.

http://www.math.wustl.edu/~feres/Math450Lect04.pdf – Jul 02 '15 at 08:31 — , Jul 02 '15 at 08:31
I think you can take a look here. – thanasissdr Jul 02 '15 at 08:32 — thanasissdr, Jul 02 '15 at 08:32
Also, if you use Matlab, you can take a look here, as well. – thanasissdr Jul 02 '15 at 08:39 — thanasissdr, Jul 02 '15 at 08:39

score 0 · Answer 1 · edited Jun 12 '20 at 10:38

Yeah, there is one although the algorithm is really more defined as a graphing problem. That's the case since probability theory really isn't needed to identify communication classes. The only thing you need to know is whether or not jumps between states can occur in both directions.

You could replace the P matrix you gave with a binary matrix, just replace all non-zero entries with 1 and leave all zero entries as zero.

You would then do something like below to add to a communication class after you've established a basic communication class. Each state is in a communication class so you can start from there. You'll end up with redundancies this way but you could then just pick only the unique communication classes for your output.

for all states j in the matrix
for all states i in the communication class
if P(i,j) * P(j,i) &gt; 0 then

  add j to the communication class

end if 


next i
next j

After you've computed the Markov Chain's communication classes it's then useful to label each class as either transient or recurrent, if either exists in the Markov Chain, and to then form a block matrix that's useful to compute absorption probabilities and expected number of hitting times for transient states.

The form of the block matrix is ordered so that the recurrent states are placed before the transient states in the rows and columns.

Image of a generic Markov Chain being reconfigured into a useful block matrix. The grey matrix is the original matrix and the colored one is the block matrix

Algorithm for identifying Markov chain communicating classes

1 Answers1