Proses Stokastik [PDF]

Citation preview

Proses Stokastik (Rantai Markov) Model Rantai Markov (bentuk diskrit dari pure jump Markov process). Teori Singkat Rantai Markov adalah sebuah model stokastik dari suatu sistem. Bentuk yang sangat disederhanakan dari rantai Markov meliputi: 



Keadaan/status yang dimodelkan oleh sebuah bilangan bulat x.







Ruang Status S, yaitu himpunan semua keadaan-keadaan/status-status (states). Contoh: S = {0, 1} (ruang berhingga), S = {1, 2, 4, 8, …} (ruang tak hingga).







Waktu pengamatan ke-n yang dimodelkan oleh bilangan cacah n {0, 1, 2, }







X1, X2, X3, …, Xn, … adalah peubah-peubah acak yang terdefinisi pd ruang peluang yang sama, masing-masing menyatakan nilai status pada pengamatan ke-1, ke-2, ke-3, …, ken, …, dst terhadap sistem. Jadi Xn = x menyatakan bahwa hasil pengamatan ke-n terhadap status sistem adalah (bil bulat) x. Keberadaan peubah-peubah acak di atas akan menjadi penting setelah ditambahkan persyaratan: X1, X2, X3, …, Xn, … adalah saling bebas.







Sifat Markov: Jika xn menyatakan status hasil pengamatan sekarang, maka statusx0, x1, x2, …, xn1 dari hasil pengamatan-pengamatan sebelumnya tidak akan mempengaruhi xn+1, hasil pengamatan yang akan datang. Sifat ini dirumuskan sbb: P(Xn+1 = xn+1 | X0 = x0, X1 = x1, …, Xn1 = xn1, Xn = xn) = P(Xn+1 = xn+1 | Xn = xn).(1)







Peluang P(Xn+1 = y | Xn = x) disebut peluang transisi sistem dari status x ke statusy. Pada umumnya, nilai peluang ini tergantung pada n. Dalam sistem yang dibicarakan di sini, nilai peluang transisi dianggap tidak tergantung pada n, yaitu P(X1 = y | X0 = x) = P(X2 = y | X1 = x) = … = P(Xn+1 = y | Xn = x). (2)



dan disebut peluang transisi stasioner (stationary transition probability). Isi bagian-bagian yang kosong dalam uraian berikut ini! 1. Sebuah Model Peluang: Akan dimodelkan status PC bekas yang baru dibeli dengan barisan peubah-peubah acak X1, X2, X3, … yang berdistribusi sama. Nilai Xn = 0 menyatakan PC dalam status/keadaan rusak di awal hari ke-n sedangkan nilai Xn = 1 menyatakan PC dalam status/keadaan baik di awal hari ke-n (setelah hari pembelian). Apabila PC dalam keadaan rusak pada awal hari ke-n dan a adalah peluang PC bisa diperbaiki (dan kemudian dalam keadaan baik) di awal hari ke-(n + 1), maka peluang ini dilambangkan (dengan notasi peluang bersyarat) oleh …. 1) = a. Sebaliknya apabila PC dalam keadaan baik pada awal hari ke-n dan b adalah peluang PC dalam keadaan rusak di awal hari



ke-(n + 1), maka peluang ini dilambangkan dengan (notasi peluang bersyarat) …. 2) = b. Jadi berdasarkan sifat peluang, P(Xn+1 = 0 | Xn = 0) = ….3) dan P(Xn+1 = 1 | Xn = 1) = ….4). Misalkan peluang PC rusak sejak dibeli dari toko adalah p, yaitu peluang X0 = 0 adalah ?0(0) = P(X0 = 0) = p. (3) Berdasarkan sifat peluang, ?0(1) = P(X0 = 1) = ….5). Karena kejadian {Xn = 0} dan {Xn = 1} saling lepas (ME), maka P(Xn+1 = 0) = P(Xn = 0 dan Xn+1 = 0)[*]) + ….6) = P(Xn = 0)….7) + P(Xn = 1)….8) (definisi peluang bersyarat) = P(Xn = 0)(1  a) + ….9) (dari jawaban 2)) = P(Xn = 0)(1  a) + b(1  P(Xn = 0)) (sifat peluang) = (1  a  b)P(Xn = 0) + b. (4) Dengan substitusi n = 0, 1, 2, …, dst pada (4), dan mengingat ekspresi (3), diperoleh P(X1 = 0) = (1  a  b)?0(0) + b; P(X2 = 0) = ….10) + b = ….11)?0(0) + b(1 + (1 a  b)); P(X3 = 0) = ….12) + b = ….13)?0(0) + b(1 + (1 a  b) + (1 a  b)2); 16) P(Xn = 0) = ….14) + b = ….15)?0(0) + b . (5)



Untuk kasus (trivial) a = b = 0 yang merupakan model matematis untuk kasus: sejak dibeli dari toko, status PC (rusak atau baik) tak pernah berubah untuk selamanya. Dalam kasus ini, substitusi a = b = 0 pada (5) memberikan P(Xn = 0) = ….17) dan P(Xn = 0) = ….18). Untuk kasus a + b > 0, karena 0 a 1 dan 0 b 1 (sebab ….19)), maka berlaku 0 < a + b 2 yang ekuivalen dg 1 1  a  b < 1 (Penjabarannya: ….20)). Dari rumus deret ukur (geometric series) dengan pembanding 1  a  b, berlaku .



Apabila hasil ini disubstitusi ke persamaan (5), diperoleh P(Xn = 0) = (1  a  b)n ?0(0) + 



=



+ (1  a  b)n( ?0(0) 



Sebagai akibatnya, P(Xn = 1) = 1  ….21) (sifat peluang) =1  (1  a  b)n( ?0(0) 



). (6)



) (dari (6))



=







 (1  a  b)n(1  ….22) 



=



 (1  a  b)n(….23)  ?0(1)) (sebab 1 =



=



+ (1  a  b)n(?0(1) 



) (sifat peluang) )



). (7)



Apabila diasumsikan lebih jauh bahwa a dan b tak pernah bersama-sama bernilai 1 (dengan kata lain a + b < 2), selain asumsi a + b > 0, nilai mutlak suku pembanding dari deret ukur di atas adalah |1  a  b| < 1 sehingga limit n terhadap (6) dan (7) bisa diberlakukan: ….24) = dan ….25) = . Dengan substitusi ?0(0) =



dan ?0(1) =



masing-masing ke dalam ekspresi



(6) dan (7), diperoleh hasil bahwa kedua nilai P(Xn = 0) = ….26) dan P(Xn = 1) = ….27)tidak tergantung pada n. 2. Model Rantai Markov (Lanjutan): Sampai sejauh ini, sifat Markov belum diberlakukan pada sistem. Sekarang X1, X2, …,Xn, … dianggap memenuhi sifat Markov (1). Ini berarti X1, X2, …, Xn, … tidak saling independen, sebab ….28). Misalkan n = 2 dan x0, x1, x2 {0, 1}. P(X0 = x0, X1 = x1, X2 = x2) = P(X0 = x0, X1 = x1)P(….29)) (definisi peluang bersyarat) = P(….30))P(….29)) (definisi peluang bersyarat) = P(X0 = x0)P(X1 = x1| X0 = x0)P(X2 = x2| X1 = x1), berdasarkan sifat Markov. Pada langkah terakhir ini, sifat Markov berperan dan bisa digunakan untuk membantu pencarian nilai peluang P(X0 = x0, X1 = x1, X2 = x2). Mis. dari hasil di atas diperoleh P(X0 = 0, X1 = 1, X2 = 0) = P(X0 = 0)P(X1 = 1| X0 = 0)P(X2 = 0| X1 = 1) = ?0(0)(….31)) Dengan cara yang analog, diperoleh tabel daftar nilai-nilai P(X0 = x0, X1 = x1, X2 = x2) untuk semua kemungkinan status x0, x1 dan x2. x0 x1 x2 P(X0 = x0, X1 = x1, X2 = x2) 0 0 0 ?0(0)(1  a)2 0 0 1 ….32) 0 1 0 ….31) 0 1 1 ….33) 1 0 0 (1 ?0(0))b(1  a)



1 1 1



0 1 1



1 0 1



….34) ….35) ….36)



3. Fungsi Transisi dan Distribusi Awal Misalkan Xn, n = 0, 1, 2, … adalah rantai Markov dengan himpunan status/keadaan S. Tidak lagi ada asumsi S = {0,1}. Dalam kasus diskrit, hanya ada dua kemungkinan untuk S: a. Sberhingga, atau b. S tak hingga. Dalam kasus S berhingga (kemungkinan a), selalu dianggap S = {0, 1, 2, …, d}. Untuk kemungkinan b, selalu dianggap S = {…, 3, 2, 1, 0, 1, 2, 3, …}, yaitu himpunan tak hingga terhitung (countable, tidak bisa tak terhitung, sebab sistem dianggap diskrit). Untuk setiap pasang status x, y S, fungsi (atau peluang) transisi P(x, y) []) P(x, y) = P(X1 = y| X0 = x) menyatakan nilai peluang keadaan sistem berubah dari x menjadi y. Karena sistem memenuhi (2), yaitu sistem bersifat ….37), maka untuk setiap n = 0, 1, 2, … berlaku ….38) =P(X1 = y| X0 = x). Lebih jauh, P(x, y) memenuhi sifat-sifat fungsi peluang massa dua peubah: i. Untuk setiap pasang keadaan x, y S, berlaku ….39). ii. Untuk setiap keadaan x S, berlaku . (Untuk kasus S berhingga dengan |S| = d, perumusan ii di atas adalah ….40). Distribusi awal dari suatu rantai Markov adalah suatu fungsi peluang (FPM) ?0 yang memenuhi sifat-sifat fungsi peluang massa satu peubah: i. Untuk setiap keadaan s S, ….41). 42) ii. (atau dalam kasus S berhingga dengan |S| = d, ….43)). Adanya kemungkinan keadaan awal sistem adalah x (dengan peluang sebesar ?0(x) 0) dinyatakan lewat definisi berikut ?0(x0) = P(X0 = x0). Peluang keadaan awal X0 = x berubah menjadi keadaan X1 = y diilustrasikan sbb: X0 = x sistem X1 = y



Menurut aturan peluang bersyarat P(X0 = x0, X1 = x1) = P(X0 = x0) ….44) = ….45). Demikian pula, P(X0 = x0, X1 = x1, X2 = x2) = P(X0 = x0, X1 = x1) ….46) = ?0(x0) ….47). Karena sifat Markov (1), P(X2 = x2 | X0 = x0, X1 = x1) = P(X2 = x2 | X1 = x1) sehingga P(X0 = x0, X1 = x1, X2 = x2) = ?0(x0) P(x0, x1) P(X2 = x2 | X1 = x1). = ?0(x0) P(x0, x1) P(x1, x2).



Dengan induksi, bisa dibuktikan bentuk umum dari kedua hasil di atas yang merupakan perumusan distribusi bersama dari n + 1 peubah acak X0, X1, , Xn sebagai berikut, P(X0 = x0, X1 = x1, X2 = x2, , Xn = xn) = ?0(x0) P(x0, x1) P(x1, x2) P(xn1, xn). (8) 4. Model-model Lain: Model dengan himpunan status {0, 1} di atas adalah model yang sangat sederhana. Berikut empat perumusan lebih kompleks dan lebih dikenal untuk model Ranntai Markov sebagai pendekatan matematis terhadap beberapa masalah nyata: 1. Simple Random Walk, jika Xn = x, maka y = Xn+1 {x  1, x, x + 1} {-2, , -1, 0, 1, 2, } dan P(x,y) =



Boleh juga mencari real world problem yang bias dimodelkan oleh bentuk umumRandom Walk yang didefinisikan melalui peubah acak ?0 = X0, ?1, ?2, yang berdistribusi sama, bernilai bulat dan saling independent, sebagai berikut: Xn+1 = X0 + ?1 + ?2 + + ?n. 2. Ehrenfest Chain, jika Xn = x, maka y = Xn+1 {x  1, x + 1}. P(x,y) =



3. Rantai Penjudi Bangkrut (Gamblers ruin chain) P(x,y) =



Ada dua versi rantai ini: a. Versi 1, state spacenya adalah S = {0, 1, 2, 3, } Di asumsikan ada absorbing state x = 0 (bankrupty state). a. Versi 2, state spacenya adalah S = {0, 1, 2, 3, , d} Di asumsikan ada dua absorbing state, yaitu x = 0 (bankrupty state) dan x = d(dengan kata lain, salah satu pihak bermodal terbatas sebanyak d). Model 2 dan 3 di atas adalah bentuk khusus dari model matematis 4. Birth and deaths process dengan dua pilihan S = {0, 1, 2, 3, } atau S = {0, 1, 2, 3, , d}, dan



P(x,y) =



Teori Singkat Rantai Markov Murni Pandang suatu proses stokastik X(t) dengan t T. Apabila T = {t0, t1, , tn, tn+1}, t0 < t1