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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: