Vol. 13, No. 1,  85-90,  Juli  2016
Penerapan Teorema Perron-Frobenius pada Penentuan Distribusi Stasioner Rantai Markov
Jusmawati Massalesse 

## Abstrak
Perilaku  suatu  rantai  Markov  setelah  berjalan  cukup  lama  dapat  diketahui  melalui  distribusi limit peluangnya. Sifat ergodik dan reguler rantai Markov menjamin eksistensi limit peluang. Dalam tulisan ini, diperlihatkan bahwa nilai eigen Perron-Frobenius dari matriks transisi rantai Markov  adalah 1  pf  dan  normalisasi  vektor  eigen  kiri  yang  bersesuaian  dengan  nilai
eigen pf  dari matriks transisi P merupakan distribusi stasioner rantai Markov.
Kata Kunci: Matriks stokastik, nilai eigen Perron-Frobenius, vektor eigen kiri.

## 1. Pendahuluan
Persoalan  yang  menarik  untuk  dikaji  dari  suatu  rantai  Markov  antara  lain  adalah bagaimana  peluang  perpindahan  dari  satu  keadaan  ke  keadaan  yang  lain,  apakah  setelah berpindah  proses  masih  akan  kembali  ke  keadaan  awal,  serta  bagaimana  proporsi  waktu  yang dibutuhkan  oleh  sistem  untuk  mencapai  suatu  keadaan  setelah  berlangsung  cukup  lama.  Jika rantai Markov bersifat ergodik dan reguler, maka perpindahan antar keadaan akan selalu terjadi sehingga memungkinkan untuk mencapai suatu keadaan dari manapun proses berawal. Kemudian yang  menjadi  pertanyaan  adalah,  bagaimanakah  distribusi  peluang  dari  suatu  rantai  Markov setelah  berjalan  untuk  jangka  waktu  yang  sangat  lama.  Pertanyaan  ini  akan  terjawab  melalui distribusi  stasioner  dari  rantai  Markov.  Teorema  Perron  Frobenius  menjamin  bahwa  setiap matriks  reguler  memiliki  nilai  eigen  Perron  Frobenius.  Tulisan  ini  menampilkan  beberapa teorema  dan  akibat  dari  Teorema  Perron  Frobenius,  khususnya  yang  berkaitan  dengan  matriks peluang  transisi  rantai  Markov.  Penerapan  teorema  ini  pada  matriks  stokastik  reguler memperlihatkan  adanya  kaitan  antara  vektor  eigen  kiri  dari  matriks  transisi  yang  bersesuaian dengan nilai eigen Perron Frobenius  dengan distribusi stasioner rantai Markov.

## 2. Landasan Teori

## 2.1. Rantai Markov
Misalkan   ,... 2 , 1 , 0 ,   n X X n adalah proses stokastik dimana X n menyatakan keadaan dari sistem pada saat n . Jika semua nilai dari X n merupakan elemen dari suatu himpunan S , maka S disebut  ruang  keadaan.  Untuk  rantai  Markov  dengan  ruang  keadaan  merupakan  himpunan berhingga  atau  terhitung,  maka  himpunan S dapat  dituliskan:   ... 2 , 1 , 0  S .  Penulisan i X n   Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Hasanuddin, Jl. Perintis Kemerdekaan Km.10, Tamalanrea, Makassar, email: jusmawati@gmail.com

## Jusmawati Massalesse
menyatakan  bahwa  proses  berada  di  keadaan i pada  saat n .  Rantai  Markov  merupakan  proses stokastik  dengan  ruang  keadaan  berhingga  dan  terhitung,  serta  memiliki  sifat  Markovian  yang secara formal didefinisikan sebagai berikut.

## Definisi 1.
Proses  Stokastik   ,... 2 , 1 , 0 ,   n X X n disebut  rantai  Markov  dengan  ruang  keadaan  S  jika     ij n n n n p i X j X P i X i X i X j X P           | ,..., , | 1 1 1 0 0 1 , untuk setiap
S j i i i i n   , , ,..., , 1 1 0 dan untuk setiap ,... 2 , 1 , 0  n .
Notasi p ij menyatakan  peluang  perpindahan  atau  peluang  transisi  dari  keadaan i ke keadaan j dalam satu langkah atau transisi, dan memenuhi sifat:
S j i p ij   , , 0 dan S i p S j ij   
 , 1 .
Peluang  perpindahan  proses  dari  keadaan i ke  keadaan j setelah  mengalami  n  transisi  dikenal sebagai  peluang  transisi  n-langkah,  dinotasikan  dengan n ij p .  Jadi n ij m m n p i X j X P     ) | ( . Untuk keperluan praktis, peluang transisi rantai Markov dituliskan dalam bentuk matriks peluang transisi P dimana p ij merupakan elemen baris ke- i kolom ke- j dari P .
Kajian  mengenai  perilaku  sistem  dari  suatu  rantai  Markov  diawali  dengan  melihat klasifikasi dari keadaan-keadaan rantai Markov. Dan untuk memahami klasifikasi dan sifat rantai Markov, beberapa istilah diperkenalkan dalam definisi berikut ini.

## Definisi 2.
Keadaan j dikatakan accessible dari keadaan i jika terdapat 0  n sedemikian sehingga 0  n ij p . Definisi 3. Keadaan  i  dikatakan berkomunikasi dengan  keadaan  j  jika  keadaan  i  accessible  dari  j  dan keadaan j accessible dari keadaan i.
Keadaan i berkomunikasi  dengan  keadaan j ditulis  dengan  notasi j i  . Konsep komunkasi “ j i  ” merupakan suatu kelas ekuivalensi. Dengan relasi ekuivalensi ini, ruang keadaan S akan terdiri  atas  satu  atau  beberapa  kelas  ekuivalensi.  Jika  suatu  rantai  Markov  hanya  memiliki  satu kelas ekuivalensi maka rantai Markov tersebut dinamakan rantai Markov irreducible. Setiap kelas ekuivalensi  bersifat recurrent atau transient ,  tergantung  dari  nilai     o n n ii ii f f ,  dimana n ii f adalah peluang suatu rantai Markov yang pada suatu saat berada di keadaan i akan kembali ke i . Jika 1  ii f maka keadaan i bersifat  recurrent, sedangkan  jika 1  ii f maka keadaan i bersifat transient.  Sifat  recurrent  dari  suatu  keadaan  berarti  bahwa  apabila  proses  berawal  dari  keadaan tersebut,  maka  proses  akan  selalu  kembali  ke  keadaan  tersebut.  Sedangkan  sifat  transient  dari suatu  keadaan  berarti  bahwa  jika  rantai  Markov  pada  suatu  saat  berada  pada  keadaan  tersebut, maka  terdapat  peluang  positif  bahwa  proses  tidak  akan  kembali  ke  keadaan  tersebut.  Suatu keadaan  yang  bersifat recurrent dan  memenuhi       o n n ii ii nf  disebut  bersifat  positif recurrent .

## Jusmawati Massalesse
Definisi 4.
Keadaan  i  dikatakan  mempunyai periode d(i)=d  jika  d  adalah  pembagi  bersama  terbesar  dari himpunan   0 |  n ii p n .
Jika d ( i ) = 1 untuk suatu S i  maka keadaan i dikatakan aperiodic . Suatu rantai Markov dikatakan aperiodic jika d ( i )=1  untuk  setiap S i  .  Rantai  Markov  yang  bersifat irreducible, recurrent  positif dan  aperiodik  disebut  ergodik.  Berikut  ini  sebuah  teorema  yang  penting berkaitan dengan sifat ergodik dari suatu rantai Markov.
Teorema 1. (Ross, 2010)
Jika  sebuah  rantai  Markov  bersifat  ergodik  maka n ij n P   lim ada  dan  bebas  terhadap  i.  Dan  jika dimisalkan
0 , lim     j P n ij n j  , (1)
maka j  merupakan penyelesaian satu-satunya  dari persamaan:
. 1 : 0 , 0 0        j j ij i i j j P   
(2)
Jadi j  merupakan  limit  peluang  dari rantai Markov,  yang  menyatakan  bahwa  dimulai dari keadaan apapun, proses akan berada di keadaan j setelah n transisi. Selain itu, j  dapat juga berarti  proporsi  waktu  dari  proses  akan  berada  di  keadaan j setelah  berjalan  cukup  lama.  Dan untuk rantai Markov ergodik, ( j  ), j = 0,1,2 merupakan distribusi stasioner.

## 2.2. Matriks Stokastik dan Teorema Perron-Frobenius
Matriks stokastik adalah matriks dimana setiap elemen bernilai antara 0 dan 1 (termasuk 0 dan 1), dan jumlah elemen setiap baris adalah 1. Jadi matriks peluang transisi P adalah matriks stokastik. Disamping itu, matriks peluang transisi merupakan matriks tak negative karena setiap elemennya bernilai positif atau nol.
Banyak  sifat  dari  matriks  yang  diturunkan  dari  matriks  tak  negatif.  Beberapa  sifat  dan pengertian  yang  menjadi  dasar  kajian  dalam  tulisan  ini  seperti  teorema  Perron-Frobenius  (tidak dibuktikan),  nilai  eigen  Perron-Frobenius,  vektor  eigen  kiri  dan  vektor  eigen  kanan mengelaborasi sifat-sifat dari matriks tak negative dan matriks stokastik.
Definisi 5. Misalkan nxn R A  adalah matriks bujursangkar dan  adalah nilai eigen A. Vektor 0  x yang
memenuhi x Ax   ( x xA   ) disebut vektor eigen-kanan (vektor eigen kiri) dari A.
Teorema 2. (Robinson, 2002)
Misalkan nxn R A  adalah  matriks  tak  negatif  dan  regular,  yaitu  setiap  elemen  A  tak  negative dan 0  k A untuk suatu N k  , maka:
Jusmawati Massalesse
- Terdapat nilai eigen 0  pf  dengan vektor eigen kiri dan vektor eigen kanan positif,
- Untuk setiap nilai eigen  dari A, jika pf    maka pf    , - Nilai eigen pf  bersifat simple, yang berarti mempunyai multiplisitas 1.
Nilai  eigen pf  selanjutnya  disebut nilai  eigen  Perron-Frobenius dari A .  Sebuah  akibat  dari teorema Perron-Frobenius dinyatakan dalam Akibat berikut.

## Akibat 1.
Jika A adalah matriks stokastik, maka A mempunyai vektor eigen tak negatif dengan nilai eigen 1.

## 3.  Penerapan  Nilai  Eigen  Perron-Frobenius  dalam  Menentukan Distribusi Peluang
Sebagai  matriks  stokastik  dengan  jumlah  elemen  setiap  baris  adalah  1,  maka  dengan mudah  dapat  dipahami  bahwa  vektor   T 1 ... 1 1 1   merupakan  vektor  eigen  kanan  yang bersesuaian dengan nilai 1   . Nilai  eigen 1   mempunyai  multiplisitas  1,  dan  sekaligus  merupakan  nilai  eigen Perron-Frobenius.  Lebih  khusus  lagi,  jika  rantai  Markov  bersifat irreducible,  aperiodic dan reguler ,  maka  nilai-nilai  eigen  yang  lain  memenuhi 1   . Jadi 1  pf  .  Dan  jika diasumsikan A dapat  didiagonalisasi,  maka  terdapat  matriks  invertible nxn R C  sedemikian sehingga:
                n C C P   0 0 0 : ... : :
0 ... 0 0 ... 0 1 2 1 ,
dimana  kolom  pertama C merupakan  vektor   T 1 ... 1 1 1   , n   ,..., 2 adalah  nilai  eigen P
yang bersifat n i i ,... 2 , 1 , 1    . Dari sifat matriks diagonal untuk sebarang N n  berlaku:
                m n m m m C C P   0 0 0 : ... : : 0 ... 0 0 ... 0 1 2 1 .
Jika   m maka n i m i ,... 3 , 2 , 0     , sehingga:
Jusmawati Massalesse
1 0 0 0 0
: ... : : 0 ... 0 0 0 ... 0 1               C C P m . (3)
Karena  matriks m  mempunyai  elemen  1  pada  baris  pertama  kolom  pertama  yang  merupakan elemen  satu-satunya  yang  tidak  nol,  dan  kolom  pertama C adalah  vektor   T 1 ... 1 1 1   , maka  hasil  perkalian  pada  persamaan  (3)  merupakan  perkalian  kolom  pertama C dan  baris pertama C -1 . Jadi
                                                        1 1 1 12 1 11 1 1 1 12 1 11 1 1 1 12 1 11 1 1 1 12 1 11 1 .. : .. : : .. .. .. 1 : 1 1 0 0 0 0 :
... : : 0 ... 0 0 0 ... 0 1 n n n n m c c c c c c c c c c c c C C P (4)
dimana   1 1 1 12 1 11 ...    n c c c adalah  baris  pertama C -1 .  Dengan  membandingkan  persamaan  (1) dan (4), diperoleh bahwa
    n n c c c    ... ... 2 1 1 1 1 12 1 11     .
Pada  kenyataannya,  baris  pertama C -1 adalah  vektor  eigen-kiri  dari P yang  bersesuaian  dengan nilai eigen 1 (sebut v 1 ) , sehingga   1 1
1 12 1 11 ...    n c c c merupakan normalisasi vektor eigen kiri tersebut  ke  vektor  satuan.  Dari  sini  disimpulkan  bahwa  normalisasi  vektor  eigen  kiri  yang bersesuaian dengan nilai eigen Perron-Frobenius 1  pf  dari matriks transisi P merupakan limit peluang  dan  distribusi  stasioner  dari  rantai  Markov.  Ilustrasi  mengenai  hasil  yang  diperoleh diterapkan pada sebuah contoh seperti berikut.

## Jusmawati Massalesse
Contoh: Sebuah rantai Markov memiliki peluang transisi sebagai berikut:
. 4 , 0 3 , 0 3 , 0 0 8 , 0 2 , 0 2 , 0 3 , 0 5 , 0
           P
Tentukan distribusi peluang P .
Jawab: Asumsi  ergodik  dipenuhi  oleh  rantai  Markov.  Nilai  eigen  yang  bersesuaian  dengan matriks transisi P tersebut adalah 2 , 0 , 5 , 0 , 1 2 2 1       . Vektor eigen kiri yang bersesuaian dengan nilai eigen Perron-Frobenius 1  pf  adalah            1 . 0 6 . 0 3 . 0 1 v
Jadi  distribusi  limit  rantai  Markov  adalah
                     1 . 0 6 . 0 3 . 0 3 2 1   
.  Hasil  yang  sama  diperoleh  dengan
menyelesaikan  persamaan (2).

## Daftar Pustaka
Anynomous, 2010. Convergence of regular Markov chain, Lecture Note. Website: www.stanford.edu/class/ee363/lectures/pf.pdf, diakses pada tanggal 15 Desember 2010.
Clark, R.R., 2002. Perron-Frobenius theorem. Website: www.math.northwestern.edu/~clark/354/2002/ perron .pdf, diakses pada tanggal 7 Desember 2010.
Mas275, 2010. Probability modeling: Lecture 9, Limiting and equilibrium behaviour of Markov chain.  Website:  www.shef.ac.uk/pas/MAS275/ mas27509 .pdf,  diakses  pada  tanggal  12 Desember 2010.
Ross, S.M., 2010. Introduction to Probability Model. Elsevier Inc., Oxford, USA.