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.
Proses stokastik dapat didefinisikan sebagai himpunan dari peubah acak yang diberi indeks. Nilai dari peubah acak merupakan anggota ruang keadaan dan indeks merupakan anggota ruang parameter. Anggota ruang keadaan dan ruang parameter, dapat bersifat diskrit ataupun kontinu. Probabilitas suatu keadaan pada waktu ke t yang hanya bergantung pada waktu ke s dan tidak tergantung pada keadaan waktu ke u dengan u < s < t disebut rantai Markov. Nilai-nilai probabilitas dari perubahan kedaan yang satu ke keadaan yang lain untuk satu satuan waktu disusun kedalam matriks probabilitas transisi. Berdasarkan matriks probabilitas transisi keadaan-keadaan yang mungkin dapat dikelompokan kedalam satu atau beberapa kelas. Apabila kelas yang terbentuk lebih dari satu, keadaan-keadaan yang mungkin dapat dikelompokan kedalam beberapa kelompok yang bersifat transient dan recurrent. Keadaan yang transient dapat mengunjungi keadaan recurrent akan tetapi tidak sebaliknya. Penentuan kelas klasifikasi keadaan membantu untuk menyusun matriks probabilitas transisi kedalam bentuk kanonik yang berguna untuk menentukan seberapa lama sebuah keadaan transient berada di dalam kelasnya sebelum berpindah ke keadaan recurrent. Apabila kelas yang terbentuk adalah satu maka analisis selanjutnya dapat dilanjutkan untuk menentukan perilaku jangka panjang dari matriks probabilitas transisi. Dalam hal banyaknya keadaan cukup besar proses klasifikasi keadaan menjadi tidak sederhana. Dalam makalah ini dibahas tentang klasifikasi keadaan menggunakan algoritma graf yang memungkinkan dapat diimplementasikan untuk banyaknya keadaaan yang cukup besar.