## PENENTUAN KLASIFIKASI STATE PADA RANTAI MARKOV DENGAN MENGGUNAKAN NILAI EIGEN DARI MATRIKS PELUANG TRANSISI
Yohanes A.R. Langi 1)
1) Program Studi Matematika FMIPA Universitas Sam Ratulangi, Manado 95115 e-mail:ylangi@yahoo.com

## ABSTRAK
Masalah dasar dari pemodelan stokastik dengan proses Markov adalah menentukan deskripsi state yang sesuai, sehingga proses stokastik yang berpadanan akan benar-benar memiliki sifat Markov, yaitu pengetahuan terhadap state saat ini adalah cukup untuk memprediksi perilaku stokastik dari proses  di  waktu  yang  akan  datang.  Penelitian  ini  dilakukan  untuk  menentukan  klasifikasi  state pada  rantai  Markov  yang  dibatasi  untuk  n  =  4.  Hasil  penelitian  ini  menunjukkan  bahwa  untuk, state 4 terdapat satu state absorbing dan tiga state transient . Untuk batasan nilai terdapat  dua  state  yang transient ,  dua  state  yang recurrent ,  dan  membentuk  satu  kelas ekivalensi,  sedangkan  untuk  batasan  nilai
terdapat  dua  state  yang
transient , dua state yang recurrent , dan termasuk state yang recurrent dalam satu kelas ekivalensi.
Kat kunci: klasifikasi state,  rantai markov, stokastik

## DETERMINE CLASSIFICATION OF STATE IN MARKOV CHAIN USING EIGEN VALUE FROM TRANTITION PROBABILITY MATRIX

## ABSTRACT
Base  problem  from  stochastic  modal  with  Markov  process  is  to  determine  appropriate  state  of description, in order that stochastic process corresponding will has truly Markov’s characteristic. Recently, it is adequate for knowledge of state to predict process of behavior stochastic in future. The research is intended to determine classification of state in Markov’s chain that is restriction to 4.   The  results  indicate  that  for  state,for  4.  A  restriction  value will  be formed  one  state  transient,  two  states  recurrent  and  one  class  of  equivalent,  while  limited  one will be formed two states transient, two states recurrent, and including one state recurrent inside one class of equivalent.
Keywords: state clasification, marcov chain, stochastic

## PENDAHULUAN
Rantai  Markov  merupakan  sebuah proses  stokastik,  dimana  kejadian  pada  masa mendatang  hanya  bergantung  pada  kejadian hari  ini  dan  tidak  bergantung  pada  keadaan masa lampau. Rantai Markov terdefinisi oleh matriks  peluang  transisinya.  Matriks  peluang transisi  adalah  suatu  matriks  yang  memuat informasi  yang  mengatur  perpindahan sistem dari  suatu  state  ke  state  lainnya  (Langi, 2009). Matriks peluang transisi sering disebut juga matriks stokastik karena peluang transisi adalah  tetap  dan  tidak  bergantung  pada waktu t ,  dimana adalah  peluang  transisi satu langkah yang bergerak dari keadaan i ke keadaan j .  Matriks  peluang  transisi  juga merupakan  matriks  segi.  Melalui  matriks
peluang  transisi  maka  dapat  ditentukan klasifikasi state pada rantai Markov.
Masalah dasar dari pemodelan stokastik  dengan  proses  Markov  adalah menentukan  deskripsi  state  yang  sesuai, sehingga  proses  stokastik  yang  berpadanan akan  benar-benar  memiliki  sifat  Markov, yaitu  pengetahuan  terhadap  state  saat  ini adalah  cukup  untuk  memprediksi  perilaku stokastik  dari  proses  di  waktu  yang  akan datang.  Sekarang,  bagaimana  jika  penentuan klasifikasi state dikaitkan dengan nilai eigen, apakah  hal  tersebut  bisa  dilakukan?  Maka  di dalam  penulisan  ini,  penulis  berusaha membahas  pengklasifikasian  state-state  pada rantai  Markov  dari  sebuah  matriks  dengan nilai  eigen  tertentu.  Tujuan  penelitian  adalah untuk  menentukan  klasifikasi  state  dalam
rantai  Markov  dengan  menggunakan  nilai eigen  dari  matriks  peluang  transisi  untuk matriks segi berordo  4.

## TINJAUAN PUSTAKA

## Proses Stokastik
Proses  stokastik  didefinisikan  sebagai proses menyusun dan mengindeks
sekumpulan  variabel  acak  { },  dengan indeks t berada  pada  sekumpulan  T.
Terkadang  T  dianggap  sebagai  sekumpulan bilangan bulat nonnegatif, dan merepresentasikan  karakteristik  terukur  yang kita  perhatikan  pada  waktu t (Hillier  dan Lieberman, 2008). Himpunan T disebut state atau  ruang  indeks  dari  proses  stokastik  X. State  merupakan  posisi  atau  keadaan  yang akan ditentukan klasifikasinya.

## Proses Markov
Proses  Markov  adalah  suatu  proses stokastik  dengan  sifat:  jika  keadaan  untuk saat sekarang diketahui, peluang keadaan dari proses  disatu  langkah  ke  depan  hanya dipengaruhi  oleh  keadaan  proses  disaat sekarang.  Artinya,  keadaan  proses  diwaktu- waktu  lampau  tidak  mempengaruhi  keadaan ke depan.

## Rantai Markov
Rantai  Markov  mempunyai  sifat  kunci sebagai berikut: Proses stokastik dikatakan mempunyai sifat Markovian jika * + * + (1) untuk dan setiap urutan (Hillier  dan  Lieberman, 2008).  Sifat  Markovian  ini  menyatakan bahwa  peluang  bersyarat  dari  ”kejadian” mendatang,  dengan  ”kejadian”  masa  lampau dan state saat ini , adalah independent terhadap  kejadian  di  waktu  lalu  dan  hanya tergantung pada keadaan saat ini (Hillier dan Lieberman, 2008).
Peluang  bersyarat * + untuk  rantai  Markov  disebut  peluang transisi  (satu  langkah).  Jika,  untuk  setiap i dan j ,
* +    * + untuk (2) maka peluang transisi (satu langkah) dikatakan stasioner . Oleh karena itu, peluang transisi stasioner menyiratkan bahwa peluang
transisi  tidak  berubah  seiring  dengan  waktu. Keberadaan  peluang  transisi  stasioner  (satu langkah)  juga  menyiratkan  bahwa  untuk  tiap i , j , dan v (               ) , * +    * + (3) untuk  semua Peluang  bersyarat ini disebut peluang transisi v -langkah (Hillier dan Lieberman, 2008).
Untuk menyederhanakan notasi penulisan  dengan  peluang  transisi  stasioner,
misalkan * + (4) ( ) * + (5)
(Hillier dan Lieberman, 2008)
Oleh  karena  itu,  peluang  transisi v -
langkah ( ) hanyalah  merupakan  peluang bersyarat  sehingga  sistem  akan  berada  pada state j tepat setelah v langkah (satuan waktu), jika sistem tersebut bermula pada state i pada waktu t kapan pun.  Oleh karena ( ) adalah peluang  bersyarat,  peluang  tersebut  harus nonnegatif,  dan  oleh  karena  prosesnya  harus membuat  perubahan  ke  state  lain  maka peluang tersebut harus memenuhi sifat ( ) untuk  semua i dan j ;
dan ∑ ( )
untuk  semua
i ; dan (Hillier dan Lieberman, 2008). Bentuk matriks (matriks peluang transisi v -langkah) untuk menunjukkan semua peluang transisi v -langkah adalah:
( ) [ ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ]

## Persamaan Chapman-Kolmogorov
Persamaan Chapman-Kolmogorov memberikan sebuah metode untuk
menghitung peluang transisi v -langkah ini:
( ) ∑ ( ) (   ) (6)
untuk semua i = 0, 1, . . ., l; j = 0, 1, . . ., l; dan w = 1, 2, . . ., v – 1; v = w + 1, w + 2, . . . (Hillier dan Lieberman, 2008).
Persamaan  6  menunjukkan  bahwa dalam  perubahan  dari  state i ke  state j sebanyak v langkah,  proses  ini  akan  berada dalam  beberapa  state k setelah  tepat w
(kurang  dari v )  state.  Oleh  karena  itu,
( ) (   ) adalah peluang bersyarat dengan titik  mulai  state i ,  proses  menuju  ke  state k setelah w langkah  dan  kemudian  ke  state j setelah v  –  w langkah.  Dengan  demikian, penjumlahan  peluang  bersyarat  terhadap semua k yang  mungkin  akan  menghasilkan ( ) . Untuk w = 1, maka
( ) ∑ (   ) (7)
untuk w = v – 1, maka ( ) ∑ (   )
(8)
untuk  semua  state i dan j .  Rumusan  ini memungkinkan  peluang  transisi v -langkah diperoleh  dari  peluang  transisi  satu  langkah yang diterapkan secara berulang. Untuk v = 2 rumusan (8) menjadi ( ) ∑ untuk semua state i dan j , dimana ( ) merupakan  elemen  dari  matriks ( ) . ( ) diperoleh  dengan  mengalikan matriks peluang transisi satu langkah dengan dirinya  sendiri ( ( ) ) .  Dengan
cara  yang  sama,  rumusan  di  atas  untuk ( )
mengindikasikan  bahwa  matriks  peluang transisi v -langkah adalah: ( ) (   ) (9)
(Hillier dan Lieberman, 2008).
Oleh  karena  itu,  matriks  peluang transisi v -langkah dapat diperoleh dengan menghitung pangkat ke- v dari matriks transisi satu langkah P.

## Klasifikasi State Rantai Markov
State j dikatakan  bisa  diakses ( accessible )  dari  state i jika ( ) untuk beberapa (Hillier  dan  Lieberman, 2008). Pada umumnya, kondisi yang memadai untuk semua state agar bisa diakses
adalah  adanya  nilai v di  mana ( )
untuk semua i dan j .
Jika  state j bisa  diakses  dari  state i dan state i bisa diakses dari state j maka state i dan j dikatakan  berkomunikasi,  dan dinotasikan  dengan (Hillier  dan Lieberman, 2008).
Teorema 2.1. Konsep  komunikasi  ( ) merupakan  suatu relasi ekivalen.
1. State  mana  pun  berkomunikasi  dengan dirinya sendiri karena ( ) * + (     )
2. Jika state i berkomunikasi dengan state j ( )  maka  state j berkomunikasi dengan  state i (     ) karena i dapat diakses dari j dan j dapat diakses dari i 3. Jika  state i berkomunikasi  dengan  state j ( ) dan state j berkomunikasi dengan state k (     ) maka state i berkomunikasi  dengan  state k (     ) (Brzeźniak dan Zastawniak, 2002).
Dari teorema di atas, dapat disimpulkan  bahwa adalah  suatu  relasi ekivalen.  Sebagai  hasil  dari  ketiga  sifat komunikasi  tersebut,  state  dapat  dibagi menjadi  satu  kelas  atau  lebih  sehingga  state tersebut berkomunikasi satu sama lain dalam kelas  yang  sama.  (sebuah  kelas  dapat  terdiri dari  state  tunggal)  Jika  hanya  terdapat  satu kelas, yaitu semua state berkomunikasi, rantai Markov  dikatakan irreducible (tak  bisa diperkecil  lagi)  (Hillier  dan  Lieberman, 2008).
Definisi 2.1. Suatu  state i disebut  state  penyerap
( absorbing state ) jika (Tijms, 2003)
Jika  suatu  state  merupakan  state  penyerap ( absorbing  state )  maka  tidak  ada  state  yang bisa diakses dari state tersebut.
Misalkan ( ) menyatakan  peluang bahwa,  mulai  dari  state i ,  proses  bertransisi untuk  pertama  kali  ke  state j terjadi  pada waktu v . Peluang ini disebut the first-passage time probability . Jadi untuk setiap v = 1, 2, . .
* +
(10)
(Tijms, 2003) Untuk dan ∑ (11) (Serfozo, 2009). Selanjutnya untuk setiap didefinisikan ∑ (12) (Tijms, 2003) Jadi,  untuk  setiap , menyatakan
peluang  bahwa  suatu  proses  yang  dimulai pada state i akan pernah bertransisi ke state j .
Khususnya,  untuk  setiap  state i , menyatakan  peluang  bahwa  suatu  proses yang  dimulai  pada  state i akan  pernah bertransisi kembali ke state i.
Definisi 2.2. State  dikatakan recurrent (berulang)  jika
,  sedangkan  state  dikatakan transient
jika (Tijms, 2003). Suatu  state  dikatakan recurrent bila ketika  memasuki  state  tertentu  proses  pasti akan  kembali  ke  state  itu  lagi.  Oleh  karena itu, state adalah recurrent jika dan hanya jika state  tersebut  tidak transient .  Suatu  state dikatakan  transient  bila  ketika  memasuki state  tertentu  proses  tidak  akan  pernah kembali  ke  state  itu  lagi.  Oleh  karena  itu, state i dikatakan transient jika dan hanya jika terdapat  state j ( j ≠ i )  yang  bisa  diakses  dari state i ,  tetapi  tidak  sebaliknya,  yaitu  state i tidak bisa diakses dari state j .

## METODOLOGI PENELITIAN
Jika  A  adalah  matriks  segi  ( n x n ) maka  kumpulan  nilai  eigen  dari  A  dapat dinyatakan  sebagai ( ) , dimana .  Klasifikasi state  dapat  ditentukan  dengan  merubah matriks segi berdasarkan persamaan karakteristi
∏( )
maka dapat ditinjau dalam setiap kasus untuk n = 4 dengan memisalkan bahwa
dan
.
Langkah-langkah  yang  akan  ditempuh  dalam penelitian ini adalah:
Untuk n = 4 1. Memisalkan , dan sebagai  nilai eigen 2. Untuk
a. Membuat matriks diagonal
b. Merubah  matriks  diagonal  (langkah  3.2. bagian a) menjadi matriks stokastik
c. Menentukan  state  berdasarkan  matriks yang  telah  diperoleh  pada  langkah  3.2 bagian b
3. Untuk a. Mencari  nilai melalui  determinan
dengan menganggap (     )(
)( )( )       ( )
b. Membuat matriks yang memuat unsur- unsur yang  telah  diperoleh  pada
langkah 3.3. bagian a
c. Menentukan  state  berdasarkan  matriks yang telah diperoleh pada langkah 3.3.
bagian b
4. Untuk dan
a. Membuat matriks stokastik
b. Menentukan  state  berdasarkan  matriks yang telah diperoleh pada langkah 3.4. bagian a 5. Untuk dan
a. Membuat matriks stokastik
b. Menentukan  state  berdasarkan  matriks yang telah diperoleh pada langkah 3.5. bagian a

## HASIL DAN PEMBAHASAN
Jika  A  adalah  matriks  segi  ( n x n ) maka  kumpulan  nilai  eigen  dari  A  dapat dinyatakan  sebagai ( ) , dimana .  Pada  bab
ini  akan  dibahas  bagaimana  menentukan klasifikasi state dengan merubah matriks segi berdasarkan persamaan karakteristik:

## ∏( )
maka dapat ditinjau dalam setiap kasus untuk n =  2,  3,  dan  4  dengan  memisalkan  bahwa
dan . Untuk n = 4 Misalkan ( )
.  Ada  empat  kasus  yang  akan ditinjau, yaitu:
a. Jika
Maka  dipilih  matriks  diagonalnya  sebagai berikut:

## [
]
Dari  matriks  di  atas  dapat  dilihat bahwa  matriks  tersebut  belum  merupakan matriks  stokatik  karena belum tentu  bernilai  satu,  sehingga  matriks  di  atas dapat  dirubah  menjadi  matriks  stokastik seperti berikut:

## [ ]
Dengan diagram transisinya sebagai berikut:
Gambar  1.  Diagram  Transisi  4  State  untuk
Dari  diagram  transisi  di  atas  dapat dikatakan  bahwa  state  2  dapat  diakses  dari state 1, tetapi state 1 tidak dapat diakses dari state  2.  State  3  dapat  diakses  dari  state  2, tetapi  state  2  tidak  dapat  dikases  dari  state  3 dan  state  4  dapat  diakses  dari  state  3,  tetapi state  3  tidak  dapat  dikases  dari  state  4. Dengan  demikian  dapat  dikatakan  bahwa state  1,  2,  dan  3  merupakan  state  yang transient ,  sedangkan  state  4  merupakan  state yang absorbing karena
,  sehingga tidak ada state yang dapat diakses dari state 4.
b. Jika
Matriks transisinya adalah sebagai berikut:
[ ] Dapat  dilihat  bahwa  matriks  di  atas bukan  merupakan  matriks  stokatik  karena nilai dan belum  tentu  bernilai  satu, maka matriks tersebut dapat dirubah menjadi matriks stokastik seperti berikut:
[ ] Dimana  diagram  transisinya  adalah  seperti berikut ini: Gambar  2.  Diagram  Transisi  4  State  untuk
Dari  diagram  transisi  di  atas  dapat dilihat  bahwa  state  2  dapat  diakses  dari state1,  tetapi  state  1  tidak  dapat  diakses  dari state  2,  state  3  dapat  dikases  dari  state  2, tetapi state 2 tidak dapat dikases dari state 3, sehingga  dapat  dikatakan  bahwa  state  1  dan state  2  merupakan  state  yang transient . Sedangkan  state  3  dan  state  4  merupakan state  yang recurrent karena  state  3  dapat diakses  dari  state  4  dan  begitu  juga sebaliknya.
c. Jika
Maka misalkan matriksnya adalah:

## [ ]
Dari  matriks  di  atas  dapat  dilihat  bahwa matriks  tersebut  belum  merupakan  matriks stokastik  karena  apabila  baris  ke  tiga  dan  ke empat  dijumlahkan  akan  menghasilkan , dimana belum  tentu  bernilai  satu,
sehingga  matriks  tersebut  dapat  dirubah menjadi matriks stokastik dalam bentuk: [ ]
Dimana  diagram  transisi  dari  matriks  di  atas adalah:
1 2 4 3 1 3 4
Gambar  3.  Diagram  Transisi  4  State  untuk
Dari  diagram  transisi  di  atas  dapat dilihat  bahwa  state  1  dapat  diakses dari  state 2, kemudian state 2 dapat diakses dari state 1, state 3 dapat diakses dari state 1, tetapi state 1 tidak dapat diakses dari state 3, sehingga state
1  merupakan  state  yang transient . Kemudian state  2  dapat  diakses  dari  state  1  dan  state  1 dapat  diakses  dari  state  2,  selain  itu  juga, state 4 dapat diakses dari state 2, tetapi state 2 tidak dapat dikases dari state 4, sehingga state 2 merupakan state yang transient . Selanjutnya state 3 dapat diakses dari state 4 dan sebaliknya state 4 juga dapat diakses dari state  3  sehingga  state  3  dan  state  4 merupakan state yang recurrent . d. Jika dan Misalkan:
( ) ;
Maka matriksnya adalah:
[ ]
Diagram transisi dari matriks tersebut adalah:
Gambar  4.  Diagram  Transisi  4  State  untuk dan
Berdasarkan  diagram  transisi  di  atas, maka  dapat  dikatakan  bahwa  state-statenya termasuk state yang recurrent dan merupakan satu kelas ekivalensi.

## KESIMPULAN
Untuk state 4, dimana nilai eigennya 1,
, dan ,  dengan akan  terdapat  1  state absorbing dan  3  state transient ,  sedangkan  untuk akan  terdapat  2  state  yang transient dan 2 state yang recurrent juga akan terdapat
1  kelas  ekivalensi.  Jika akan  terdapat  2  state  yang transient dan  2  state  yang recurrent dan  juga  statenya termasuk  state  yang recurrent dalam  1  kelas ekivalensi

## DAFTAR PUSTAKA
Anton,  H.  1991.  Aljabar  Linier  Elementer Edisi Ketiga. Terjemahan Pantur Silaban  dan  I.    Nyoman  Susila. Penerbit Erlangga, Jakarta
Bhat,  Narayan.  2008. An  Introduction  to Queueing Theory . Birkhäuser, Boston. Brzeźniak  and  Zastawniak.  2002. Basic Stochastic Processes . Springer, London. DeGroot,  Morris.  1986. Probability  and Statistics  Second  Edition .  Addison-
Wesley  Publishing Company, London.
Grinstead,  Charles  and  Snell,  Laurie.  [tahun terbit  tidak  diketahui]. Introduction  to
Probability .  [penerbit  tidak  diketahui], [tempat tidak diketahui].
1 2 3 4 1 2 3 4
Hadley, G. 1992. Aljabar Linear Edisi Revisi. Penerbit Erlangga, Jakarta.
Hillier,  F.  S.,  and  Lieberman,  G.  J.  2008. Introduction  to  Operation  Research . 8th  EditionJilid  2.  Penerbit  Andi, Yogyakarta.
Langi, Yohanes. 2009. Penentuan Klasifikasi State  pada  Rantai  Markov. Jurnal Ilmiah Sains . 9(1): 63-67.
Serfozo,  Richard.  2009. Basic  of  Applied
Stochastic Processes . Springer, Berlin.
Tijms, H. 2003. A First Course in Stochastic
Models . John Willey & Sons, England.