Sunday, August 24, 2014

In the previous post, we mentioned Markov chains and a closed communicating class. If we have a Markov chain with transition matrix P and fix n transitions from the overall N, then the Markov chain with transition matrix Pn has exactly the same closed communicating classes. Recall that each single-element set from the states is a closed communicating class and by definition a closed communicating class has all the states that the origin leads to. A general Markov chain can have an infinite number of communicating classes. This is something we see from sets and relations. When we visualize the topological structure of a Markov chain, we will see closed communicating classes that have no arrows for communication and arrows between two non-closed communicating classes that are in the same direction. If we remove the non-closed communicating classes, we can get disjoint closed communicating classes.
If we have an irreducible chain where all the states form a single closed communicating class, we can further simplify the behavior of the chain by noticing that if the chain is in one set it can move to only a few other sets. For example, if we take the set with four communicating classes, the diagonal states will transition to the opposite. This we say has a period of two. A triangular three communicating class will have a period of three. The numbers two and three are indicative of a divisor in the communicating classes. If an integer n divides m and the reflexive state transitions are possible with n transitions, then its possible with m transitions. So, whether it is possible to return to i in m steps can be decided by one of the integer divisors of m. The period of the state is defined as the greatest common divisor of all natural numbers n with such that it is possible to return to i in n steps. A state i is called aperiodic if it can be returned to only one step.

No comments:

Post a Comment