Classification Of States Of Markov Chains Using Graph Algorithms

Yussy Anistia Nurislamiyati, Suwanda Suwanda, Lisnur Wachidah


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.


Stochastic Process, Markov Chains, Graph Algorithms, Transient, Recurrent


Ash, C. (2014). Undergraduate Course Notes on Discrete Math. Mathematics University of Illinois.

Bhat, U. N., & Miller, G. K. (2002). Element of Applied Stochastic Processes. Wiley.

Boffey , T. B. (1982). Graph Theory in Operations Research. London: The Macmillan Press, Ltd.

Cay, T., & Uslu, A. (t.thn.). Analysis of Brand Loyalty with Markov Chains. Turkey: Marmara University .

Everitt, B. S. (2002). The Cambridge Dictionary of Statistics. CUP.

Florescu, I. (2014). Probability and Stochastic Processes. John Wiley & Sons.

Hillier, F. S., & Lieberman, G. J. (2008). Introduction to Operations Research. Yogyakarta: ANDI.

Joseph, L. D. (1990). Stochastic Processes. Wiley.

Karlin, S., & Taylor, H. E. (1975). A First Course in Stochastic Processe. California: Academic Press.

Lamperti, J. (1977). Stochastic Processes : A Survey of The Mathematical Theory. Springer.

Privault, N. (2013). Understanding Markov Chains Examples and Application. Singapore: Springer.

Suwanda. (2016). Proses Stokastik. Bandung: Seri Buku Ajar Universitas Islam Bandung.

Flag Counter