10
$\begingroup$

Say we have a Markov Chain with probability matrix

$$ P = \begin{pmatrix} 0.25 & 0.25 & 0.5 & 0 & 0 \\ 0 & 0.66 & 0 & 0.33 & 0 \\ 0 & 0.25 & 0.25 & 0.25 & 0.25 \\ 0.5 & 0 & 0 & 0.25 & 0.25 \\ 0 & 0 & 0 & 0.2 & 0.8 \end{pmatrix} $$

I'm confused, it may seem really basic but I don't want to leave it to chance in the exam.

What would be the communication classes.

I would have thought that there would be only one as all the states communicate, hence it is irreducible.

But states 4 and 5 could be a class?

$\endgroup$

3 Answers 3

6
$\begingroup$

I was not familiar with the definition of communicating classes for Markov chains, but found agreement in the definitions given on Wikipedia and on this webpage from the University of Cambridge.

Assume that $\{X_n\}_{n\geq 0}$ is a time homogenous Markov Chain. Both sources state a set of states $C$ of a Markov Chain is a communicating class if all states in $C$ communicate. However, for two states, $i$ and $j$, to communicate, it is only necessary that there exists $n>0$ and $n^{\prime}>0$ such that

$$ P(X_n=i|X_0=j)>0 $$

and

$$ P(X_{n^{\prime}}=j|X_0=i)>0 $$

It is not necessary that $n=n^{\prime} = 1$ as stated by @Varunicarus. As you mentioned, this Markov chain is indeed irreducible and thus all states of the Markov chain form a single communicating class, which is actually the definition of irreducibility given in the Wikipedia entry.

It is often helpful for problems with small transition matrices like this to draw a directed graph of the Markov chain and see if you can find a cycle that includes all states of the Markov Chain. If so, the chain is irreducible and all states form a single communicating class. For larger transition matrices, more theory and\or computer programming will be necessary.

$\endgroup$
2
  • 2
    $\begingroup$ Worth a quick mention: the link to the University of Cambridge webpage is very good. It contains two very nice examples complete with solutions and graphs. $\endgroup$ Commented Jun 21, 2013 at 7:28
  • $\begingroup$ Credit where credit is due: Since it's not obvious from the pdf at Cambridge, the pdf appears to be by Yuri Suhov. $\endgroup$
    – Mars
    Commented Dec 14, 2017 at 18:00
4
$\begingroup$

In an irreducible Markov Chain all states belong to a single communicating class.

The given transition probability matrix corresponds to an irreducible Markov Chain. This can be easily observed by drawing a state transition diagram.

enter image description here

Alternatively, by computing $P^{(4)}$, we can observe that the given TPM is regular. This concludes that the given Markov Chain is irreducible. $$ P^{(4)} = \begin{matrix} 0.1576938 & 0.2583928 & 0.08312500 & 0.2327933 & 0.2588625\cr 0.1655115 & 0.2854474 & 0.11632500 & 0.2161569 & 0.1923158\cr 0.1500375 & 0.1895678 & 0.09953125 & 0.2075683 & 0.3465500\cr 0.1218750 & 0.2135125 & 0.10625000 & 0.2215688 & 0.3334688\cr 0.1277500 & 0.0615000 & 0.07750000 & 0.1892750 & 0.5437250\cr \end{matrix} $$

$\endgroup$
-3
$\begingroup$

Communicating Classes for this matrix would be: {1}, {2}, {3}, {4,5}.

State 4 and 5 communicate with each other directly, therefore they constitute the same communicating class -- they are an equivalent class . The rest of the states do not have two way direct communication. For example you may access state 1 from 4 but not state 4 from 1, therefore states 4 and 1 are not in the same communication class.

Disclaimer: So I just started learning this topic myself -- I feel your pain of having a poor lecturer -- and thus the above is a result of novice understanding.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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