ma4181 pengantar proses stokastik bab 3 rantai markov · ketika meninggalkan rumah, ying memakai...

PengantarSilabus dan Tujuan Perkuliahan

IlustrasiRantai Markov

Peluang n-langkahPeluang Transisi Tak Bersyarat

LatihanJenis Keadaan

Limit Peluang TransisiLATIHAN

“Waktu” dalam M.p.t

MA4181 PENGANTAR PROSES STOKASTIKBab 3 Rantai Markov

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

“SMART AND STOCHASTIC”

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







Pengantar

Tentang peubah acak:

Satu peubah acak X dan kaitannya dengan kejadian A

Dua peubah acak X dan Y yang tidak saling bebas serta“konsekuensinya” (baca: peluang bersyarat dan ekspektasibersyarat)








Misalkan X dan Y peubah acak kontinu dengan fungsi peluangbersama

f (x, y) = e−x(y+1), 0 ≤ x, 0 ≤ y ≤ e− 1

Tentukan P(X > 1|Y = 12) dan E(X|Y = 1

2)








Tunjukkan bahwa

Cov(X,E(Y|X)) = Cov(X,Y)








Mencari uang lewat ketangkasan permainan sering dilakukan. Inimasuk kategori berjudi juga sih. Mau bagaimana lagi? Terlepas dariitu, bermain peluang menjadi alasan Birgitta. Dia dan Bona bermainserangkaian permainan. Peluang Birgitta menang di setiap permainanadalah θ. Pemenang rangkaian permainan tersebut adalah dia yangmemenangkan dua atau lebih permainan. Berapa peluang bahwaBirgitta adalah pemenang? Berapa banyak permainan yangdilakukan?








Pandang peubah acak-peubah acak X0,X1,X2; setiap peubah acakmemiliki nilai {0, 1, 2}. Diketahui:

P(X0 = 0) = 0.3,P(X0 = 1) = 0.4,P(X0 = 2) = 0.3








P(X2 = 0|X1 = 0) = 0.1

P(X2 = 0|X1 = 1) = 0.9

P(X2 = 0|X1 = 2) = 0.1

P(X2 = 1|X1 = 0) = 0.2

P(X2 = 1|X1 = 1) = 0.1

P(X2 = 1|X1 = 2) = 0.8

P(X2 = 2|X1 = 0) = 0.7

P(X2 = 2|X1 = 1) = 0

P(X2 = 2|X1 = 2) = 0.1








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








Setiap minggu pagi Ying meninggalkan rumahnya untuk berlari pagi.Ying akan pergi lewat pintu depan atau belakang dengan peluangsama. Ketika meninggalkan rumah, Ying memakai sepatu olah ragaatau bertelanjang kaki jika sepatu tidak tersedia di depan pintu yangdia lewati. Ketika pulang, Ying akan masuk lewat pintu depan ataubelakang dan meletakkan sepatunya dengan peluang sama. Diketahuibahwa Ying memiliki 2 pasang sepatu olah raga. Berapa peluangbahwa Ying akan sering berolah raga dengan bertelanjang kaki?








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 Markov2 Menghitung peluang transisi n-langkah3 Menerapkan persamaan Chapman-Kolmogorov4 Menentukan keadaan yang dapat diakses dan berkomunikasi5 Menentukan keadaan-keadaan recurrent dan transient6 Menghitung peluang transisi untuk jangka panjang








Ilustrasi 1

Perilaku bunuh diri kini kian menjadi-jadi. Hesti (nama sebenarnya)adalah sebuah contoh. Dia pernah melakukan percobaan bunuh diri,namun gagal. Menurut pakar, kalau pada suatu waktu seseorangmelakukan percobaan bunuh diri maka besar kemungkinan dia akanmelakukannya lagi di masa mendatang. Jika seseorang belum pernahmelakukan percobaan bunuh diri, di masa mendatang orang tersebutakan mungkin melakukan percobaan bunuh diri. Deskripsikanfenomena diatas sebagai model peluang (probability model).








Ilustrasi 2

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 peluang terjadinyahal ini? Apakah model ini membantu dalam strategi pemasaran suatubarang?








Ilustrasi 3

Akhir-akhir ini, hujan dan panas (baca: tidak hujan) datang silihberganti tanpa bisa diduga. Kalau hari ini hujan, besok mungkin hujanmungkin juga panas. Tentu saja peluang besok hujan akan lebih besardibanding peluang besok akan panas. Begitu pula jika hari ini panas.Besok akan lebih mungkin panas dibandingkan hujan. Jika hari Seninhujan, berapa peluang bahwa hari Selasa akan hujan? Berapa peluangbahwa hari Kamis akan hujan?








DefinisiPeluang TransisiLatihan

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 · · ·...

......









P02

...

P20

0

1 2 P00

P01 P12

P10 P21

P11 P22









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









Latihan

1. Jika, pada waktu t, Rez mengajukan klaim asuransi, maka Rezakan mengajukan klaim pada waktu t + 1 dengan peluang α; jikaRez tidak mengajukan klaim asuransi saat ini maka di masadepan Rez akan mengajukan klaim asuransi dengan peluang β.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” memilikimatriks 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 keadaan hujandalam dua hari terakhir. Jika dalam dua hari terakhir hujan makabesok akan hujan dengan peluang 0.7; Jika hari ini hujan dankemarin tidak hujan maka besok akan hujan dengan peluang 0.5;jika hari ini tidak hujan dan kemarin hujan maka besok akanhujan dengan peluang 0.4; jika dalam dua hari terakhir tidakhujan maka besok hujan dengan peluang 0.2. Matriks peluangtransisinya 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 pertama terdapati produk A. Setiap saat (langkah), kita pindahkan satu itemproduk dari setiap paket dan meletakkan item produk tersebutdari paket 1 ke paket 2 dan sebaliknya. Misalkan Xn

menggambarkan keadaan dari sistem setelah langkah 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 peluang sama.Jika hari ini mereka mengalami salju atau hujan maka besokakan bercuaca sama dengan peluang separuhnya. Jika terdapatperubahan cuaca dari salju atau hujan, hanya separuh dari waktubesok akan menjadi hari bercuaca baik. Tentukan matrikspeluang transisi dari Rantai Markov yang dibentuk darikeadaan-keadaan diatas.









6. Suatu rantai Markov memiliki ruang keadaan {0, 1, 2, 3, 4}.Diketahui P0,4 = 1. Jika rantai berada di keadaan i, i > 0, makakeadaan berikutnya adalah 0, 1, . . . , i− 1 dengan peluang sama(when the chain is in state i, i > 0, the next state is equally likelyto be any of the state 0, 1, . . . , i− 1). Tentukan m.p.t dari rantaiMarkov diatas.









Solusi:

P =

0 0 0 0 11 0 0 0 0

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









7. Tiga dari setiap empat truk yang ada di jalan akan diikuti olehsebuah mobil. Sementara itu, hanya satu dari setiap lima mobilakan diikuti oleh sebuah truk. Bentuk rantai Markov-nya.









Solusi:

P =

(1/4 3/41/5 4/5

)dengan keadaan: ‘0’ truk, ‘1’ mobil.









8. Chen melantunkan 3 koin; M menyatakan keluaran Muka.Misalkan X1 menyatakan banyaknya muncul M. Kemudian,koin-koin yang memiliki keluaran M dilantunkan. Misalkan X2total banyaknya B (termasuk dari koin yang tidak dilantunkan dilantunan kedua). Chen kini melantunkan semua koin yang punyakeluaran B dan misalkan X3 menyatakan total banyaknya M(termasuk dari koin yang tidak dilantunkan). Chen melakukanini terus menerus. Proses {Xn} adalah suatu rantai Markov.Tentukan matriks peluang transisinya









Solusi:

P =

0 0 0 10 0 1/2 1/20 1/4 1/2 1/4

1/8 3/8 3/8 1/8

,

dengan ruang keadaan {0, 1, 2, 3}.









9. Dua tim futsal wanita di MA-ITB akan memainkan tujuhrangkaian pertandingan. Hasil setiap pertandingan saling bebas.Setiap pertandingan akan dimenangkan oleh tim A denganpeluang α dan oleh tim B dengan peluang 1− α. Misalkankeadaan suatu sistem direpresentasikan oleh pasangan (a, b)dimana a menyatakan banyak pertandingan yang dimenangkanA dan b banyak pertandingan yang dimenangkan B. Bentuklahrantai Markov untuk masalah tersebut.









Catatan: a + b ≤ 7 dan rangkaian pertandingan akan berakhir apabilaa = 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








Persamaan Chapman-KolmogorovLatihan

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 dalam n + mtransisi, melalui keadaan k dalam n transisi/langkah.









Latihan

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









Solusi:

P4 =

(0.5749 0.42510.5668 0.4332

)









2. Keadaan hujan pada suatu hari bergantung pada keadaan hujandalam dua hari terakhir. Jika dalam dua hari terakhir hujan makabesok akan hujan dengan peluang 0.7; Jika hari ini hujan dankemarin tidak hujan maka besok akan hujan dengan peluang 0.5;jika hari ini tidak hujan dan kemarin hujan maka besok akanhujan dengan peluang 0.4; jika dalam dua hari terakhir tidakhujan maka besok hujan dengan peluang 0.2. Matriks peluangtransisinya 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. MA4181 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-langkah memenuhisifat:

∞∑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, Laila menggunakanpayung dalam perjalanan kos-kampus atau kampus-kos. Jika harihujan dan payung ada ditempat Laila berada maka Laila akanmenggunakan payung tersebut. Jika hari tidak hujan, Laila selalulupa untuk membawa payung. Misalkan θ adalah peluang hujansetiap kali Laila akan menuju kampus atau kos. Jika Lailamemiliki 3 buah payung, bentuklah suatu rantai Markov dariproses diatas! Berapa peluang Laila akan basah pada suatu hari?(Kerjakan dahulu matriks 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








DefinisiLatihan

Definisi

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

dimana∑∞

i=0 αi = 1. Peluang tak bersyarat dapat dihitung denganmensyaratkan pada keadaan awal,

P(Xn = j) =∞∑

i=0

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

i=0

Pnij αi








DefinisiLatihan

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) bahwa hariakan hujan 4 hari lagi adalah...








DefinisiLatihan

Solusi:

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

10

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








DefinisiLatihan

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 lebih dari 3itu kepada orang lain. Jika setelah dia menerima uang diawalbulan H memiliki uang 5, berapa peluang uangnya akan 1 ataukurang setiap saat selama 4 bulan berikut?








DefinisiLatihan

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








DefinisiLatihan

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


)=

{PI

ij, n genap,PII

ij , n ganjil,

dimana∑2

j=0 PIij =

∑2j=0 PII

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








2. Pandang 3 paket/kotak barang berwarna MERAH, PUTIH,BIRU. Paket barang MERAH memuat 1 kaos merah dan 4 kaosbiru; paket PUTIH memuat 3 kaos putih, 2 kaos merah dan 2kaos biru; paket BIRU memuat 4 kaos putih, 3 kaos merah dan 3kaos biru. Pada tahap awal, sebuah kaos diambil secara acak daripaket MERAH dan dikembalikan (lagi) ke paket tersebut. Padasetiap tahap berikutnya, sebuah kaos diambil secara acak daripaket yang berwarna sama dengan kaos yang terambilsebelumnya dan dikembalikan ke paket tersebut. Bentuklahmatriks peluang transisi yang mungkin.








Solusi:

P =

1/5 0 4/52/7 3/7 2/73/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 peluang transisidan tentukan kelas-kelas keadaan. Bentuk suatu rantai 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. Sebuah rantai Markov {Yt, t ≥ 0} dengan keadaan-keadaan 0,1,2memiliki 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).








Keadaan Dapat Diakses dan BerkomunikasiLatihanLatihanKeadaan Recurrent dan TransientLatihan

Sifat Dapat Diakses dan Berkomunikasi

Keadaan j dikatakan dapat diakses (accessible) dari keadaan i jikaPn

ij > 0 untuk suatu n ≥ 0. Akibatnya, keadaan j dapat diakses darikeadaan i jika dan hanya jika dimulai dari keadaan i proses akanmasuk ke keadaan j. Jika keadaan j tidak dapat diakses dari keadaan imaka peluang masuk ke keadaan j dari keadaan i adalah nol.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 semua i ≥ 02 Jika keadaan i berkomunikasi dengan keadaan j maka keadaan j

berkomunikasi dengan keadaan i3 Jika keadaan i berkomunikasi dengan keadaan j dan keadaan j

berkomunikasi dengan keadaan k maka keadaan i berkomunikasidengan 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.









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 matriks peluang transisi:

P =

0.5 0.5 00.5 0.25 0.250 0.33 0.67

Apakah rantai Markov dengan peluang transisi diatas tidak dapatdireduksi (irreducible)?









3. Apakah yang dapat anda katakan tentang rantai Markov denganmatriks 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 dan Yanidengan 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 dengan peluang1/3(ii) Jika Yani memegang bola pertama kali, dia akan melemparkan keTris; 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 rantai Markov,proses akan dimulai lagi ketika kembali ke keadaan i, danseterusnya, sehingga keadaan i akan dikunjungi lagi. Jikakeadaan i recurrent maka dimulai dari keadaan i maka prosesakan kembali ke keadaan i terus dan terus sebanyak tak hinggakali.









Misalkan keadaan i transient. Setiap kali proses kembali kekeadaan i, terdapat kemungkinan (peluang yang positif) sebesar1− fi bahwa proses tidak pernah kembali ke keadaan i. Dengandemikian, dimulai dari keadaan i, peluang bahwa proses beradadi i sebanyak tepat n periode/kali adalah f n−1

i (1− fi), n ≥ 1. Jikakeadaan i transient maka, dimulai dari keadaan i, banyakperiode/kali bahwa proses akan berada di keadaan i adalahpeubah acak geometrik dengan parameter 1− fi.









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









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 tidak dapatdireduksi adalah recurrent (PENTING!)









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 mana yangtransient!









Solusi:Semua keadaan recurrent.









2. Bagaimana dengan rantai Markov (keadaan: 0,1,2,3,4) denganmatriks 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 mana yangtransient!









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.








DefinisiLatihan

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

)








DefinisiLatihan

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.








DefinisiLatihan

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

ij konvergen ke suatu nilai, untuk n→∞, yang samauntuk semua i. Dengan kata lain, terdapat limit peluang (limitingprobability) bahwa proses akan berada di keadaan j setelahsekian/banyak langkah/transisi. Nilai limit ini saling bebas dengannilai pada keadaan awal.








DefinisiLatihan

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.








DefinisiLatihan

Jika keadaan i recurrent, maka keadaan tersebut akan dikatakanpositive recurrent jika, dimulai dari keadaan i, waktu harapan hinggaproses kembali ke i adalah hingga. Pada rantai Markov yang memilikikeadaan hingga, semua keadaan yang recurrent adalah positiverecurrent. Suatu keadaan yang positive recurrent dan aperiodikdisebut ergodik.








DefinisiLatihan

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.Dosen: Khreshna I.A. Syuhada, MSc. PhD. MA4181 PENGANTAR PROSES STOKASTIK Bab 3 Rantai Markov







DefinisiLatihan

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 di keadaan j








DefinisiLatihan

Jika rantai Markov tidak dapat direduksi, maka terdapat solusiuntuk

π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 akan beradadi keadaan j.








DefinisiLatihan

Latihan

1. Jika hari ini hujan maka besok akan hujan dengan peluang α; jikahari ini tidak hujan maka besok akan hujan dengan peluang β.Jika ′0′ adalah keadaan hujan dan ′1′ adalah keadaan tidak hujanmaka peluang hujan dan tidak hujan untuk jangka panjang adalah








DefinisiLatihan

Solusi:

P =

(α 1− αβ 1− β

),

dan kita punyai persamaan-persamaan:

π0 = απ0 + β π1

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

π0 + π1 = 1








DefinisiLatihan

Kita peroleh peluang hujan dan tidak hujan pada jangka panjang:

π0 =β

1 + β − α

danπ1 =

1− α1 + β − α








DefinisiLatihan

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 percobaan suksesuntuk jangka panjang.








DefinisiLatihan

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








DefinisiLatihan

Kita punyai persamaan-persamaan:

π0 =

π1 =

π2 =

π3 =

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








DefinisiLatihan

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

π0 + π1 = 32/50








DefinisiLatihan

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








DefinisiLatihan

Catatan:

Peluang jangka panjang πj, j ≥ 0, disebut juga peluang stasioner(stationary probability). Jika keadaan awal dipilih berdasarkanpeluang πj, j ≥ 0, maka peluang akan menjadi keadaan j padasetiap waktu n adalah sama dengan πj.

Untuk keadaan j, definisikan mjj yaitu banyak transisi yangdiharapkan (expected number of transitions) hingga suatu rantaiMarkov, dimulai dari keadaan j akan kembali ke keadaantersebut:

πj =1

mjj








1. Seorang dosen KS terus menerus memberikan ujian kepadamahasiswanya. Dosen KS memberikan 3 tipe/jenis ujian denganhasil BAGUS atau JELEK. Misalkan θi adalah peluang bahwamahasiswa mengerjakan BAGUS untuk ujian tipe i. Diketahuiθ1 = 0.3, θ2 = 0.6, θ3 = 0.9. Jika mahasiswa mengerjakandengan BAGUS pada suatu ujian maka tipe ujian berikut yangakan dikerjakan memiliki peluang sama. Jika hasil ujian JELEKmaka ujian berikut adalah ujian tipe 1. Bentuklah rantai Markovuntuk 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 dan munculMUKA maka besok dilantunkan koin 1. Jika munculBELAKANG maka besok akan dilantunkan koin 2. Jika peluangkoin 1 terpilih untuk dilantukan pertama kali adalah 0.5, tentukanpeluang bahwa pada hari ketiga akan dilantunkan koin 1.








Suppose that coin 1 has probability of coming up heads and coin 2 hasprobability 0.6 of coming up heads. If the coin flipped today comesup heads, then we select coin 1 to flip tomorrow. If it comes up tailsthen we select coin 2 to flip tomorrow. If the coin initially flipped isequally likely to be coin 1 or coin 2, then what is the probability thatthe coin flipped on the third day after the initial flip 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 satu keadaanbersifat transient, dan satu unsur dari matriks bernilai nol.








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








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 memakai sepatuadalah

(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. Penumpang yangnaik di area B akan turun di area A dengan peluang 0.3.Keuntungan yang diharapkan (expected profit) sopir taksi untukpelayanan selama di area A adalah 6 dan selama di area B adalah8. Keuntungan yang diharapkan apabila pelayanan taksimelintasi 2 area adalah 12. Hitung keuntungan rata-rata sopirtaksi 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









Pandang matriks peluang transisi (m.p.t) berukuran 3× 3 atau denganruang keadaan {0, 1, 2},

P =

1 0 0α β γ0 0 1

,

dimana α, β, γ > 0 dan α+ β + γ = 1.








Jika, pada waktu t, proses berada di keadaan 0 atau 2, maka prosesakan tetap berada di keadaan itu. Sementara itu, jika proses berada dikeadaan 1, proses akan bergerak ke keadaan lain; jika ke keadaan 0atau 2, maka berlaku proses seperti yang dijelaskan sebelumnya.








Diskusi

Ke keadaan mana, 0 atau 2, proses akan berakhir?

Berapa lama (langkah) proses menuju keadaan tersebut?








Misalkan T = min{n ≥ 0;Xn = 0 atau Xn = 2}. Tentukan

u = P(XT = 0|X0 = 1)

danv = E(T|X0 = 1).








Pada langkah pertama, setelah langkah 0, proses mungkin berada dikeadaan 0, 1 atau 2 dengan peluang berturut-turut α, β, γ. Jika X1 = 0maka T = 1 dan XT = 0; jika X1 = 2 maka T = 1 dan XT = 2. JikaX1 = 1 maka proses berlanjut,

P(XT = 0|X1 = 0) = 1,

P(XT = 0|X1 = 1) = u,

P(XT = 0|X1 = 2) = 0.








atauv =

11− β

.








Catatan:Perhatikan bahwa p.a. T , yang menyatakan langkah untuk mencapaiproses/keadaan yang absorbing, berdistribusi geometrik dengandistribusi peluang

P(T > k|X0 = 1) = βk, k = 0, 1, . . . ,

dan ekspektasi

E(T|X0 = 1) =1

1− β.








Diskusi

Bagaimana dengan m.p.t berikut,

=

1 0 0 0

P10 P11 P12 P13P20 P21 P22 P230 0 0 1

?


ma4181 pengantar proses stokastik bab 3 rantai markov · ketika meninggalkan rumah, ying memakai...

Documents