## Aplikasi diagonalisasi matriks pada rantai Markov
(Application of matrix diagonalization on Markov chain)

## Bidayatul hidayah, Rahayu Budhiyati V., dan Putriaji Hendikawati
Jurusan Matematika, FMIPA, Universitas Negeri Semarang (UNNES), Semarang 50229, Indonesia dan email: bidayatul.hudayah@gmail.com
diterima 2 Desember 2013, disetujui 3 Februari 2014

## Abstrak
Rantai  Markov  adalah  rangkaian  proses  kejadian  dimana  peluang  bersyarat  kejadian  yang  akan datang  hanya  bergantung  kepada  kejadian  sekarang  dan  tidak  tergantung  kepada  kejadian  yang  lalu.  Peluang peralihan pada tingkat keadaan seimbang (peluang steady state) adalah peluang peralihan yang sudah mencapai keseimbangan, sehingga tidak akan berubah terhadap perubahan waktu yang terjadi atau perubahan tahap yang terjadi.  Dalam  tulisan  ini  dikaji  nilai  eigen  untuk  menentukan  state  dan  diagonalisasi  untuk  menentukan  vektor kondisi. Pemecahan yang dilakukan dengan  mengupas definisi dan teorema.

## Kata kunci: matriks, diagonalisasi matriks, rantai Markov

## Abstract
Markov chain is a series of events in which the conditional probability upcoming events only depend on the current  events  and  do  not  depend  on  the  previous  occurrence.  Transition  probabilities  at  the  steady  state  level (steady state probability) is a transition probability that has reached equilibrium, so that it will not change with time or  phase  changes  that  occur.  This  paper  determines  the  eigenvalue  states  and  diagonalization  to  determine  the steady state. The solution is obtained by peeling definitions and theorems.
Key words: matrix, matrix diagonalization, Markov chain

## Pendahuluan
Dalam  kehidupan,  sejumlah  fenomena dapat  di  pikirkan  sebagai  percobaan  yang mencakup sederetan pengamatan yang berturut–turut  dan  bukan  satu  kali  pengamatan. Umumnya,  tiap  pengamatan  dalam  suatu percobaan  tergantung  pada  beberapa  atau semua  pengamatan  masa  lalu  hasil  tiap pengamatan,  umumnya  ditentukan  dengan hukum–hukum peluang. Studi tentang percobaan  dalam  bentuk  seperti  ini  dikenal dengan teori proses stokastik.
Rantai Markov merupakan sebuah proses  stokastik,  dimana  kejadian  pada  masa mendatang  hanya  bergantung  pada  kejadian hari  ini  dan  tidak  bergantung  pada  keadaan masa  lampau.  Konsep  dasar  Rantai  Markov
diperkenalkan  sekitar  tahun  1907  oleh  seorang Matematisi  Rusia  Andrei  A.  Markov  (1856  – 1922)  yang  membahas  suatu  rantai  yang disebut Rantai Markov.
Rantai  markov  terdefinisi  oleh  matriks peluang  transisinya.  Matriks  peluang  transisi adalah  suatu  matriks  yang  memuat  informasi yang  mengatur  perpindahan  system  dari  suatu state  ke  state  yang  lainnya.  Matriks  peluang transisi  sering  disebut  juga  matriks  stokastik karena  peluang  transisi p adalah  tetap  dan tidak  bergantung  pada  waktu  t,  dimana p adalah  peluang  transisi  satu  langkah  yang bergerak  dari  keadaan  i  ke  keadaan  j.  Matriks peluang  transisi  juga  merupakan  matriks persegi.  Melalui  matriks  peluang  transisi  maka dapat ditentukan state pada rantai Markov.
Masalah  dasar  dari  pemodelan  stokastik dengan  proses  markov  adalah  menentukan 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.
Vektor eigen dari A adalah Jika A matriks n × n , maka  vektor  taknol  x  di  dalam R jika  Ax adalah  kelipatan  dari  x    yakni Ax = λ x untuk suatu  skalar λ dinamakan    nilai  eigen (eigenvalue) dari A dan x dikatakan vektor eigen yang bersesuaian dengan λ .
Nilai  eigen  dapat  dimisalkan  sebagai kasus  proses  markov  sehingga  memungkinkan untuk  menentukan  state  menggunakan  nilai eigen.  Oleh  karena  itu  penulis  akan  mencoba menentukan  state  menggunakan  nilai  eigen. Vektor-vektor  eigen  yang  terbentuk  digunakan untuk  membentuk  matriks  pendiagonal  Y  untuk menghitung vektor-vektor kondisi untuk menentukan vektor tunak.

## Metode Penelitian
Metode  penelitian  memegang  peranan yang  sangat  penting  dalam  pencapaian  tujuan penelitian  yang  telah  ditetapkan  agar  penelitian dapat  berjalan  lancar.  Metode  yang  digunakan dalam  penelitian  ini  adalah  study  pustaka. Langkah-langkah yang dilakukan dalam penelitian  adalah  mengupas  definisi-definisi yang  berhubungan  dengan  permasalahan  yang diangkat,  melengkapi  definisi  dengan  contoh- contoh, dan membuktikan teorema.

## Hasil dan Diskusi
Definisi 1. Proses Stokastik adalah himpunan acak yang merupakan fungsi waktu (time) atau proses acak variabel acak.

## Definisi 2.Himpunan harga-harga yang mungkin
untuk suatu variabel acak dari suatu proses stokastik disebut Ruang state.
Definisi 3. Jika proses stokastik X t , t ∈ T mempunyai sifat
P X = x |X = x , X = x , … , X = x = P X = x |X = x
untuk  setiap  harga x , x , … , x sembarang  n, dan x , x , … , x ∈ S  ruang state maka proses itu disebut proses markov.
Definisi 4. Jika sebuah rantai markov mempunyai k kemungkinan  keadaan,  di  mana ditandai  dengan  1,  2,  …, k ,  maka  probabilitas bahwa  sistem  berada  dalam  keadaan j pada suatu  pengamatan  setelah  mengalami  keadaan i pada  pengamatan  sebelumnya,  dilambangkan dengan p dan  disebut  probabilitas  transisi (transition  probability)  dari  keadaan j ke keadaan i .  Matriks P = [p ] disebut  matriks transisi  rantai  markov  (matrix  transition  of  the Markov Chain).
Definisi  5.  Misalkan  diketahui  ruang  state  S berhingga, S = 0,1,2, … , n , P matriks berukuran nxn , disebut matriks transisi
P = *p + = , p p … p p p … p ⋮ ⋮ ⋮ p p … p . dengan p ≥ 0 dan  ∑ p = 1
2 i, j = 0,1,2, … n .
Definisi  6.  Vektor  keadaan  (state  vector)  untuk sebuah  pengamatan  pada  suatu  rantai  markov yang  mempunyai  k  keadaan  adalah  sebuah vektor  baris  x  dimana  komponen  ke- i ,  yakni x merupakan  probabilitas  bahwa  sistem  berada pada keadaan ke- i pada saat itu.
Definisi  7.  Sebuah  Matriks  transisi  bersifat reguler  jika  suatu  pangkat  bulatdari  matriks tersebut mempunyai entri-entri positif.
Teorema  1.  Jika  P  merupakan  matriks  transisi rantai  markov  dan x adalah  vector  keadaan pada pengamatan ke-n, maka x = x P .
Bukti.
Diketahui P merupakan  matriks  transisi  rantai markov sehingga P = Pr3X
= S 4 5X = S 6 .
Diketahui x merupakan  vektor  keadaan  pada pengamatan ke- n ,  Sehingga x = Pr3X = S 7 ∧ ⋯ ∧ X : = S ∧ X = S 6 ,
dan x merupakan  vektor  vektor  keadaan pada pengamatan ke- n + 1 ,
sehingga x = Pr3X = S 7 ∧ ⋯ ∧ X : = S ∧ X = S ∧ X = S 4 6 .
Maka x = Pr3X = S 7 ∧ ⋯ ∧ X : = S ∧ X = S ∧ X = S 4 6 = Pr3X = S 7 ∧ ⋯ ∧ X : = S ∧
X = S 6Pr3X = S 4 5X = S 6 = x P
[1].
Sehingga
x = x P
x < = x P = x P <
x = = x < P = x P =
x = x : P = x P
vektor  keadaan  awal x dan  matriks  transisi  P akan menentukan x untuk
n = 1, 2, … …
Teorema  2.  Jika  P  adalah  sebuah  matriks transisi, maka ketika n → ∞
P → , q q < ⋯ q 4 q q < ⋯ q 4 ⋮ ⋮ ⋮ q q < ⋯ q 4 .
dimana q 4 adalah  bilangan-bilangan  positif sedemikian rupa sehingga q + q < + ⋯ + q 4 = 1 .
Bukti.
Akan  ditunjukkan P matriks  transisi  reguler untuk matriks dengan semua komponen barisnya sama.
Misalkan  kolom j dari P adalah P y dimana  y adalah vektor kolom dengan 1 di entri ke- j dan 0 di entri yang lainnya.
Misalkan  y  suatu r komponen  vektor  kolom, dimana r adalah  bilangan  dari  state  dari  rantai.
diasumsikan r > 1 yaitu y = B r ⋮ r C .
Misalkan M dan m berturut-turut  maksimum dan minimum komponen dari vektor P y .
Vektor P y = P. P : y .
Karena  setiap  komponen  dari  P n y    adalah  rata- rata  dari  komponen  dari  P n : 1 y,  sehingga M 0 ≥ M 1 ≥ M 2 ≥ ⋯ dan m 0 ≤ m 1 ≤ m 2 ≤ ⋯ .
Setiap  urutan  adalah  sama  dan  dibatasi m 0 ≤ m n ≤ M n ≤ M 0 .
Akibatnya setiap urutan mempunyai limit sampai n menuju tak hingga.
Misalkan M = lim n → ∞ M n dan m = lim → ∞ m n .
Diketahui  bahwa  m ≤ M  sehingga  M n − m n menuju 0.
Misalkan d elemen terkecil dari P.
Karena semua entri dari P positif, maka d > 0.
Dari lemma M n − m n ≤ ( ) 2d - 1 ( ) 1 n 1 - n m M − − sehingga M n − m n ≤ ( ) n 2d - 1 ( ) 0 0 m M − .
Karena r ≥ 2, d ≤ 1 2 , maka 0 ≤ 1 − 2d < 1, maka selisih  M n − m n menuju  0  dengan  n  menuju  tak hingga.
Karena  setiap  komponen  dari  P n y  terletak diantara  M n dan  m n ,  setiap  komponen  harus mendekati  bilangan  yang  sama  u = M = m,  ini menunjukkan  bahwa  lim n → ∞ P n y = ,  dimana  u adalah semua vektor kolom dari komponen yang sama dengan u.
Misalkan  y  vektor  dengan  komponen  j  sama dengan 1 dan 0 untuk komponen yang lainnya.
Maka  P n y  adalah  kolom  j  dari  P n .  Lakukan  ini untuk  tiap  j  membuktikan  bahwa  kolom  dari  P n mendekati vektor kolom konstan.
Ini  berarti,  baris  dari  P n mendekati  vektor  baris w,  atau lim n → ∞ P n = .
Tinggal menunjukkan semua entri di W positif.
Sebelumnya, misalkan y vektor dengan komponen  j  sama  dengan  1  dan  komponen yang lainnya adalah 0.
Maka  Py  adalah  kolom  j  dari  P,  dan  kolom  ini mempunyai  semua  entri  positif.  Komponen minimum  dari  vektor  Py  didefinisikan  m 1 ,  m 1 > 0.
Karena m 1 < , maka m > 0.
Ini berarti nilai dari m hanya komponen j dari w, jadi semua komponen w adalah positif [2].
Teorema  3.  Jika  P  adalah  sebuah  matriks transisi  reguler  dan  z  adalah  suatu  vektor probabilitas, maka ketika n → ∞
P n → [ q 1 q 2 ⋯ q k ] = q
dimana  q  adalah  sebuah  vektor  probabilitas tetap, yang tidak tergantung pada n, dan semua entrinya adalah positif.

## Bukti.
Dari teorema sebelumnya
Jika  P  adalah  sebuah  matriks  transisi  reguler, maka ketika n → ∞
P n → J K K L q 1 q 2 ⋯ q k q 1 q 2 ⋯ q k ⋮ ⋮ ⋮ q 1 q 2 ⋯ q k M N N O dimana q k adalah bilangan-bilangan positif sedemikian rupa sehingga q 1 + q 2 + ⋯ + q k = 1.
Misal q = [ q 1 q 2 ⋯ q k ] adalah vektor probabalitas ketika n → ∞ .
Ambil  sebarang = [ 1 2 ⋯ k ] vektor probabilitas.
Maka
P n = [ 1 2 ⋯ k ] J K K L q 1 q 2 ⋯ q k q 1 q 2 ⋯ q k ⋮ ⋮ ⋮ q 1 q 2 ⋯ q k M N N O = J K K L 1 q 1 + 2 q 1 + ⋯ + k q 1 1 q 2 + 2 q
2 + ⋯ + k q 2 ⋮ 1 q k + 2 q k + ⋯ + k q k M N N O = 1 2 ⋯ k [ q 1 q 2 ⋯ q k ] = 1 q = q
Teorema  4.  Vektor  keadaan  tunak  q  dari sebuah  matriks  transisi  reguler  P  merupakan
vektor  probabilitas  yang  unik,  yang  memenuhi persamaan qP=q.
Bukti.
qP = P n P = [ 1 2 ⋯ k ] J K K L q 1 q 2 ⋯ q k q 1 q 2 ⋯ q k ⋮ ⋮ ⋮ q 1 q 2 ⋯ q k M N N O = J K K L 1 q 1 + 2 q 1 + ⋯ + k q 1 1 q 2 + 2 q 2 + ⋯ + k q 2 ⋮ 1 q k + 2 q k + ⋯ + k q k M N N O = 1 2 ⋯ k [ q 1 q 2 ⋯ q k ] = 1 q = q
Jadi qP = q
teorema  di  atas  juga  dapat  dinyatakan  dengan pernyataan bahwa suatu sistem linear homogen
q I − P = 0
mempunyai  sebuah  vektor  solusi  q  yang  unik dengan  entri-entri  tak  negatif  yang  memenuhi syarat  q 1 + q 2 + ⋯ + q k = 1.
Sifat  jangka  panjang  suatu  pengamatan, dapat  ditentukan  dengan  nilai  eigen  dan  vektor eigen matriks transisi dari persamaan karakteristik
λ I − A = 0
dengan I matriks identitas dan A matriks transisi. Vektor-vektor kondisi dihitung dengan menetapkan
X n = X 0 3 YDY : 1 6 n = X 0 YD n Y : 1
dengan  meningkatnya  n  maka  X n mendekati vektor tunak x.

## Kesimpulan
Dari  pembahasan  yang  telah  dilakukan, dapat diambil kesimpulan sebagai berikut:
1.  State  atau  sifat  jangka  panjang  dapat ditentukan cara
a.  Menentukan  matriks  transisi  dari suatu kasus b.  Menentukan akar persamaan yaitu det λ I − A = 0 dengan  I  matriks  identitas  dan  A matriks transisi. c.  Maka state yaitu λ ditemukan.
2.  Vektor-vektor  kondisi  dapat  ditentukan dengan
a.  Menentukan  vektor  eigen  dengan λ (state)  yang  sudah  ditemukan  pada
(2)
b.  Menentukan  matriks  pendiagonal  A yang  vektor-vektor  kolomnya  adalah vektor-vektor eigen dari A.
c.  Vektor-vektor  kondisi  dapat  dihitung
dengan
X n = X 0 YD n Y : 1
dengan
Y adalah matriks
pendiagonal A. d.    Dengan  meningkatnya  n  maka  X n mendekati vektor tunak x.

## Pustaka
[1]  J.  Kenemy  dan  J.  Snell,  Finite  Markov Chains,  Springer-Verlag,  New  York  Inc, 1976.
[2]  J.  Snell  dan  C.  Grinstead,  Introduction  to Probability,  The  American  Mathematical Society, 2006.