BAB II TEORI DASAR 2.1
Proses Stokastik Rantai Markov
Proses stokastik merupakan suatu cara untuk mempelajari hubungan yang dinamis dari suatu runtunan peristiwa atau proses yang kejadiannya bersifat tidak pasti. Dalam
memodelkan
perubahan
dari
suatu
sistem
yang
mengandung
ketidakpastian seperti pergerakan harga saham, banyaknya klaim yang datang ke suatu perusahaan asuransi, keadaan cuaca, dan lain sebagainya, proses stokastik banyak digunakan. Secara formal, Ross [1] mendefinisikan proses stokastik sebagai barisan peubah acak {V(t), t∈T} yang diberi indeks dengan urutan oleh parameter t dimana nilai t berubah-ubah sesuai dengan himpunan indeks T. Dengan demikian, untuk setiap t elemen dari T, V(t) adalah suatu peubah acak. Nilai dari peubah acak V(t) disebut keadaan pada saat t. Himpunan T adalah himpunan indeks yang membangun suatu ruang, yaitu ruang parameter. Himpunan T bisa berupa himpunan terbilang (terhitung) baik terhingga maupun tak terhingga, misalnya T = {1,2,3,4,5,……}, atau tak terbilang (berupa selang atau interval), misalkan T = [t0 , tn]. Semua nilai peubah acak V(t) yang mungkin terjadi membentuk sebuah himpunan keadaan S. Himpunan S membangun suatu ruang, yaitu ruang keadaan. Disini, V(t) ∈ S untuk setiap t ∈ T. Seperti T, himpunan S juga bisa berupa himpunan
6
yang terbilang baik hingga atau tak hingga, atau tak terbilang. Selanjutnya, himpunan yang terbilang kita sebut sebagai himpunan diskrit dan himpunan yang tak terbilang sebagai himpunan kontinu. Proses stokastik pada dasarnya dikelompokkan berdasarkan sifat ruang parameter T, sifat ruang keadaan S, dan hubungan ketergantungan diantara peubah acakpeubah acak V(t). Berdasarkan sifat ruang parameter T, proses stokastik digolongkan menjadi proses stokastik diskrit dan proses stokastik kontinu. Seringkali jika T diskrit, untuk membedakan kita lebih baik menuliskan Vt daripada V(t). Sementara itu, jika T kontinu, kita dapat menuliskan sebagai V(t). Berdasarkan sifat ruang keadaan S, proses stokastik digolongkan menjadi proses stokastik dengan ruang keadaan disrit dan proses stokastik dengan ruang keadaan kontinu. Berdasarkan hubungan ketergantungan diantara peubah acak-peubah acak V(t), proses stokastik dapat dibagi kedalam beberapa tipe klasik diantaranya proses stasioner, proses renewal, martingales, point process, dan proses Markov. Sebagai contoh, salah satu proses stokastik dengan ruang parameter diskrit dan ruang keadaan diskrit adalah banyaknya pengunjung yang datang ke suatu pertokoan pada hari ke-t. Contoh proses stokastik dengan ruang parameter kontinu dan ruang keadaan kontinu adalah selang waktu antar kedatangan pengunjung ke suatu pertokoan pada waktu t sembarang. Sebelumnya membahas mengenai rantai Markov, perlu dijelaskan proses Markov terlebih dahulu. Menurut Karlin dan Taylor [2], proses Markov adalah sebuah proses dengan sifat, diberikan nilai V(t), nilai V(t+1) tidak tergantung pada nilai V(u) untuk setiap u < t. Secara formal sebuah proses dikatakan Markov jika memenuhi sifat Markov yaitu, P (V ( t + 1) = v t + 1
V (1) = v1 , V ( 2 ) = v 2 ,
= P (V ( t + 1) = v t + 1
, V ( t − 1) = v t -1 , V ( t ) = v t )
V ( t ) = v t ) = p v( tt ,,vt +t +1)1 ( s )
(2.1.1)
dengan s = t+1 – t Inti dari definisi diatas adalah, untuk mempelajari keadaan proses pada satu kurun waktu berikutnya, sebut t+1, kita hanya perlu melihat keadaan proses saat t.
7
Demikian juga, keadaan yang akan datang hanya bergantung pada keadaan saat ini dan tidak dipengaruhi oleh keadaan sebelumnya. Notasi tersebut menyiratkan bahwa secara umum, peluang transisi juga merupakan fungsi dari selang waktu s. Jika peluang transisi satu langkah tidak bergantung pada variabel waktu, kita sebut rantai Markov tersebut memiliki peluang transisi stasioner. Dalam hal ini,
pv(tt ,,vt +t+1)1 ( s) adalah suatu kostanta untuk s yang sama. Secara umum rantai Markov yang biasa kita temui memiliki peluang transisi stasioner. Berdasarkan ruang keadaan dan ruang parameternya, proses Markov dapat dikelompokkan sebagai berikut,
RUANG
PARAMETER
DISKRIT
KONTINU
DISKRIT
Rantai Markov Parameter Diskrit
Rantai Markov Parameter Kontinu
KONTINU
Proses Markov Parameter Diskrit
Proses Markov Parameter Kontinu
RUANG KEADAAN
Jadi, rantai Markov adalah proses Markov dengan ruang keadaan yang diskrit. Dalam rantai Markov, salah satu hal yang menarik adalah kita dapat mempelajari perubahan keadaan pada proses. Untuk rantai Markov dengan ruang parameter diskrit -untuk seterusnya akan disebut sebagai rantai Markov saja-, peluang Vt +1 berada pada keadaan it+1 bila diberikan Vt berada pada keadaan it dinamakan peluang transisi satu langkah dan dinotasikan dengan Pit ,it +1 . Di sini, P (V t + 1 = i t + 1 V 1 = i1 , V 2 = i 2 ,
, V t − 1 = i t -1 , V t = i t )
= P (V t + 1 = i t + 1 V t = i t ) = p it , it + 1
dimana
n
∑
it + 1 = 1
p it , it + 1 = 1 d a n p it , it + 1 > 0 , i t = i t + 1 = 1 , 2 ,
(2.1.2) n
8
Disini it dan it+1 merupakan anggota himpunan bilangan asli karena dalam studi kasus pada Bab IV yang dibahas adalah jenis-jenis basa nukleotida. Secara teoritis, it dan it+1 bisa berupa anggota dari sembarang himpunan bilangan diskrit ⎧1 misalnya himpunan bilangan bulat atau ⎨ , n = 1, 2, ⎩n
2.2
⎫ ⎬. ⎭
Sifat-Sifat Pada Rantai Markov
Salah satu karakteristik utama suatu rantai Markov adalah peluang-peluang transisinya. Peluang transisi tersebut menggambarkan peluang perpindahan dari satu keadaan ke keadaan lainnya. Dengan kata lain, ia menggambarkan peluang proses berada di satu keadaan bila diketahui keadaan proses pada satu waktu sebelumnya. Secara matematis, peluang transisi tersebut dapat ditulis sebagai berikut,
pij = P(Vt +1 = j Vt = i) dengan i dan j masing-masing menyatakan keadaan proses saat t dan t+1. Peluang-peluang transisi tersebut penulisannya dapat dilakukan dalam berbagai cara seperti,
⎧ p1 j ⎪p ⎪ 2j pij = ⎨ ⎪ ⎪⎩ pnj
, j = 1, 2,
,n
(a)
atau
⎡ p11 ⎢p P = ⎢ 12 ⎢ ⎢ ⎣⎢ p1n
p21 … p22 … p2 n …
pn1 ⎤ pn 2 ⎥⎥ ⎥ ⎥ pnn ⎦⎥
(b )
atau
⎡ p11 ⎢p P = ⎢ 21 ⎢ ⎢ ⎣⎢ pn1
p12 … p22 … pn 2 …
p1n ⎤ p2 n ⎥⎥ ⎥ ⎥ pnn ⎦⎥
(c )
Akan tetapi, bentuk umum yang dipakai adalah persamaan (c). Hal menguntungkan dengan menuliskan secara persamaan ini adalah dalam penerapan prinsip aljabar linear khusunya perkalian matriks. Dalam aljabar linear dua
9
matriks misal A dan B dapat dikalikan jika banyaknya kolom pada matriks pertama (A) sama dengan banyaknya baris pada matriks kedua (B). Untuk menyelaraskan aturan perkalian matriks dan persamaan Chapmann-Kolmogorof, maka peluang transisi sebaiknya dituliskan sebagai matriks peluang transisi,
⎡ p11 ⎢p P = ⎢ 21 ⎢ ⎢ ⎢⎣ pn1
p1n ⎤ p2 n ⎥⎥ ⎥ ⎥ pnn ⎥⎦
p12 … p22 … pn 2 …
Matriks tersebut, seluruh elemennya non-negatif dan jumlah elemen dalam satu baris sama dengan satu yaitu, pij ≥ 0 dan
n
pij = 1 , ∑ j =1
i = 1, 2,
,n
(2.2.1)
Persamaan Chapmann-Kolmogorof sendiri akan dipaparkan dalam pembahasan selanjunya. Selain peluang transisinya, rantai Markov juga ditentukan melalui distribusi peluangnya. Untuk rantai Markov dengan ruang parameter diskrit, distibusi
peluang di waktu ke-t atau
πt
adalah
π t = {π kt : k = 1, 2,
, n}
dimana
π kt = P (Vt = k ) dan Dengan kata lain, distribusi peluang
πt
n
∑π k =1
t k
= 1
menyatakan proporsi dari keadaan proses
di waktu t. Perhatikan bahwa,
P(Vt = it , Vt −1 = it -1,
, V1 = i1, V0 = i0 )
= P(Vt = it Vt −1 = it -1, , V1 = i1, V0 = i0 ) × P(Vt −1 = it -1, ,V1 = i1, V0 = i0 ) Dari definisi proses Markov pada persamaan (2.1.2),
= P (Vt = it Vt −1 = it -1 ) × P ( Vt −1 = it -1 ,
, V1 = i1 , V0 = i0 )
10
Dengan induksi maka diperoleh = P (V0 = i0 ) × P (V1 = i1 V0 = i0 ) × P (V2 = i2 V1 = i1 ) × = pi0 pi0 i1 pi1 i2
× P (Vt = it Vt −1 = it -1 )
pit−1 i t
(2.2.2)
Ini menunjukkan bahwa sebuah rantai Markov ditentukan oleh distribusi peluang di awal proses yaitu saat t=0 dan peluang transisinya. Hubungan antara distribusi peluang dengan matriks peluang transisi adalah,
π t = π t −1 × P = π 0 × P(t ) Disini matriks P(t) adalah matriks peluang transisi t langkah dimana
pij (t ) = P(Vt = j V0 =i ) merupakan elemen-elemen dari P(t). Sebelum membahas mengenai matriks peluang transisi t langkah, perhatikan contoh berikut. Misalkan matriks peluang transisi untuk rantai Markov dengan tiga keadaan sebagai berikut,
⎡ ⎢ ⎢ P = ⎢ ⎢ ⎢ ⎢ ⎢⎣
2 5 1 3 4 7
1 5 1 3 2 7
2 5 1 3 1 7
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦
Matriks peluang transisi di atas adalah matriks peluang transisi satu langkah. Jadi, misalkan {Vt} adalah rantai Markov dengan matriks peluang transisi P, maka peluang transisi Vt = 1 bila proses berawal di Vt-1 = 3 yaitu P (Vt = 1 adalah
Vt −1 = 3)
4 . Pertanyaan berikutnya adalah bagaimana jika yang ingin dicari ialah 7
peluangnya jika diketahui V0 = 3. Dengan kata lain, ingin dicari peluang transisi t langkah yaitu P (Vt = 1 V0 = 3) .
Sebelumnya akan dibahas persamaan Chapman-Kolgomorov terlebih dahulu. Persamaan ini menyatakan bahwa peluang transisi dari keadaan i ke j dalam t langkah sama dengan peluang transisi dari i ke seluruh n-keadaan dalam t-m langkah, kemudian dilanjutkan dengan transisi ke keadaan j dari n-keadaan
11
tersebut dalam m langkah sisa. Dengan memanfaatkan Law of Total Probability dapat dibuktikan bahwa, p ij( t ) = P (V t = j V 0 = i ) =
n
∑
k =1
p ik( t − m ) p kj( m )
Untuk m = 1 maka diperoleh
p ij( t ) = p ij(( t −1) + 1) =
n
∑
k =1
p ik( t −1) p kj
(2.2.3)
Tampak bahwa persamaan diatas merupakan perkalian antara baris dan kolom dari dua matriks. Bila P(t) adalah matriks peluang transisi t langkah maka,
P (t ) = P (t−1) × P Dengan menggunakan induksi diperoleh
P ( t ) = (P × P ×
× P) × P
= P t −1 x P = Pt
(2.2.4)
Akibatnya, peluang berada di keadaan i saat ini dan di keadaan j setelah t kurun waktu, tidak lain adalah elemen baris ke-i dan kolom ke-j dari
P(t ) = P × P × × P = Pt t
Seringkali, selain perhitungan distribusi peluang di waktu ke-t, perhitungan distribusi peluang setelah proses berjalan lama yaitu πt untuk t → ∞ yang dinamakan distribusi limit juga menarik untuk dipelajari. Konsep ini sangat penting karena dapat memprediksi keadaan sistem setelah ia berjalan lama. Dengan kata lain, dapat dipelajari kelakuan dari sistem setelah ia ’stabil’. Untuk menganalisa kelakuan tersebut, kita memerlukan pengetahuan mendasar tentang klasifikasi dari keadaan suatu rantai makov. Akan tetapi, sebelumnya akan dibahas terlebih dahulu mengenai rantai Markov dengan matriks peluang transisi regular dan bagaimana distribusi limitnya. Misalkan P adalah matriks peluang transisi dari suatu rantai Markov dengan n keadaan yaitu 1, 2,…,n. Matriks P disebut regular jika memenuhi: (i)
Untuk setiap pasangan keadaan i dan j, selalu ada keadaan k1, k2,…, kt dimana pik1 pk1k2
(ii)
p kt j > 0 .
Sekurang-kurangnya terdapat satu keadaan i dimana pii > 0
12
Perhatikan syarat pertama untuk matriks regular dimana pik1 pk1k2
pkt j > 0 yang
merupakan komponen dari elemen-elemen matriks peluang transisi t langkah pada persamaan (2.2.3). Dari syarat tersebut, dapat disimpulkan bahwa untuk suatu matriks peluang transisi regular, maka terdapat t dimana peluang transisi dari satu keadaan ke keadaan lainnya dalam t langkah selalu bernilai positif. Dengan kata lain, maka secara sederhana suatu matriks peluang transisi P dikatakan regular jika memiliki sifat yaitu jika dipangkatkan oleh suatu konstanta positif k maka matriks Pk seluruh elemennya bernilai positif. Matriks peluang transisi yang demikian serta rantai Markov yang berkaitan dengannya disebut regular. Salah satu hal penting yang berkaitan dengan rantai Markov regular yaitu adanya distribusi peluang limit π = (π 1 , π 2 , n
∑π j =1
j
, π n ) dimana πj > 0 untuk j = 1, 2, …, n dan
= 1 . Secara formal, untuk matriks peluang transisi regular P, maka terdapat
konvergensi,
lim P(Vt = j V0 = i) = π j > 0, t →∞
j = 1, 2,
,n
(2.2.5)
Konvergensi ini memiliki arti bahwa untuk jangka waktu yang lama (t → ∞), peluang memperoleh rantai Markov berada pada keadaan j adalah πj tanpa mempedulikan keadaan awal yaitu saat 0. Berikut ini teorema yang dapat digunakan untuk mencari distribusi limit dari suatu rantai Markov regular, Teorema 1
Untuk P suatu matriks peluang transisi rantai Markov regular
dengan anggota ruang keadaannya 1, 2, …, n, maka distribusi limit
π = (π 1 , π 2 ,
, π n ) adalah solusi unik dari persamaan n
π j = ∑ π k pkj
j = 1, 2,
,n
(2.2.6)
k =1
dan n
πk =1 ∑ k =1
(2.2.7)
13
Memeriksa apakah suatu rantai Markov memiliki distribusi limit dengan melihat sifat regular matriks peluang transisinya memang mudah untuk dilakukan. Akan tetapi, dalam beberapa kasus elemen-elemen matriks peluang transisi seluruhnya baru akan bernilai positif untuk t yang sangat besar. Oleh karena itu, apalagi untuk rantai Markov yang memiliki banyak keadaan, cara ini tidak selalu memberikan hasil yang memuaskan. Dalam hal memeriksa apakah suatu rantai Markov memiliki distribusi limit tanpa melihat sifat regularnya, pengetahuan mengenai klasifikasi keadaan suatu rantai makov diperlukan. Tidak semua rantai Markov merupakan rantai Markov yang regular. Perhatikan beberapa contoh berikut ini. Rantai Markov yang mempunyai matriks peluang transisi berupa matriks identitas sebagai berikut,
⎡1 P = ⎢⎢ 0 ⎢⎣ 0
0⎤ 0 ⎥⎥ 1 ⎥⎦
0 1 0
Dari waktu ke waktu, rantai Markov ini tidak pernah berubah keadaan. Karena Pt = P untuk semua t, maka rantai Markov {Vt} mempunyai distribusi limit, yang bergantung pada keadaan awal. Sebaliknya, matriks peluang transisi berikut,
⎡0 P = ⎢⎢ 0 ⎢⎣ 1
0 1 0
1⎤ 0 ⎥⎥ 0 ⎥⎦
Rantai Markov ini akan selalu berubah, tidak pernah berada dalam keadaan yang sama untuk dua waktu yang berurutan. Rantai Markov ini bersifat periodik dan tidak mempunyai distribusi limit. Jika t ganjil, maka Pt = P, dan jika t genap, maka Pt adalah matriks identitas berukuran 3 x 3. Perhatikan matriks peluang transisi berikut ini,
⎡1 P = ⎢2 ⎢ ⎣0
1⎤ 2⎥ ⎥ 1⎦
Maka dapat dicari bahwa Pt adalah sebagai berikut,
14
t ⎡⎛ 1 ⎞t ⎛1⎞ ⎤ 1− ⎜ ⎟ ⎥ ⎢ P t = ⎢⎜⎝ 2 ⎟⎠ ⎝2⎠ ⎥ ⎢⎣ 0 1 ⎥⎦
dan limitnya adalah ⎡0 1⎤ lim P t = ⎢ ⎥ t →∞ ⎣0 1⎦ Disini, keadaan 1 adalah transient, yaitu setelah prosesnya dimulai dari keadaan 1 maka terdapat peluang yang positif bahwa keadaanya tidak akan kembali lagi. Suatu keadaan i dikatakan transient jika dan hanya jika, setelah proses yang berawal dari keadaan i, ada kemungkinan bahwa proses tersebut tidak akan kembali ke keadaan i. Sedangkan keadaan i dikatakan reccurent jika dan hanya jika, setelah proses berawal dari keadaan i, peluang untuk kembali ke keadaan i setelah suatu selang interval waktu tertentu sama dengan satu. Sebelum mendefinisikan keadaan transient dan reccurent secara matematis, terlebih dahulu definisikan fijt = P(Vt = j, Vu ≠ j , u = 1, 2,
, t -1 V0 = i ) yaitu
peluang dimana, dimulai dari keadaan i, proses akan pindah untuk pertama kali ke keadaan j dalam t langkah. Jadi, fiit = P(Vt = i, Vu ≠ j, u = 1, 2,
, t -1 V0 = i )
merupakan peluang proses pertamakali kembali ke keadaan i dalam t langkah. Selanjutnya, jika proses berawal dari keadaan i, maka peluang ia kembali ke keadaan i suatu waktu adalah ∞
T
fii = ∑ fii(t ) = lim ∑ fii( t ) T →∞
t =0
(2.2.8)
t =0
Jadi, berdasarkan definisi sebelumnya, jika i reccurent maka fii = 1 yaitu setelah proses berawal dari keadaan i, maka ia pasti akan kembali ke i dan jika i transient maka fii < 1. Teorema 2
Ruang keadaan i dikatakan reccurent jika dan hanya jika, ∞
∑p t =1
t ii
=∞
(2.2.9)
15
Dan ruang keadaan i dikatakan transient jika dan hanya jika, ∞
∑p t =1
t ii
<∞
(2.2.10)
Bukti Pertama, misalkan keadaan i merupakan transient dimana berdasarkan definisi fii < 1 dan M yang menyatakan banyaknya proses kembali ke keadaan i. Disini M berdistribusi geometrik dimana
P( M ≥ k V0 = i) = ( f ii )k ,
k =1,2,
dan
f E ⎡⎣ M V0 = i ⎤⎦ = ii 1 − f ii Tulis I sebagai peubah acak indikator ∞
⎧1
t =1
⎩0
I = ∑1{Vt = i} dengan 1{Vt } = ⎨
Vt = i Vt ≠ i
Karena i transient, maka dari definisi diperoleh E ⎡⎣ I V0 = i ⎤⎦ < ∞ sehingga ∞
∞
t =1
t =1
∑ pii(t ) = ∑ E ⎡⎣1{Vt = i} V0 = i ⎤⎦ = E ⎡⎣ I V0 = i ⎤⎦ < ∞ Sebaliknya, misalkan
∞
pii(t ) < ∞ maka ∑ t =1
E ⎡⎣ I V0 = i ⎤⎦ =
f ii <∞ 1 − f ii
⇒ 1 − f ii > 0 ⇒ f ii < 1 sehingga terbukti bahwa i merupakan transient. Dua sifat diatas merupakan contoh bagaimana sifat dari peluang transisi dan ruang keadaan akan mempengaruhi rantai Markov yang dibawanya. Beberapa definisi dan klasifikasi dari ruang keadaan dan matriks peluang transisi diperlukan untuk mengetahui berbagai macam kemungkinan mengenai sifat limit rantai Markov yang terkait.
16
Selanjutnya, akan dibahas konsep komunikasi sebagai berikut. Keadaan j dikatakan dapat dicapai (accessible) dari keadaan i jika terdapat bilangan bulat n ≥ 0 dimana pijn > 0 . Dengan kata lain, terdapat peluang positif bahwa dalam berhingga transisi keadaan j dapat dicapai dari keadaan i. Jika keadaan j dapat dicapai dari keadaan i dan keadaan i dapat dicapai dari keadaan j, maka i dan j dikatakan saling berkomunikasi, dan dinotasikan dengan i ↔ j. Jika dua keadaan i dan j tidak saling berkomunikasi, maka pijn = 0 atau p nji = 0 untuk setiap n ≥ 0.
Konsep komunikasi merupakan suatu relasi ekivalen. Perhatikan bahwa, (i)
Jika i adalah keadaan dari suatu rantai Markov sebarang, jelas bahwa i ↔ i karena pii = 1 (sifat refleksi).
(ii)
Jika i ↔ j, maka dari definisi berkomunikasi, j ↔ i karena i dapat dicapai dari j dan j dapat dicapai dari i (sifat simetri).
(iii)
Jika i ↔ j dan j ↔ k, maka i ↔ k (sifat transitif)
Bukti (sifat transitif) Misalkan i ↔ j dan misalkan j ↔ k, maka terdapat bilangan bulat positif n1 dan n2 sehingga pijn1 > 0 dan p nji2 > 0 . Sementara itu, terdapat bilangan bulat positif m1 dan m2 sehingga p mjk1 > 0 dan pkjm2 > 0 . Maka pikn1 + m1 > 0 dan pkin2 + m2 > 0 , atau dengan kata lain i ↔ k. Dengan relasi ekivalen tersebut, ruang keadaan suatu rantai Markov dapat dikelompokkan ke dalam kelas-kelas ekivalen. Jika suatu rantai Markov hanya memiliki satu kelas ekivalen, yaitu jika semua keadaannya saling berkomunikasi, maka rantai Markov tersebut disebut tak tereduksi. Selanjutnya, ada yang disebut sebagai periode rantai Markov. Periode dari keadaan i, dinotasikan dengan d(i), didefinisikan sebagai faktor persekutuan terbesar (FPB) dari semua bilangan bulat m ≥ 1 dengan piim ≥ 0 (Jika
piim = 0
untuk setiap m ≥ 1, didefinisikan d(i) = 0 ). Misalkan rantai Markov dengan matriks peluang transisi sebagai berikut,
17
⎡ ⎢ ⎢ P = ⎢ ⎢ ⎢ ⎢ ⎢⎣
0 1 3 1 2
1 0 1 2
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ 0 ⎥ ⎥⎦ 0 2 3
Jelas bahwa,
0 →1→ 0 0 →1→ 2 →1→ 0 1→ 2 →1 2 →1→ 2 2 →1→ 0 →1→ 2 Maka, d(0) = d(1) = d(2) = 2 Rantai Markov yang setiap ruang keadaannya memiliki periode 1 disebut aperiodik. Sebagian besar rantai Markov adalah aperiodik. Perhatikan suatu keadaan reccurent i, maka untuk Ri yang menyatakan waktu kembali pertama kali ke i, Ri = min{t ≥ 0;V0 = i}
Peluang kembali pertamakali ke i, fii dapat dituliskan sebagai berikut,
fiit = P( Ri = t V0 = i )
t = 1, 2,
Karena i merupakan keadaan yang bersifat reccurent, berlaku fii = 1. Maka, mean banyaknya transisi yang diperlukan untuk kembali ke keadaan i adalah ∞
ηi = E ⎡⎣ Ri V0 = i ⎤⎦ = ∑ tfiit t =1
Setelah mulai di i, selanjutnya secara rata-rata, proses akan berada di i satu kali setiap ηi = E ⎡⎣ Ri V0 = i ⎤⎦ satuan waktu. Teorema limit dasar rantai Markov berikut memperjelas hasil tersebut, Teorema 3 (Teorema Limit Dasar Rantai Markov) (i) Jika suatu rantai Markov yang tak tereduksi adalah positif reccurent dan aperiodik, maka terdapat limit peluang
18
lim piit = t →∞
1 ∞
∑ tf t =1
= t ii
1
ηi
,
i = 1, 2,
,n
(ii) Dibawah kondisi yang sama seperti di (i), lim pijt = lim p tjj untuk j = 1,2,… . t →∞
t →∞
Jika lim p tjj > 0 untuk satu i dalam kelas aperiodik reccurent, maka πj > 0 untuk t →∞
setiap j dalam kelas i. Dalam kasus ini, kelas tersebut dinamakan positif reccurent atau ergodik kuat. Jika setiap πj = 0 dan kelasnya reccurent, maka kelas tersebut dinamakan null reccurent atau ergodik lemah. Dalam istilah waktu pertama kembali, Ri = min{t ≥ 0;V0 = i} , keadaan i disebut positif reccurent jika mean banyaknya transisi yang diperlukan untuk kembali berhingga dan disebut null reccurent jika sebaliknya. Selanjutnya akan dilihat tentang peluang stasioner dari
teorema berikut ini, Teorema 4 Jika suatu rantai Markov yang tak tereduksi adalah positif reccurent dan aperiodik, maka terdapat limit peluang
lim pijt = π j > 0, t →∞
i, j = 1, 2,
,n
dimana bebas dari keadaan i pertama dengan πj untuk j=1,2,…,n dan πj disebut peluang stasioner untuk suatu rantai Markov (longrun fraction of transition entering j or leaving j).
Definisi 1 (Stasioner) Suatu distribusi peluang Pj, j ≥ 0 dikatakan stasioner untuk suatu rantai Markov jika ∞
∞
i =1
i =1
P (V1 = j ) = ∑ P (V1 = j V0 = i ) P (V0 = i ) = ∑ p j pij
dengan induksi dapat diperoleh, ∞
∞
i =1
i =1
P (Vt = j ) = ∑ P (Vt = j V0 = i ) P (V0 = i ) = ∑ p j pijt
Dengan kata lain, peluang stasioner adalah peluang dimana untuk suatu t → ∞ maka terjadinya transisi ke suatu keadaan, baik keluar maupun masuk dari suatu keadaan, nilainya relatif tidak berubah. Sehingga, πj itu sendiri merupakan solusi tunggal dari sistem persamaan linear,
19
n
π j = ∑ π k pij
j = 1, 2,
,n
(2.2.15)
i =1
dan n
∑π i =1
i
=1
Dalam bentuk matriks, persamaan diatas dapat ditulis sebagai, Π=Π P
(2.2.16)
dimana ⎡π1 ⎤ ⎢π ⎥ 2 Π=⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎢π n ⎦⎥
2.3
Orde Rantai Markov dan Sifat-Sifatnya
Pandang peluang bersyarat dari suatu rantai Markov pada persamaan (2.1.2). Andaikan peluang keadaan saat t, Vt tidak hanya bergantung kepada Vt-1 melainkan juga bergantung pada Vt-2, Vt-3, dan seterusnya, artinya kita bekerja dengan rantai Markov yang disebut sebagai rantai Markov berorde lebih dari satu. Definisi 2 (Orde Rantai Markov) Suatu rantai Markov dikatakan berorde-r atau Ō(r) jika kemunculan Vt hanya bergantung secara langsung pada r keadaan sebelumnya yaitu Vt-1, Vt-2, …, Vt-r dan independen dengan keadaan lainnya. Dengan demikian, untuk suatu Ō(r) berlaku P (Vt = it Vt −1 = it −1 , = P (Vt = it Vt −1 = it −1 ,
, Vt − ( r −1) = it − ( r −1) , Vt − r = it − r ,
, V0 = i0 )
, Vt − ( r −1) = it − ( r −1) , Vt − r = it − r ) = pit −r it −( r −1)
(2.3.1)
it −1it
Berdasarkan definisi diatas, untuk selanjutnya rantai Markov yang telah umum dikenal seperti pada (2.1.2) dinamakan rantai Markov berorde-1, Ō(1) dan jika setiap keadaannya tidak bergantung satu sama lain atau saling bebas maka dinamakan rantai Markov berorde-0, Ō(0).
20
Taylor dan Karlin [3] memberi saran mengenai penulisan peluang transisi dan matriks peluang transisi untuk rantai Markov berorde tinggi. Dalam literatur tersebut memang tidak disebutkan secara langsung mengenai orde rantai Markov melainkan hanya diberikan ilustrasi berikut sebagai contoh, Contoh 1 (Rantai Markov Orde-2) Misalkan cuaca pada suatu hari bergantung pada keadaan cuaca selama dua hari sebelumnya. Diketahui bahwa jika hari ini dan kemarin cerah, maka besok akan cerah juga dengan peluang 0,8; jika hari ini cerah tapi kemarin hujan, maka besok akan cerah dengan peluang 0,6; jika hari ini hujan tapi kemarin cerah, maka besok akan cerah dengan peluang 0,4; dan jika terjadi baik hari ini maupun kemarin hujan, peluang besok cerah adalah sebesar 0,1. Dengan Vt menyatakan keadaan saat t, Vt +1 ∈S={1 ≡ hujan, 2 ≡ cerah} peluang transisinya dapat ditulis sebagai berikut, P (Vt +1 = it +1 Vt = it , Vt −1 = it −1 ) = P (Vt +1 = it +1 , Vt = it Vt = it , Vt −1 = it −1 ) = pit−1it it +1
(2.3.2)
dan matriks peluang tansisinya adalah, (1,1) (1,2) (2,1) (2,2) (1,1) ⎡ P111 (1,2) ⎢⎢ 0 P= (2,1) ⎢ P211 ⎢ (2,2) ⎣ 0
P112
0
0
P121
P212
0
0
P221
0 ⎤ ⎡ 0,8 0, 2 0 0 ⎤ ⎥ ⎢ P122 ⎥ 0 0 0, 4 0, 6 ⎥⎥ ⎢ = 0 ⎥ ⎢ 0, 6 0, 4 0 0 ⎥ ⎥ ⎢ ⎥ P222 ⎦ ⎣ 0 0 0,1 0,9 ⎦
(2.3.3)
Terdapat elemen-elemen bernilai 0 misalnya pada baris pertama, P (Vt +1 = 1, Vt = 2 Vt = 1, Vt −1 = 1) = 0 P (Vt +1 = 2, Vt = 2 Vt = 1, Vt −1 = 1) = 0
karena tidak mungkin proses berada pada dua keadaan yang berbeda dalam satu kurun waktu dimana dalam hal ini Vt = 1 dan Vt = 2 sekaligus. Dengan menulis peluang transisinya seperti pada (2.3.2), secara tersirat keadaannya sekarang menjadi ( Vt−1 , Vt )∈S*={(1,1),(1,2),(2,1),(2,2)} dimana S* adalah ruang keadaan baru dimana anggota-anggotanya merupakan pasangan terurut dari anggota ruang keadaan semula. Secara umum berdasarkan (2.3.2), menurut Taylor dan Karlin peluang transisi untuk Ō(r) adalah,
21
P (Vt = it Vt −1 = it −1 , = P(Vt = it , Vt −1 = it −1 , = pit −r it−( r −1)
, Vt − ( r −1) = it −( r −1) , Vt − r = it − r ) ,Vt −( r −1) = it − ( r −1) Vt −1 = it −1 ,
, Vt − ( r −1) = it − ( r −1) , Vt − r = it − r ) (2.3.4)
it −1it
Sementara itu, berdasarkan (2.3.4) maka matriks peluang transisinya adalah,
⎡ p11 11 ⎢ 0 ⎢ ⎢ ⎢ ⎢ 0 ⎢ p21 11 ⎢ ⎢ 0 P=⎢ ⎢ ⎢ 0 ⎢ ⎢ ⎢ pn1 11 ⎢ ⎢ 0 ⎢ ⎢ ⎢⎣ 0
p11 1n 0 0 p21
1n
0 p11
0 21
0 0
p11
2n
0 0
0 0
0 0
0 0
0 p1n n1 0 0
0
0
0
p21
0
0
0
0
0 p2n
pn1 1n 0
0
0
0 0
0 0
0
0 pnn
0
pn1
21
21
0
p21
0 0
pn1
2n
2n
0
0
n1
0 0
n1
0 ⎤ 0 ⎥⎥ ⎥ ⎥ p1n nn ⎥ 0 ⎥ ⎥ 0 ⎥ ⎥ ⎥ p2n nn ⎥ ⎥ ⎥ 0 ⎥ ⎥ 0 ⎥ ⎥ ⎥ pnn nn ⎥⎦
(2.3.5)
yaitu sebuah matriks persegi berukuran nr x nr dengan elemen-elemennya,
pij
kl
= P (Vt = l Vt −1 = k ,
, Vt − r +1 = j , Vt − r = i )
= P (Vt = l , Vt −1 = k ,
, Vt − r +1 = j Vt −1 = k ,
, Vt − r +1 = j , Vt − r = i )
Dengan mempertahankan bentuk tersebut, kita dapat melakukan perhitungan seperti mencari matriks peluang transisi t langkah dan distribusi stasioner dengan cara yang serupa dengan Ō(1). Perhatikan bahwa berdasarkan (2.2.3) dan (2.3.4) maka peluang transisi t langkahnya adalah,
22
n
P(Vt +1 = l V1 = j,V0 = i) = ∑ P(Vt +1 = l ,Vt = k V1 = j,V0 = i) k =1
n
= ∑ P(Vt +1 = l Vt = k ,V0 = i)P(Vt = k V1 = j,V0 = i) k =1 n
= ∑ P(Vt +1 = l ,Vt = k Vt = k ,V0 = i)P(Vt = k ,V1 = j V1 = j,V0 = i)
(2.3.6)
k =1
Bila P(t) adalah matriks peluang transisi t langkah maka,
P (t ) = P (t−1) × P dengan menggunakan induksi diperoleh
P ( t ) = (P × P ×
× P) × P
= P t −1 × P = Pt
(2.3.7)
Disini, sifat dari matriks peluang transisi t langkah sebagai pangkat t dari matriks peluang transisi satu langkah dipertahankan untuk Ō(r) dengan matriks peluang transisi seperti pada (2.3.5). Sebagai contoh dari (2.3.3) akan dihitung peluang transisi untuk 2 langkah yaitu
P(Vt + 2 = it + 2 Vt = it , Vt −1 = it −1 ) . Karena, P2 = P × P 0 ⎤ ⎡ 0,8 0, 2 0 0 ⎤ ⎡ 0.64 ⎡ 0,8 0, 2 0 ⎢ 0 ⎥ ⎢ 0 0, 4 0, 6 ⎥ ⎢ 0 0 0, 4 0, 6 ⎥⎥ ⎢⎢ 0.24 ⎢ = = ⎢ 0, 6 0, 4 0 0 ⎥ ⎢0, 6 0, 4 0 0 ⎥ ⎢ 0.48 ⎢ ⎥⎢ ⎥ ⎢ 0 0,1 0,9 ⎦ ⎣ 0 0 0,1 0,9 ⎦ ⎣ 0.06 ⎣ 0
0.16 0.08 0.12 ⎤ 0.16 0.06 0.54 ⎥⎥ 0.12 0.16 0.24 ⎥ ⎥ 0.04 0.09 0.81⎦
dengan elemen-elemennya adalah P(Vt + 2 = it + 2 ,Vt +1 = it +1 Vt = it ,Vt −1 = it −1 ) maka peluang transisi 2 langkahnya adalah, 2
(i) P(Vt +2 = 1 Vt = 1,Vt −1 = 1) = ∑P(Vt +2 = 1,Vt +1 = k Vt = 1,Vt−1 = 1) = 0.64 + 0.08 = 0.72 k =1
2
(ii) P(Vt +2 = 2 Vt = 1,Vt −1 = 1) = ∑P(Vt +2 = 2,Vt+1 = k Vt = 1,Vt −1 = 1) = 0.16 + 0.12 = 0.28 k =1
2
(iii) P(Vt +2 = 1 Vt = 2,Vt −1 = 1) = ∑P(Vt +2 = 1,Vt+1 = k Vt = 2,Vt−1 = 1) = 0.24 + 0.06 = 0.3 k =1
23
2
(iv) P(Vt +2 = 2 Vt = 2,Vt −1 = 1) = ∑P(Vt +2 = 2,Vt+1 = k Vt = 2,Vt −1 = 1) = 0.16 + 0.54 = 0.70 k =1
2
(v) P(Vt +2 = 1 Vt = 1,Vt −1 = 2) = ∑P(Vt +2 = 1,Vt+1 = k Vt = 1,Vt−1 = 2) = 0.48 + 0.16 = 0.64 k =1
2
(vi) P(Vt +2 = 2 Vt = 1,Vt −1 = 2) = ∑P(Vt +2 = 2,Vt+1 = k Vt = 1,Vt −1 = 2) = 0.12 + 0.24 = 0.36 k =1
2
(vii) P(Vt +2 = 1 Vt = 2,Vt −1 = 2) = ∑P(Vt +2 = 1,Vt +1 = k Vt = 2,Vt−1 = 2) = 0.06 + 0.09 = 0.15 k =1
2
(viii) P(Vt +2 = 2 Vt = 2,Vt −1 = 2) = ∑P(Vt +2 = 2,Vt +1 = k Vt = 2,Vt −1 = 2) = 0.04 + 0.81 = 0.85 k =1
Selanjutnya untuk t → ∞, t
0 ⎤ ⎡0.2727 ⎡ 0,8 0, 2 0 ⎢ 0 0 0, 4 0, 6 ⎥⎥ ⎢⎢0.2727 t ⎢ lim P = lim = t →∞ t →∞ ⎢ 0, 6 0, 4 0 0 ⎥ ⎢0.2727 ⎢ ⎥ ⎢ 0 0,1 0,9 ⎦ ⎣0.2727 ⎣ 0
0.0909 0.0909 0.0909 0.0909
0.0909 0.0909 0.0909 0.0909
0.5455⎤ 0.5455⎥⎥ 0.5455⎥ ⎥ 0.5455⎦
dengan (i) π1 = P(Vt = 1) = P(Vt = 1,Vt −1 = 1) + P(Vt = 1,Vt −1 = 2) = 0.2727 + 0.0909 = 0.3636 (ii) π2 = P(Vt = 2) = P(Vt = 2,Vt −1 = 1) + P(Vt = 2,Vt −1 = 2) = 0.0909 + 0.5455 = 0.6364 Meski secara matematis menjadi lebih mudah, penulisan matriks peluang transisi seperti ini akan menimbulkan kesulitan dalam perhitungan. Untuk matriks berukuran nr x nr, sekurang-kurangnya terdapat (nr-n) x nr elemen bernilai nol dan hanya nr x n elemen yang menyatakan peluang transisi sebenarnya. Oleh karena itu, bagi Ō(r) diperlukan matriks peluang transisi yang lebih sederhana dan ringkas dari (2.3.5). Salah satu cara untuk menyederhanakan matriks untuk rantai Markov berorde lebih dari satu adalah dengan hanya memperhatikan elemen yang menyatakan peluang transisi sebenarnya dan menghilangkan sisanya yaitu sebanyak (nr-n) x nr elemen bernilai nol. Cara penulisan seperti ini secara umum akan menghasilkan matriks berukuran nr x n,
24
⎡ p11 ⎢p ⎢ 11 ⎢ ⎢ ⎢ p1n ⎢ p21 ⎢ ⎢ p21 P=⎢ ⎢ ⎢ p2 n ⎢ ⎢ ⎢ p n1 ⎢ ⎢ p n1 ⎢ ⎢ ⎣⎢ pnn
11 21
p11 p11
12 22
11
p1n p21
12
21
p21
22
n1
p2 n
n1
21
p n1 p n1
n1
pnn
11
n2
n2
12 22
n2
⎤ ⎥ 2n ⎥ ⎥ ⎥ p1n nn ⎥ p21 1n ⎥ ⎥ p21 21n ⎥ ⎥ ⎥ p2 n nn ⎥ ⎥ ⎥ p n1 1 n ⎥ ⎥ p n1 n n ⎥ ⎥ ⎥ pnn nn ⎥⎦ p11 p11
dengan
pij
kl
1n
(2.3.8)
elemen-elemennya
= P ( Vt = l Vt −1 = k ,
, Vt − r +1 = j , Vt − r = i ) .
Berdasarkan (2.3.8), pada Contoh 1 matriks peluang transisinya cukup ditulis, ⎡ p111 ⎢p P = ⎢ 121 ⎢ p211 ⎢ ⎣⎢ p221
p112 ⎤ ⎡ 0,8 p122 ⎥⎥ ⎢0, 4 =⎢ p212 ⎥ ⎢ 0, 6 ⎥ ⎢ p222 ⎦⎥ ⎣ 0,1
0, 2 ⎤ 0, 6 ⎥⎥ 0, 4 ⎥ ⎥ 0,9 ⎦
Untuk matriks peluang transisi yang telah dimodifikasi seperti pada (2.3.8), perkalian matriks secara biasa tidak dapat dilakukan karena banyaknya kolom matriks tersebut adalah n dan banyaknya baris adalah nr. Oleh karena itu, diperlukan aturan perkalian matriks yang berbeda. Aturan perkalian yang baru tentunya harus tetap mempertahankan persamaan Chapmann-Kolmogorof karena tujuan mengalikan matriks disini adalah untuk mencari matriks peluang transisi t langkah.
25
Perhatikan persamaan (2.2.4) dengan t = 2 dan P adalah matriks seperti pada (2.3.8). Di sini yang diinginkan adalah P(2) = P2 = P x P. Berdasarkan (2.3.6) elemen-elemen dari P2 adalah, n
P(Vt +2 = l Vt = j,Vt −1 = i) = ∑ P(Vt +2 = l Vt +1 = k ,Vt = i)P(Vt +1 = k Vt = j,Vt −1 = i) k =1
n
⇒ pijl(2) = ∑ pijk p jkl
(2.3.9)
k =1
Oleh karena itu, langkah-langkah perkaliannya adalah sebagai berikut, (i)
Bagi matriks P kedalam n submatriks Anxn sebagai berikut,
⎡ A1 ⎤ ⎢ ⎥ A P = ⎢ 2⎥ ⎢ ⎥ ⎢ ⎥ ⎢⎣ A n ⎥⎦ dengan i ⎡ a11 a12i ⎢ i a ai Ai = ⎢ 21 22 ⎢ ⎢ i i ⎢⎣ an1 an 2
(ii)
a1in ⎤ ⎡ pi1 ⎥ ⎢ a2i n ⎥ ⎢ pi1 ⎥ i ⎥ ann ⎥⎦
=
⎢ ⎢ ⎢⎣ pin
21
pi1 pi1
n1
pin
11
12 22
n2
⎤ ⎥ 2n ⎥ ⎥ , i = 1,2,…,n ⎥ pin nn ⎥⎦
pi1 pi1
1n
Elemen baris ke-i submatriks ke-j dari P2 adalah perkalian antara baris ke-i submatiks ke-j dari P dengan submatriks ke-i dari P.
(iii)
Matriks peluang transisi t langkahnya adalah Pt = P x Pt-1.
Sebagai contoh, dari Contoh 1 maka matriks peluang transisinya adalah, ⎡ 0,8 ⎢0, 4 P=⎢ ⎢ 0, 6 ⎢ ⎣ 0,1
0, 2 ⎤ 0, 6 ⎥⎥ ⎡ A1 ⎤ = 0, 4 ⎥ ⎢⎣ A 2 ⎥⎦ ⎥ 0,9 ⎦
⎡ 0.8 0.2 ⎤ ⎡0.6 0.4 ⎤ dan A 2 = ⎢ dengan A1 = ⎢ ⎥ ⎥ . Maka matriks peluang transisi dua ⎣ 0.4 0.6 ⎦ ⎣ 0.1 0.9 ⎦ langkahnya adalah,
26
P2 = P × P
⎡ 0,8 ⎢0, 4 =⎢ ⎢ 0, 6 ⎢ ⎣ 0,1
0, 2 ⎤ ⎡ 0,8 0, 6 ⎥⎥ ⎢⎢0, 4 0, 4 ⎥ ⎢ 0, 6 ⎥⎢ 0,9 ⎦ ⎣ 0,1
0, 2 ⎤ ⎡0.72 0.28⎤ 0, 6 ⎥⎥ ⎢⎢ 0.3 0.7 ⎥⎥ = 0, 4 ⎥ ⎢0.54 0.36⎥ ⎥ ⎢ ⎥ 0,9 ⎦ ⎣ 0.15 0.85⎦
Selanjutnya untuk t → ∞, ⎡ 0,8 ⎢0, 4 t lim P = lim ⎢ t →∞ t →∞ ⎢ 0, 6 ⎢ ⎣ 0,1
t
0, 2 ⎤ ⎡0.3636 0, 6 ⎥⎥ ⎢⎢0.3636 = 0, 4 ⎥ ⎢0.3636 ⎥ ⎢ 0,9 ⎦ ⎣0.3636
0.6364 ⎤ 0.6364 ⎥⎥ 0.6364 ⎥ ⎥ 0.6364 ⎦
27
