# Mathematics Prelims

## December 20, 2008

### Communication and Equivalence of States

Filed under: Probability Theory,Stochastics — cjohnson @ 4:41 pm

When states $i$ and $j$, $i \neq j$, of a Markov chain can be reached from one another (that is, there is a positive probability of transitioning to $i$ from $j$, and a positive probability of transitioning to $j$ from $i$; note these needn’t be one-step transitions), we say that the two states communicate.  Note that every state communicates with itself, as if we’re in state $i$ we’ll be in state $i$ after zero transitions.  Communication of states forms an equivalence relation, and so when we say two states belong to the same class, we mean that they belong to the same equivalence class with this relation.   If a chain has only one class of states, the chain is called irreducible.

For instance, consider the chain that simply moves from state one to state two, from state two to state three, then from state three back to state one, and the process repeats.  Such a chain would have a transition probability matrix of

$\displaystyle \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array} \right]$

This chain has only one class and so is irreducible.

The chain with transition matrix

$\displaystyle \left[ \begin{array}{cccc} 1/2 & 1/4 & 1/4 & 0 \\ 0 & 1/2 & 1/2 & 0 \\ 1/3 & 1/3 & 0 & 1/3 \\ 0 & 0 & 0 & 1 \end{array}\right]$

has two classes, $\{1, 2, 3\}$ and $\{4\}$.  The first three states communicate with one another as if you’re any one of $\{1, 2, 3\}$, then there is a positive probability of transitioning to any of $\{1, 2, 3\}$.  Notice that we can transition from state two to state one by going through state three first.  State four is in a class by itself, though, as state four can only communicate with itself: Once you’re in state four, you stay in state four with probability one.