Classification Of States Of Markov Chains Using Graph Algorithms

Abstract

The stochastic process can be defined as the set of random variables that are indexed. The value of the random variable is a collectionr of the state space and the index is a collection of the parameter space. Element of the state space and parameter space, may be discrete or continuous. The probability of a state at time t depends only on time s and does not depend on the state of time u with u < s < t is called as  Markov chain. The values of probability  that change from one to another at a time are arranged into a transition probability matrix. Based on the transition probability matrix, the sates of markov chain can be   classified into one or more classes. If the classified class is  more than one, states may be grouped into transient and recurrent. A transient state can visit a recurrent state but not for recurrent state. Determination of classification of states helps to construct a transition probability matrix into a canonical form that can be used to determine how long a transient state is in its class before switching to a recurrent state. If the sates classified into a class, then further analysis can be proceed to determine the long-term behavior of the transition probability matrix. In the case of a considerable number of states the process of classifying satates becomes not simple. This paper discussed about the classification of the state using graph algorithm that can be implemented for a large number of sates.