Vtyjkyuk

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(beginmatrix 0.5 &0 &0.5 &0 \ 0 &0.5 &0 &0.5 \ 0.5 &0 &0.5 &0 \ 0 &0.5 &0 &0.5 endmatrixright)$$
Then the output will be $(1,3),(2,4)$.

Thank you.

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