ma4081 pengantar proses stokastik bab 3 rantai markov · ilustrasi rantai markov peluang n-langkah...

Silabus dan Tujuan PerkuliahanIlustrasi

Rantai MarkovPeluang n-langkah

Peluang Transisi Tak BersyaratLatihan

Program MATLABJenis Keadaan

Limit Peluang TransisiLATIHAN

MA4081 PENGANTAR PROSES STOKASTIKBab 3 Rantai Markov

Dosen: Khreshna I.A. Syuhada, MSc. PhD.

“Cerdas dan Stokastik”

Dosen: Khreshna I.A. Syuhada, MSc. PhD. MA4081 PENGANTAR PROSES STOKASTIK Bab 3 Rantai Markov






SilabusTujuan

Silabus

Definisi rantai Markov, sifat Markov, peluang transisi n-langkah,persamaan Chapman-Kolmogorov, jenis keadaan, recurrent dantransient, limit peluang transisi (kestasioneran).







SilabusTujuan

Tujuan

1 Mempelajari model rantai Markov

2 Menghitung peluang transisi n-langkah

3 Menerapkan persamaan Chapman-Kolmogorov

4 Menentukan keadaan yang dapat diakses dan berkomunikasi

5 Menentukan keadaan-keadaan recurrent dan transient

6 Menghitung peluang transisi untuk jangka panjang







Ilustrasi 1

Perilaku bunuh diri kini kian menjadi-jadi. Hesti (namasebenarnya) adalah sebuah contoh. Dia pernah melakukanpercobaan bunuh diri, namun gagal. Menurut pakar, kalau padasuatu waktu seseorang melakukan percobaan bunuh diri makabesar kemungkinan dia akan melakukannya lagi di masamendatang. Jika seseorang belum pernah melakukan percobaanbunuh diri, di masa mendatang orang tersebut akan mungkinmelakukan percobaan bunuh diri. Deskripsikan fenomena diatassebagai model peluang (probability model).







Ilustrasi 2

“Pada 23 Juni lalu sekitar pukul 21.30 mobil yang dikemudikansuami saya terperosok masuk lubang di jalan tol lingkar luarJakarta, kira-kira 2 kilometer dari Pintu Tol Pondok Ranji arahJakarta. Ban dan gadi-gading roda rusak. Esoknya sayamengajukan klaim asuransi Sinar Mas kepada SiMas Bekasi. Pada1 Juli saya mendapat jawaban bahwa klaim asuransi ditolak denganalasan: bagian yang rusak hanya ban dan gading-gading roda. Takmengenai badan mobil.







Padahal, tercantum jelas di dalam pasal-pasal polis asuransimaupun surat penolakan bahwa ban dan gading-gading roda tidakdijamin, kecuali disebabkan oleh Pasal 1 angka 1.1. Isi pasal itu,pertanggungan ini menjamin kerusakan yang secara langsungdisebabkan oleh tabrakan, benturan, terbalik, tergelincir atauterperosok. Asuransi Sinar Mas berusaha menghindar darikewajiban dengan alasan mengada-ada, bahkan mengingkari aturanyang dibuatnya sendiri” (Surat Pembaca KOMPAS; 03/08/2010).Andaikan suatu hari saya mengajukan klaim lagi ke Asuransi SinarMas, berapa peluang bahwa klaim saya akan diterima?







Ilustrasi 3

Permainan. Foto.







Ilustrasi 4

Loyalitas konsumen terhadap suatu merek barang. Wilkie (1994)mendefinisikan “brand loyalty as a favorable attitude toward andconsistent purchase of a particular brand”. Lyong (1998): “brandloyalty is a function of a brands’ relative frequency of purchase inboth time-independent and time-dependent situations”. Seorangkonsumen pembeli merek barang A diharapkan akan terus membelibarang A. Mungkinkah ini terjadi? Apakah model statistika yangdapat dengan tepat (atau mendekati tepat) merinci peluangterjadinya hal ini? Apakah model ini membantu dalam strategipemasaran suatu barang?







Ilustrasi 5

Akhir-akhir ini, hujan dan panas (baca: tidak hujan) datang silihberganti tanpa bisa diduga. Kalau hari ini hujan, besok mungkinhujan mungkin juga panas. Tentu saja peluang besok hujan akanlebih besar dibanding peluang besok akan panas. Begitu pula jikahari ini panas. Besok akan lebih mungkin panas dibandingkanhujan. Jika hari Senin hujan, berapa peluang bahwa hari Selasaakan hujan? Berapa peluang bahwa hari Kamis akan hujan?







Ilustrasi 6

Sebagai calon atlet, setiap pagi Swari meninggalkan rumahnyauntuk berlari pagi. Swari akan pergi lewat pintu depan ataubelakang dengan peluang sama. Ketika meninggalkan rumah,Swari memakai sepatu olah raga atau bertelanjang kaki jika sepatutidak tersedia di depan pintu yang dia lewati. Ketika pulang, Swariakan masuk lewat pintu depan atau belakang dan meletakkansepatunya dengan peluang sama. Diketahui bahwa Swari memiliki4 pasang sepatu olah raga. Berapa peluang bahwa Swari akansering berolah raga dengan bertelanjang kaki?







Ilustrasi 7

Hutang tak terbayar.Hutang atau rugi dimasa depan, milik siapa?Perlukah kita mengetahui (baca: memprediksi) kerugian dimasadepan?Bagaimana memodelkan kerugian?“segmentation algorithm”?“Markov chain”?“account’s behavioural score”?







P =

0.85 0.09 0.01 0.00 0.01 0.01 0.030.05 0.76 0.12 0.04 0.01 0.00 0.020.03 0.08 0.70 0.15 0.03 0.00 0.010.01 0.04 0.03 0.70 0.12 0.00 0.000.00 0.02 0.07 0.03 0.88 0.00 0.000.00 0.00 0.00 0.00 0.00 1.00 0.000.00 0.00 0.00 0.00 0.00 0.00 1.00







DefinisiPeluang TransisiContoh/Latihan

Definisi

Proses stokastik {Xn} adalah Rantai Markov:

n = 0, 1, 2, . . .

nilai yang mungkin adalah hingga atau terhitung

P(Xn+1 = j |Xn = i ,Xn−1 = in−1, . . . ,X1 = i1,X0 = i0

)= Pij (∗)

distribusi bersyarat Xn+1, diberikan keadaan-keadaan lampau(past states) X0,X1, . . . ,Xn−1 dan keadaan sekarang (presentstate) Xn, hanya bergantung pada keadaan sekarang (“SifatMarkov”)

keadaan-keadaan (states): i0, i1, . . . , in−1, i , j








Pij peluang bahwa proses akan berada di keadaan j dari keadaan i ;

Pij ≥ 0, i , j ≥ 0;∞∑j=0

Pij = 1, i = 0, 1, . . .








Matriks peluang transisi Pij adalah

P =

P00 P01 P02 · · ·P10 P11 P12 · · ·

......

...Pi0 Pi0 Pi0 · · ·

......

...








Diagram transisi keadaan








Perhatikan (*):


)= P

(Xn+1 = j |Xn = i

)= Pij ,

yang disebut sebagai peluang transisi 1-langkah atau one-steptransition probability.








Peluang bersama

P(Xn = i ,Xn−1 = in−1, . . . ,X1 = i1,X0 = i0

)dapat dihitung dengan sifat peluang bersyarat berikut.

P(Xn = i ,Xn−1 = in−1, . . . ,X1 = i1,X0 = i0

)= P

(Xn−1 = in−1, . . . ,X1 = i1,X0 = i0

)× P

(Xn = i |Xn−1 = in−1, . . . ,X1 = i1,X0 = i0

)= P

(Xn−1 = in−1, . . . ,X1 = i1,X0 = i0

)× P

(Xn = i |Xn−1 = in−1

)= · · ·= pi0 · · · Pin−1,in








Contoh/Latihan

1. Jika, pada waktu t, Rez mengajukan klaim asuransi, makaRez akan mengajukan klaim pada waktu t + 1 dengan peluangα; jika Rez tidak mengajukan klaim asuransi saat ini maka dimasa depan Rez akan mengajukan klaim asuransi denganpeluang β. Matriks peluang transisinya adalah...








Solusi:

P =

(1− β β1− α α

)dengan keadaan-keadaan:’0’ tidak mengajukan klaim’1’ mengajukan klaim








2. Suatu rantai Markov dengan keadaan-keadaan “0, 1, 2”memiliki matriks peluang transisi:

P =

0.1 0.2 0.70.9 0.1 00.1 0.8 0.1

dan P(X0 = 0) = 0.3,P(X0 = 1) = 0.4,P(X0 = 2) = 0.3.Hitung

P(X0 = 0,X1 = 1,X2 = 2)








Solusi: 0








3. Keadaan hujan pada suatu hari bergantung pada keadaanhujan dalam dua hari terakhir. Jika dalam dua hari terakhirhujan maka besok akan hujan dengan peluang 0.7; Jika hariini hujan dan kemarin tidak hujan maka besok akan hujandengan peluang 0.5; jika hari ini tidak hujan dan kemarinhujan maka besok akan hujan dengan peluang 0.4; jika dalamdua hari terakhir tidak hujan maka besok hujan denganpeluang 0.2. Matriks peluang transisinya adalah...








Solusi:

P =

0.7 0 0.3 00.5 0 0.5 00 0.4 0 0.60 0.2 0 0.8

dengan keadaan-keadaan:’0’ (00) = hari ini dan kemarin hujan’1’ (10) = hari ini hujan, kemarin tidak hujan’2’ (01) = hari ini tidak hujan, kemarin hujan’3’ (11) = hari ini dan kemarin tidak hujan








4. Tiga item produk A dan tiga item produk B didistribusikandalam dua buah paket/kotak sedemikian hinga setiap paketterdiri atas tiga item produk. Dikatakan bahwa sistem beradadalam keadaan i , i = 0, 1, 2, 3 jika dalam paket pertamaterdapat i produk A. Setiap saat (langkah), kita pindahkansatu item produk dari setiap paket dan meletakkan itemproduk tersebut dari paket 1 ke paket 2 dan sebaliknya.Misalkan Xn menggambarkan keadaan dari sistem setelahlangkah ke-n. Matriks peluang transisinya adalah...








Solusi:

P =

0 1 0 0

1/9 4/9 4/9 00 4/9 4/9 1/90 0 1 0

dengan keadaan-keadaan:’0’ terdapat 0 produk A di paket pertama’1’ terdapat 1 produk A di paket pertama’2’ terdapat 2 produk A di paket pertama’3’ terdapat 3 produk A di paket pertama








5. Menurut Kemeny, Snell dan Thompson, Tanah Australiadiberkahi dengan banyak hal kecuali cuaca yang baik. Merekatidak pernah memiliki dua hari bercuaca baik secaraberturut-turut. Jika mereka mendapatkan hari bercuaca baikmaka esok hari akan bersalju atau hujan dengan peluangsama. Jika hari ini mereka mengalami salju atau hujan makabesok akan bercuaca sama dengan peluang separuhnya. Jikaterdapat perubahan cuaca dari salju atau hujan, hanyaseparuh dari waktu besok akan menjadi hari bercuaca baik.Tentukan matriks peluang transisi dari Rantai Markov yangdibentuk dari keadaan-keadaan diatas.








Solusi:

P =

1/2 1/4 1/41/2 0 1/21/4 1/4 1/2

dengan keadaan-keadaan:’0’ cuaca hujan’1’ cuaca baik’2’ cuaca salju








6. Suatu rantai Markov dengan keadaan-keadaan “0, 1, 2”memiliki matriks peluang transisi:

P =

0.7 0.2 0.10 0.6 0.4

0.5 0 0.5

Hitung

P(X2 = 1,X3 = 1 |X1 = 0)

danP(X1 = 1,X2 = 1 |X0 = 0)








Solusi: 0.12; 0.12








7. Sebagai calon atlet, setiap pagi Swari meninggalkan rumahnyauntuk berlari pagi. Swari akan pergi lewat pintu depan ataubelakang dengan peluang sama. Ketika meninggalkan rumah,Swari memakai sepatu olah raga atau bertelanjang kaki.Ketika pulang, Swari akan masuk lewat pintu depan ataubelakang dan meletakkan sepatunya dengan peluang sama.Diketahui bahwa Swari memiliki 4 pasang sepatu olah raga.Bentuklah suatu Rantai Markov dari proses diatas.








Solusi:

P =

3/4 1/4 0 0 01/4 1/2 1/4 0 0

0 1/4 1/2 1/4 00 0 1/4 1/2 1/40 0 0 1/4 3/4

dengan keadaan-keadaan:’0’ (4,0) = 4 sepatu didepan, 0 dibelakang’1’ (3,1) = 3 sepatu didepan, 1 dibelakang’2’ (2,2) = 2 sepatu didepan, 2 dibelakang’3’ (1,3) = 1 sepatu didepan, 3 dibelakang’4’ (0,4) = 0 sepatu didepan, 4 dibelakang







Persamaan Chapman-KolmogorovContoh/Latihan

Definisi

Misalkan Pnij menyatakan peluang transisi n-langkah suatu proses

di keadaan i akan berada di keadaan j ,

Pnij = P(Yk+n = j |Yk = i), n ≥ 0, i , j ≥ 0.

Persamaan Chapman-Kolmogorov adalah alat untuk menghitungpeluang transisi n + m-langkah:

Pn+mij =

∞∑k=0

PnikPm

kj , (Buktikan!)

untuk semua n,m ≥ 0 dan semua i , j . PnikPm

kj menyatakan peluangsuatu proses dalam keadaan i akan berada di keadaan j dalamn + m transisi, melalui keadaan k dalam n transisi/langkah.








Contoh/Latihan

1. Jika hari ini hujan maka besok akan hujan dengan peluangα = 0.7; jika hari ini tidak hujan maka besok akan hujandengan peluang β = 0.4. Matriks peluang transisi 4 langkahadalah...








Solusi:

P4 =

(0.5749 0.42510.5668 0.4332

)








2. Keadaan hujan pada suatu hari bergantung pada keadaanhujan dalam dua hari terakhir. Jika dalam dua hari terakhirhujan maka besok akan hujan dengan peluang 0.7; Jika hariini hujan dan kemarin tidak hujan maka besok akan hujandengan peluang 0.5; jika hari ini tidak hujan dan kemarinhujan maka besok akan hujan dengan peluang 0.4; jika dalamdua hari terakhir tidak hujan maka besok hujan denganpeluang 0.2. Matriks peluang transisinya adalah sbb:

P =

0.7 0 0.3 00.5 0 0.5 00 0.4 0 0.60 0.2 0 0.8

Jika hari Senin dan Selasa hujan, berapa peluang bahwa hariKamis akan hujan?Dosen: Khreshna I.A. Syuhada, MSc. PhD. MA4081 PENGANTAR PROSES STOKASTIK Bab 3 Rantai Markov







Solusi:

P2 =

0.49 0.12 0.21 0.180.35 0.2 0.15 0.30.2 0.12 0.2 0.40.1 0.16 0.1 0.64

Peluang hujan pada hari Kamis adalahP2

00 + P201 = 0.49 + 0.12 = 0.61








3. Tunjukkan bahwa matriks peluang transisi n-langkahmemenuhi sifat:

∞∑j=0

Pn+mij = 1, i = 0, 1, . . .








Solusi:








4. Laila adalah mahasiswa tingkat akhir di Farmasi UnPadj. Diatinggal tidak jauh dari kampus. Cukup berjalan kaki saja daritempat kos ke kampus dan sebaliknya. Akhir-akhir ini hujandatang hampir setiap hari. Mau tidak mau, Lailamenggunakan payung dalam perjalanan kos-kampus ataukampus-kos. Jika hari hujan dan payung ada ditempat Lailaberada maka Laila akan menggunakan payung tersebut. Jikahari tidak hujan, Laila selalu lupa untuk membawa payung.Misalkan θ adalah peluang hujan setiap kali Laila akanmenuju kampus atau kos. Jika Laila memiliki 3 buah payung,bentuklah suatu rantai Markov dari proses diatas! Berapapeluang Laila akan basah pada suatu hari? (Kerjakan dahulumatriks peluang transisi n-langkah)








Solusi:

P =

0 0 0 10 0 1− θ θ0 1− θ θ 0

1− θ θ 0 0

dengan keadaan-keadaan:’0’, ’1’, ’2’, ’3’ yang menyatakan jumlah payung








5. Seorang tenaga penjual atau sales (SPG? SPB?) berjuanguntuk menjual suatu produk sebanyak i = 0, 1, 2 buah. Prosesjumlah produk yang terjual {Xn} membentuk rantai Markovdengan m.p.t:

P =

0 1/2 1/21/2 0 1/21/2 1/2 0

Hitung P(Xn = 0|X0 = 0) untuk n = 0, 1, 2.Hitung P(X3 = 1|X1 = 0).








Solusi:P(Xn = 0|X0 = 0) = P(X0 = 0)

P(X1 = 0|X0 = 0) = 0

P(X2 = 0|X0 = 0) = 1/2

P(X3 = 1|X0 = 0) = 1/4







DefinisiContoh/Latihan

Definisi

Misalkanαi = P(X0 = i), i ≥ 0,

dimana∑∞

i=0 αi = 1. Peluang tak bersyarat dapat dihitungdengan mensyaratkan pada keadaan awal,

P(Xn = j) =∞∑i=0

P(Xn = j |X0 = i) P(X0 = i) =∞∑i=0

Pnij αi








1. Pandang soal yang lalu dengan matriks peluang transisi:

P =

(0.7 0.30.4 0.6

)Jika diketahui α0 = P(X0 = 0) = 0.4 danα1 = P(X0 = 1) = 0.6, maka peluang (tak bersyarat) bahwahari akan hujan 4 hari lagi adalah...








Solusi:

P(X4 = 0) = 0.4 P400 + 0.6 P4

10

= (0.4)(0.5749) + (0.6)(0.5668) = 0.57








2. Seorang pensiunan H menerima 2 (juta rupiah) setiap awalbulan. Banyaknya uang yang diperlukan H untuk dibelanjakanselama sebulan saling bebas dengan banyaknya uang yang diapunya dan sama dengan i dengan peluangPi , i = 1, 2, 3, 4,

∑4i=1 Pi = 1. Jika H memiliki uang lebih dari

3 di akhir bulan, dia akan memberikan sejumlah uang lebihdari 3 itu kepada orang lain. Jika setelah dia menerima uangdiawal bulan H memiliki uang 5, berapa peluang uangnyaakan 1 atau kurang setiap saat selama 4 bulan berikut?








Solusi :Keadaan-keadaannya adalah‘1’ jumlah uang sebanyak 1 yang H punya di akhir bulan‘2’ jumlah uang sebanyak 2 yang H punya di akhir bulan‘3’ jumlah uang sebanyak 3 yang H punya di akhir bulanMatriks peluang transisi

P =

P2 + P3 + P4 P1 0P3 + P4 P2 P1

P4 P3 P1 + P2








Misalkan Pi = 1/4, i = 1, 2, 3, 4. Maka matriks peluang transisinyaadalah

P =

3/4 1/4 01/2 1/4 1/41/4 1/4 1/2

Peluang uangnya akan 1 atau kurang setiap saat selama 4 bulanberikut adalah P4

31 = 201/256.







Latihan

1. Pandang suatu proses {Xn, n = 0, 1, . . .} yang bernilai 0, 1, 2.Misalkan


)=

{P Iij , n genap,

P IIij , n ganjil,

dimana∑2

j=0 P Iij =

∑2j=0 P II

ij = 1, i = 0, 1, 2. Apakah{Xn, n ≥ 0} suatu rantai Markov?







Solusi: Bukan.







2. Pandang 3 paket/kotak barang berwarna MERAH, PUTIH,BIRU. Paket barang MERAH memuat 1 kaos merah dan 4kaos biru; paket PUTIH memuat 3 kaos putih, 2 kaos merahdan 2 kaos biru; paket BIRU memuat 4 kaos putih, 3 kaosmerah dan 3 kaos biru. Pada tahap awal, sebuah kaos diambilsecara acak dari paket MERAH dan dikembalikan (lagi) kepaket tersebut. Pada setiap tahap berikutnya, sebuah kaosdiambil secara acak dari paket yang berwarna sama dengankaos yang terambil sebelumnya dan dikembalikan ke pakettersebut. Bentuklah matriks peluang transisi yang mungkin.







Solusi:

P =

1/5 0 4/52/7 3/7 2/7

3/10 4/10 3/10

dengan keadaan-keadaan:’0’ Merah’1’ Putih’2’ Biru







3. Percobaan-percobaan dilakukan secara berurutan. Jika dalamdua percobaan terakhir SUKSES maka peluang GAGAL padapercobaan berikut adalah 0.8. Dalam keadaan YANG LAIN,peluang GAGAL adalah 0.4. Bentuklah matriks peluangtransisi dan tentukan kelas-kelas keadaan. Bentuk suaturantai Markov.







Solusi:

P =

0.2 0.8 0 00 0 0.6 0.4

0.6 0.4 0 00 0 0.6 0.4

dengan keadaan-keadaan:’0’ (SS) = hari ini dan kemarin SUKSES’1’ (SG) = hari ini GAGAL, kemarin SUKSES’2’ (GS) = hari ini SUKSES, kemarin GAGAL’3’ (GG) = hari ini dan kemarin GAGAL







4. Dalam Perang Teluk, ada tiga buah tank yang bertahan: A, Bdan C. Tank A dapat menembak sasaran dengan peluang 1/3,tank B dengan peluang 1/4 dan tank C dengan peluang 1/5.Dalam sebuah baku tembak, tank-tank akan terus menerusmenembak secara bersamaan hingga hanya ada satu tankyang bertahan atau tidak ada tank yang bertahan sama sekali.Asumsikan bahwa sebuah tank secara acak memilih sebuahtank lain yang masih bertahan sebagai target. Tentukanmatriks peluang transisi dari rantai Markov diatas.







Solusi:P =

1 0 0 0 0 0 0 00 1 0 0 0 0 0 00 0 1 0 0 0 0 00 0 0 1 0 0 0 0

1/12 1/4 1/6 0 1/2 0 0 01/15 4/15 0 2/15 0 8/15 0 01/20 0 1/5 3/20 0 0 3/5 0

1/240 1/24 1/24 1/24 11/60 1/8 39/240 24/60

dengan keadaan-keadaan:‘0’, ‘A’, ‘B’, ‘C’, ‘AB’, ‘AC’, ‘BC’, ‘ABC’







5. Sebuah rantai Markov {Yt , t ≥ 0} dengan keadaan-keadaan0,1,2 memiliki matriks peluang transisi:

P =

1/2 1/3 1/60 1/3 2/3

1/2 0 1/2

Jika P(Y0 = 0) = P(Y0 = 1) = 1/4, hitung E (Y2).







Solusi:

P2 =

4/12 5/18 14/361/3 1/9 5/91/2 1/6 4/12







E (Y2)

= 0 P(Y2 = 0) + 1 P(Y2 = 1) + 2 P(Y2 = 2)

= 0 +(

P(Y2 = 1|Y0 = 0) P(Y0 = 0) + P(Y2 = 1|Y0 = 1) P(Y0 = 1)

+ P(Y2 = 1|Y0 = 2) P(Y0 = 2))

+ 2(

P(Y2 = 2|Y0 = 0) P(Y0 = 0)

+ P(Y2 = 2|Y0 = 1) P(Y0 = 1) + P(Y2 = 2|Y0 = 2) P(Y0 = 2))

= P201 0.25 + P2

11 0.25 + P221 0.5 + 2

(P2

02 0.25 + P212 0.25 + P2

22 0.5)

= 71/72







6. Dua tim futsal wanita di MA-ITB akan memainkan tujuhrangkaian pertandingan. Hasil setiap pertandingan salingbebas. Setiap pertandingan akan dimenangkan oleh tim Adengan peluang α dan oleh tim B dengan peluang 1− α.Misalkan keadaan suatu sistem direpresentasikan olehpasangan (a, b) dimana a menyatakan banyak pertandinganyang dimenangkan A dan b banyak pertandingan yangdimenangkan B. Bentuklah rantai Markov untuk masalahtersebut.







Catatan: a + b ≤ 7 dan rangkaian pertandingan akan berakhirapabila a = 4 atau b = 4.







Solusi:

α

α α α

1-α 1- α 1- α 1- α

4,1 4,2 4,3 4,0

1- α 1- α 1- α 1- α

1- α

1- α

1- α

1- α

1- α 1- α

1- α 1- α

0,1 0,2 0,4 0,3 0,00 0

α α α α

1,1 1,2 1,4 1,3 1,0

α α α α

2,1 2,2 2,4 2,3 2,0

α α α α

3,1 3,2 3,4 3,3 3,0







ContohKode MATLAB

Contoh

Model penyebaran suatu penyakit adalah sbb: Jumlah populasiadalah N = 5, sebagian sakit dan sisanya sehat. Dalam setiapwaktu, 2 orang akan dipilih secara acak dari populasi tersebut dankeduanya berinteraksi. Pemilihan orang-orang tersebut dilakukansdh interaksi antara setiap pasangan adalah sama. Jika satu orangdari suatu pasangan sakit, yang lain sehat, maka penyakit akandisebarkan ke orang yang sehat dengan peluang 0.1. Diluar kondisitersebut, tidak ada penyakit yang disebarkan. Misalkan Xn

menyatakan jumlah orang yang sakit dalam populasi diakhirperiode ke-n. Bentuklah suatu matriks peluang transisi yangmungkin.







ContohKode MATLAB

Solusi:Keadaan: 0, 1, 2, 3, 4, 5, yang menyatakan jumlah orang yangsakit.P00 = 1,P55 = 1. Cukup jelas. Jika tidak ada/semua orang sakitmaka PASTI keadaan berubah ke tidak ada/semua orang sakit.

Pi ,i+1 = 0.1C i

1 C 5−i1

C 52

= 0.01(i)(5− i),

Pii = 1− 0.01(i)(5− i),

untuk i = 1, 2, 3, 4.







ContohKode MATLAB

P =

1 0 0 0 0 00 0.96 0.04 0 0 00 0 0.94 0.06 0 00 0 0 0.94 0.06 00 0 0 0 0.96 0.040 0 0 0 0 1







ContohKode MATLAB

Kode:

function transprob;

% the function calculate transition probability

% for a Markov chain

%

% created by K Syuhada, 12/03/2011

clear

clc

m = input(’m = ’); % number of states







ContohKode MATLAB

P = zeros(m,m);

for i = 1:m

for j = 1:m

if i == j

P(i,j) = 1 - 0.01*(i-1)*(5-(i-1));

elseif i+1 == j

P(i,j) = 0.01*(i-1)*(5-(i-1));

else

P(i,j) = 0;

end

end

end







ContohKode MATLAB

display(’matriks peluang transisi:’)

display(P)

% n-step probability

% Chapman-Kolmogorov Equation

n = input(’n = ’); % number of steps

Pn = P^n;

display(’matriks peluang transisi n-langkah:’)

display(Pn)







ContohKode MATLAB

---------------------------------------------------------------

m = 6

matriks peluang transisi:

P =

1.0000 0 0 0 0 0

0 0.9600 0.0400 0 0 0

0 0 0.9400 0.0600 0 0

0 0 0 0.9400 0.0600 0

0 0 0 0 0.9600 0.0400

0 0 0 0 0 1.0000







ContohKode MATLAB

n = 2

matriks peluang transisi n-langkah:

Pn =

1.0000 0 0 0 0 0

0 0.9216 0.0760 0.0024 0 0

0 0 0.8836 0.1128 0.0036 0

0 0 0 0.8836 0.1140 0.0024

0 0 0 0 0.9216 0.0784

0 0 0 0 0 1.0000







Keadaan Dapat Diakses dan BerkomunikasiContoh/LatihanLatihanKeadaan Recurrent dan TransientContoh/Latihan

Sifat Dapat Diakses dan Berkomunikasi

Keadaan j dikatakan dapat diakses (accessible) dari keadaan i jikaPnij > 0 untuk suatu n ≥ 0. Akibatnya, keadaan j dapat diakses

dari keadaan i jika dan hanya jika dimulai dari keadaan i prosesakan masuk ke keadaan j . Jika keadaan j tidak dapat diakses darikeadaan i maka peluang masuk ke keadaan j dari keadaan i adalahnol.Catatan:Dua keadaan i dan j yang saling akses satu sama lain dikatakanberkomunikasi (communicate). Notasi: i ↔ j .








1 Keadaan i berkomunikasi dengan keadaan i untuk semuai ≥ 0

2 Jika keadaan i berkomunikasi dengan keadaan j makakeadaan j berkomunikasi dengan keadaan i

3 Jika keadaan i berkomunikasi dengan keadaan j dan keadaanj berkomunikasi dengan keadaan k maka keadaan iberkomunikasi dengan keadaan k








Dua keadaan yang berkomunikasi dikatakan berada dalam kelas(class) yang sama. Setiap dua kelas dari keadaan-keadaan dapat‘identik’ (identical) atau ‘saling asing’ (disjoint). Rantai Markovdikatakan tidak dapat direduksi (irreducible) jika hanya terdapatsebuah kelas dan semua keadaan berkomunikasi satu sama lain.








Contoh/Latihan

1. Tentukan kelas keadaan dari rantai Markov dengan peluangtransisi berikut:(i)

P =

0.7 0 0.3 00.5 0 0.5 00 0.4 0 0.60 0.2 0 0.8








(ii)

P =

0 1 0 0

1/9 4/9 4/9 00 4/9 4/9 1/90 0 1 0








(iii)

P =

1 0 01/2 1/4 1/41/4 1/4 1/2








2. Diketahui matrik peluang transisi:

P =

0.5 0.5 00.5 0.25 0.250 0.33 0.67

Apakah rantai Markov dengan peluang transisi diatas tidakdapat direduksi (irreducible)?








3. Apakah yang dapat anda katakan tentang rantai Markovdengan matriks peluang transisi berikut:

P =

0.5 0.5 0 00.5 0.5 0 0

0.25 0.25 0.25 0.250 0 0 1

?








Empat gadis bermain bola: Tris, Sri, Berlian dan Yani. Jika Trismemegang bola, dia akan melemparkan bola tersebut ke Sri danYani dengan peluang sama. Jika Sri memegang bola, dia akanmelemparkannya ke Tris dengan peluang 1/3 dan melemparkan keYani dengan peluang 2/3. Jika Berlian memegang bola, dia akanmelemparkan bola ke Sri. Buatlah matriks peluang transisi untukkasus:(i) Jika Yani memegang bola, dia akan melemparkannya ke Trisdengan peluang 2/3 atau membawa lari bola tersebut denganpeluang 1/3(ii) Jika Yani memegang bola pertama kali, dia akan melemparkanke Tris; Jika Yani memegang bola yang kedua kali, dia akan larimembawa bola tersebut.








Solusi:

P =

0 0.5 0 0.5

1/3 0 0 2/30 1 0 0

2/3 0 0 1/3

dengan keadaan ’0’ Tris; ’1’ Sri; ’2’ Berlian; ’3’ Yani.








Keadaan Recurrent dan Transient

Untuk setiap keadaan i , misalkan fi peluang bahwa dimulai darikeadaan i proses akan pernah kembali ke keadaan i . Keadaan idikatakan recurrent jika fi = 1. Dikatakan transient jika fi < 1.

Jika keadaan i recurrent maka proses akan terus kembali kekeadaan i dengan peluang satu. Dengan definisi rantaiMarkov, proses akan dimulai lagi ketika kembali ke keadaan i ,dan seterusnya, sehingga keadaan i akan dikunjungi lagi. Jikakeadaan i recurrent maka dimulai dari keadaan i maka prosesakan kembali ke keadaan i terus dan terus sebanyak takhingga kali.








Misalkan keadaan i transient. Setiap kali proses kembali kekeadaan i , terdapat kemungkinan (peluang yang positif)sebesar 1− fi bahwa proses tidak pernah kembali ke keadaani . Dengan demikian, dimulai dari keadaan i , peluang bahwaproses berada di i sebanyak tepat n periode/kali adalahf n−1i (1− fi ), n ≥ 1. Jika keadaan i transient maka, dimulai

dari keadaan i , banyak periode/kali bahwa proses akan beradadi keadaan i adalah peubah acak geometrik dengan parameter1− fi .








“Keadaan i recurrent jika dan hanya jika, dimulai dari keadaan i ,maka banyak periode/kali yang diharapkan (expected number oftime periods) bahwa proses akan berada di keadaan i adalah takhingga”








Misalkan

In =

{1, Yn = i ;0, Yn 6= i .

Misalkan∑∞

n=0 In menyatkan banyak periode/kali bahwa prosesberada dalam keadaan i , dan

E

( ∞∑n=0

In |Y0 = i

)=∞∑n=0

E (In|Y0 = i)

=∞∑n=0

P(Yn = i |Y0 = i)

=∞∑n=0

Pnii








Proposisi

Keadaan i adalah

recurrent jika∞∑n=0

Pnii =∞

transient jika∞∑n=0

Pnii <∞








Catatan:

Pada rantai Markov dengan keadaan hingga, tidak semuakeadaan bersifat transient (Mengapa?)

“Jika keadaan i recurrent dan keadaan i berkomunikasi(communicate) dengan keadaan j maka keadaan j recurrent”(Bagaimana jika keadaan i transient?)

Semua keadaan pada rantai Markov (hingga) yang tidakdapat direduksi adalah recurrent (PENTING!)








Contoh/Latihan

1. Misalkan rantai Markov dengan keadaan 0,1,2,3 memilikimatriks peluang transisi:

P =

0 0 0.5 0.51 0 0 00 1 0 00 1 0 0

Tentukan keadaan mana yang recurrent dan keadaan manayang transient!








Solusi:Semua keadaan recurrent.








2. Bagaimana dengan rantai Markov (keadaan: 0,1,2,3,4)dengan matriks peluang transisi:

P =

0.5 0.5 0 0 00.5 0.5 0 0 00 0 0.5 0.5 00 0 0.5 0.5 0

0.25 0.25 0 0 0.5

?








Solusi:Keadaan 0,1,2,3 recurrent, keadaan 4 transient.








3. Misalkan rantai Markov dengan keadaan 0,1,2,3 memilikimatriks peluang transisi:

P =

0.5 0.5 0 00.5 0.5 0 0

0.25 0.25 0.25 0.250 0 0 1

Tentukan keadaan mana yang recurrent dan keadaan manayang transient!








Solusi:Keadaan 0,1,3 recurrent, keadaan 2 transient.








4. Model penyebaran penyakit memiliki matriks peluang transisi(keadaan: 0,1,2,3,4,5) sebagai berikut:

P =

1 0 0 0 0 00 0.96 0.04 0 0 00 0 0.94 0.06 0 00 0 0 0.94 0.06 00 0 0 0 0.96 0.040 0 0 0 0 1

Tentukan sifat keadaan dari rantai Markov diatas.








Solusi:Keadaan 0,5 recurrent, keadaan 1,2,3,4 transient.







IlustrasiDefinisiContoh/Latihan

Ilustrasi

Dalam suatu kesempatan, sejumlah pemain bola berdoa bersama.David Beckham bertanya pada Tuhan:“Kapan Inggris menjadijuara Piala Dunia?”








Tuhan menjawab: “Tahun 2014”.Beckham pun menangis.








Giliran Christiano Ronaldo, kapten timnas Portugal, bertanya:“Tuhan, kapan Portugal merebut Piala Dunia?”








Tuhan pun langsung menjawab “Tahun 2022”.Dan Ronaldo pun menangis.








Park-Ji Sung tidak mau ketinggalan. Dia bertanya “kapan Koreamenjadi juara, Tuhan?”








Tuhan menjawab “ya... 20 tahun lagi”.Park-Ji Sung menangis.








Akhirnya Bambang Pamungkas pun tak tahan untuk bertanya:“Kapan Indonesia bisa menjadi juara Piala Dunia, ya Tuhan?”








Tuhan pun menangis dan berseru “kalau mimpi kira-kira dong”.








Misalkan ‘0’ keadaan belum pernah juara dan ‘1’ keadaan pernahjuara. Matriks peluang transisi yang dapat dibentuk adalah

P =

(0.9 0.10.3 0.7

)








Matriks peluang transisi 8 dan 12 langkahnya:

P8 =

(0.7542 0.24580.7374 0.2626

)dan

P12 =

(0.7505 0.24950.7484 0.2516

)...dst.








Matriks P12 hampir identik dengan P8 (benar-benar identikdengan P16). Selain itu, setiap baris dari P12 memiliki unsur yangidentik. Nampaknya, Pn

ij konvergen ke suatu nilai, untuk n→∞,yang sama untuk semua i . Dengan kata lain, terdapat limitpeluang (limiting probability) bahwa proses akan berada dikeadaan j setelah sekian/banyak langkah/transisi. Nilai limit inisaling bebas dengan nilai pada keadaan awal.








Definisi

Perhatikan 2 sifat keadaan berikut:Keadaan i dikatakan memiliki periode d jika Pn

ii = 0 untuk n yangtidak dapat dibagi oleh d (d suatu integer). Contoh, suatu prosesdimulai dari keadaan i akan kembali ke i pada waktu 2, 4, 6, 8, . . . ,maka keadaan i memiliki periode 2. Suatu keadaan yang memilikiperiode 1 disebut aperiodik. Jika keadaan i memiliki periode d dankeadaan i berkomunikasi dengan keadaan j maka keadaan j jugamemiliki periode d .








Jika keadaan i recurrent, maka keadaan tersebut akan dikatakanpositive recurrent jika, dimulai dari keadaan i , waktu harapanhingga proses kembali ke i adalah hingga. Pada rantai Markovyang memiliki keadaan hingga, semua keadaan yang recurrentadalah positive recurrent. Suatu keadaan yang positive recurrentdan aperiodik disebut ergodik.








Teorema

Untuk rantai Markov yang ergodik dan tidak dapat direduksi,

limn→∞

Pnij

ada dan saling bebas dari i . Misalkan

πj = limn→∞

Pnij , j ≥ 0,

maka πj adalah solusi nonnegatif tunggal dari

πj =∞∑i=0

πi Pnij , j ≥ 0,

dengan∑∞

j=0 πj = 1.








Catatan:

Perhatikan bahwa

P(Xn+1 = j) =∞∑i=0

P(Xn+1 = j |Xn = i) P(Xn = i)

=∞∑i=0

Pij P(Xn = i)

Limit peluang πj adalah peluang jangka panjang (long-runproportion of time) bahwa suatu proses akan berada dikeadaan j








Jika rantai Markov tidak dapat direduksi, maka terdapatsolusi untuk

πj =∑i

πi Pij , j ≥ 0,

dengan∑

j πj = 1, JIKA dan HANYA JIKA rantai Markovbersifat positive recurrent. Jika solusinya ada maka solusitersebut tunggal dan πj adalah proporsi jangka panjang bahwarantai Markov berada dalam keadaan j . Jika rantai Markovaperiodik maka πj adalah limit peluang bahwa rantai akanberada di keadaan j .








Contoh/Latihan

1. Jika hari ini hujan maka besok akan hujan dengan peluang α;jika hari ini tidak hujan maka besok akan hujan denganpeluang β. Jika ′0′ adalah keadaan hujan dan ′1′ adalahkeadaan tidak hujan maka peluang hujan dan tidak hujanuntuk jangka panjang adalah








Solusi:

P =

(α 1− αβ 1− β

),

dan kita punyai persamaan-persamaan:

π0 = απ0 + β π1

π1 = (1− α)π0 + (1− β)π1

π0 + π1 = 1








Kita peroleh peluang hujan dan tidak hujan pada jangka panjang:

π0 =β

1 + β − α

dan

π1 =1− α

1 + β − α








2. Percobaan-percobaan dilakukan secara berurutan. Jika dalamdua percobaan terakhir SUKSES maka peluang SUKSES padapercobaan berikut adalah 0.8. Dalam keadaan YANG LAIN,peluang SUKSES adalah 0.5. Hitung peluang percobaansukses untuk jangka panjang.








Solusi:

P =

0.8 0.2 0 00 0 0.5 0.5

0.5 0.5 0 00 0 0.5 0.5

dengan keadaan-keadaan:’0’ (SS) = hari ini dan kemarin SUKSES’1’ (SG) = hari ini GAGAL, kemarin SUKSES’2’ (GS) = hari ini SUKSES, kemarin GAGAL’3’ (GG) = hari ini dan kemarin GAGAL








Kita punyai persamaan-persamaan:

π0 =

π1 =

π2 =

π3 =

danπ0 + π1 + π2 + π3 = 1








Diperoleh: π0 = 23/50;π1 = π2 = π3 = 9/504.Jadi, peluang SUKSES jangka panjang adalah

π0 + π1 = 32/50








3. Pandang pelantunan-pelantunan sebuah koin (dengan peluangmuncul MUKA adalah θ) yang saling bebas. Berapa banyaklantunan dibutuhkan yang diharapkan (expected number oftosses needed) agar pola HTHT muncul? (Perhatikan catatandibawah)








Catatan:

Peluang jangka panjang πj , j ≥ 0, disebut juga peluangstasioner (stationary probability). Jika keadaan awal dipilihberdasarkan peluang πj , j ≥ 0, maka peluang akan menjadikeadaan j pada setiap waktu n adalah sama dengan πj .

Untuk keadaan j , definisikan mjj yaitu banyak transisi yangdiharapkan (expected number of transitions) hingga suaturantai Markov, dimulai dari keadaan j akan kembali kekeadaan tersebut:

πj =1

mjj







1. Seorang dosen KS terus menerus memberikan ujian kepadamahasiswanya. Dosen KS memberikan 3 tipe/jenis ujiandengan hasil BAGUS atau JELEK. Misalkan θi adalah peluangbahwa mahasiswa mengerjakan BAGUS untuk ujian tipe i .Diketahui θ1 = 0.3, θ2 = 0.6, θ3 = 0.9. Jika mahasiswamengerjakan dengan BAGUS pada suatu ujian maka tipe ujianberikut yang akan dikerjakan memiliki peluang sama. Jikahasil ujian JELEK maka ujian berikut adalah ujian tipe 1.Bentuklah rantai Markov untuk cerita diatas.







Solusi:

P =

0.8 0.1 0.10.6 0.2 0.20.4 0.3 0.3

dengan keadaan ’1’ Ujian 1; ’2’ Ujian 2; ’3’ Ujian 3.







2. Misalkan koin 1 memiliki peluang muncul MUKA 0.7 ketikadilantunkan sedangkan peluang muncul MUKA untuk koin 2adalah 0.6. Jika sebarang koin dilantunkan hari ini danmuncul MUKA maka besok dilantunkan koin 1. Jika munculBELAKANG maka besok akan dilantunkan koin 2. Jikapeluang koin 1 terpilih untuk dilantukan pertama kali adalah0.5, tentukan peluang bahwa pada hari ketiga akandilantunkan koin 1.







Suppose that coin 1 has probability of coming up heads and coin 2has probability 0.6 of coming up heads. If the coin flipped todaycomes up heads, then we select coin 1 to flip tomorrow. If it comesup tails then we select coin 2 to flip tomorrow. If the coin initiallyflipped is equally likely to be coin 1 or coin 2, then what is theprobability that the coin flipped on the third day after the initialflip is coin 1?







Solusi:

P =

(0.7 0.30.6 0.4

)dengan keadaan ’1’ Koin 1; ’2’ Koin 2. Diketahui

P(X0 = 1) = P(X0 = 2) = 0.5,

sehingga

P(X3 = 1) = P311 P(X0 = 1) + P3

21 P(X0 = 2) = 2/3







3. Bentuklah suatu matriks peluang transisi dari rantai Markovyang memenuhi semua aturan berikut: memiliki tiga keadaanatau lebih, tidak ada satu pun keadaan yang absorbing, tidakdapat direduksi, memiliki periode dua, setidaknya satukeadaan bersifat transient, dan satu unsur dari matriksbernilai nol.







Solusi:Tidak ada matriks peluang transisi yang memenuhi semua aturan.







4. Setiap minggu pagi Vivian meninggalkan rumahnya untukberlari pagi. Vivian akan pergi lewat pintu depan denganpeluang dua kali lebih besar daripada pergi lewat pintubelakang. Ketika meninggalkan rumah Vivian memakai sepatuolah raga atau bertelanjang kaki jika sepatu tidak tersedia didepan pintu yang dia lewati. Ketika pulang, Vivian akanmasuk lewat pintu depan atau belakang, dan meletakkansepatunya, dengan peluang sama. Jika dia memiliki 2 pasangsepatu olah raga, berapa peluang Vivian akan sering berolahraga dengan memakai sepatu?







Solusi:

P =

2/3 1/3 01/6 3/6 2/6

0 1/6 5/6

dengan keadaan ’0’=(2,0); ’1’=(1,1); ’2’=(0,2). Diperoleh

π0 =;π1 =;π2 =

Jadi, peluang Vivian akan sering berolahraga dengan memakaisepatu adalah

(2/3)π0 + π1 + (1/3)π2 =







5. Seorang sopir taksi melayani penumpang yang bepergian di 2area dalam suatu kota. Penumpang taksi yang naik di area Aakan turun di area A juga dengan peluang 0.6. Penumpangyang naik di area B akan turun di area A dengan peluang 0.3.Keuntungan yang diharapkan (expected profit) sopir taksiuntuk pelayanan selama di area A adalah 6 dan selama di areaB adalah 8. Keuntungan yang diharapkan apabila pelayanantaksi melintasi 2 area adalah 12. Hitung keuntungan rata-ratasopir taksi untuk suatu pelayanan.







Solusi:

P =

(0.6 0.40.3 0.7

)dengan keadaan ’0’ Area A; ’1’ Area B. Diperoleh

π0 = 3/7, π1 = 4/7.

Misalkan X keuntungan dalam suatu pelayanan

E (X ) = E (X |A)π0 + E (X |B)π1

= [(0.6)(6) + (0.4)(12)](3/7) + [(0.3)(12) + (0.7)(8)](4/7)

= 62/7







6. Misalkan P suatu matriks peluang transisi. Tunjukkan bahwa∑j

Pnij = 1







7. Misalkan matriks peluang transisi untuk keadaan 0,1,2:

P =

1 0 0a b c0 0 1

dengan syarat a > 0, b > 0, c > 0. Keadaan 0 dan 2 adalahkeadaan yang absorbing.







Pandang proses yang dimulai dari keadaan 1, maka

1→ 1→ 0

atau1→ 1→ 2

Pertanyaan: Berapa lama proses akan berada di keadaan 1sebelum akhirnya ke keadaan 0 atau 2?







Dengan kata lain, misalkan

T = min{n : Xn = 0 atau Xn = 2}

maka hitungE (T |X0 = 1)


ma4081 pengantar proses stokastik bab 3 rantai markov · ilustrasi rantai markov peluang n-langkah...

Documents