6.6 Rantai Markov Kontinu pada State Berhingga

Didownload dari www.ririez.blog.uns.ac.id

6.6 Rantai Markov Kontinu pada State Berhingga

Markov chain kontinu 0 adalah proses markov pada state 0, 1, 2,... |

. Diasumsikan bahwa probabilitas transisi adalah stasioner, pada persamaan,

(6.53)

Pada bagian ini kita hanya mempertimbangkan kasus dimana state S berhingga, Sifat Markov menyatakan bahwa memenuhi diberikan tanda {0, 1, 2, ..., N}. (a) 0

(b) ∑

1,

i,j=0,1,...,N dan

(c) ∑

untuk , 0

(Chapman – Kolmogorov relation) 1, 0,

% $

dan ditambahkan pernyataan bahwa (d) lim

!"

#

' Jika menunjukkan matrik & & kemudian sifat (c) dapat ditulis dengan . 0 ,

tersusun pada notasi matrik

, 0

Sifat (d) menegaskan bahwa kontinu pada t=0 karena kenyataannya P(0) (6.54)

= ) (matrix identitas) dipenuhi pada (6.54). Dari persamaan (6.54) bahwa P(t) kontinu lim + lim" + )

untuk semua t>0. Pada kenyataannya jika s=h>0 pada (6.54), dari sifat (d) kita peroleh *!"

. ++

*!

Dengan kata lain, untuk t>0 dan 0
6.55

(6.56)

Tetapi P(h) mendekati identitas ketika h cukup kecil dan +/0 [invers dari P(h)] ada, dan juga mendekati identitas I. Oleh karena itu, lim*!" 1+2

/0

lim*!" . +

(6.57)

Hubungan limit (6.55) dan (6.57) menunjukkan bahwa P(t) adalah kontinu. Sebenarnya, P(t) tidak hanya kontinu tetapi juga differensiable dalam limit lim*!" lim"

*!

0/344 * *

5 ,

+ 5 , +

(6.58) $


ada, dimana 0≤5 <∞ $ dan 0≤5 <∞. Dimulai dengan hubungan

1 + 6 +,

/, 7

Membagi dengan h, dan memisalkan h menurun menuju nol secara langsung menghasilkan hubungan

5 6 5 .

, 7

kecepatan q9 dan q9: mememberikan deskripsi yang sangat kecil dari proses dengan

+ | q9: h oh

+ | 1 . q9 h oh.

=>? $ ,

Berbeda dengan deskripsi distribusi yang sangat kecil (infinitesimal), deskripsi

terdapat untuk durasi yang berdistribusi exponential dengan parameter q9 . Proses ini singgah dari proses menghasilkan sebagai berikut: dimulai pada state i, proses singgah

kemudian melompat ke state j $ i dengan probabilitas P9: q9: /q9 ; waktu singgah dengan state j berdistibusi exponential dengan parameter q: , dan seterusnya. Urutan dari

state-state yang dikunjungi dalam proses, dinotasikan

ξ , ξ0 , …,adalah Rantai Markov

state E , E0 , …, waktu singgah berturut-turut F , F0 , …, masing – masing adalah variable

dengan parameter diskrit, disebut Markov Chain Embedded. Dikondisikan pada urutan independen berdistribusi exponential dengan parameter 5GH , 5GI , …, berturut-turut.

Dengan asumsi bahwa (6.58) terbukti kita dapatkan sebuah pernyataan eksplisit

untuk pada bentuk matrix yang sangat kecil (infinitesimal). .5 50 … 5 5 .50 50 JK K L L 5 50 … .5

+ . ) J +

Hubungan limit (6.58) dapat dinyatakan secara singkat kedalam bentuk matrix lim"

*!

6.59

yang menunjukkan bahwa A adalah turunan matrix dari saat 0. Dapat dirumuskan J N 0.


Dengan bantuan dari (6.59) dan mengacu pada (6.54) kita dapatkan + . O+ . )P + . ) + + +

6.60

N J J

6.61

Limit yang berada disebelah kanan dan menjadi persamaan diferensial matrix

dimana N menunjukkan elemen matrix N Q /Q. Keberadaan N adalah sebuah konsekuensi yang jelas dari (6.59) dan (6.60).

Contoh : Rantai Markov dua state. Berdasarkan rantai Markov dengan state

0,1 yang matrixnya sangat kecil (infinitesimal) adalah 0 1 .S S 0 J R R T .T 1

independen dan berdistribusi eksponensial dengan parameter S. Pada state 1 adalah

Proses ini bergantian antara state 0 dan 1. Waktu singgah pada state 0 adalah

independen dan berdistribusi eksponensial dengan parameter T.

Pada kasus khusus, persamaan diferensial matrix (6.61) menjadi R

N N 0 R R N N 0 0 00

0 .S R R T 00

S R, .T

elemen pertama dari persamaan diatas adalah N .S T0

6.62

selanjutnya 0 1 . , yang terdapat pada (6.62) memberikan N T . S T .

Misalkan V W XYZ . Kemudian

QV W XYZ N S T W XYZ Q W XYZ O N S T


TW XYZ yang dapat diintegralkan secara langsung sehingga menghasilkan V T [ W XYZ Q \ ]

T ^ W XYZ \ ST

Kondisi awal V 0 1 menentukan integrasi konstan menjadi \ S/S T.

Sehingga

dan

T S ^ W XYZ ] ^ V W XYZ ] ST ST

T S W /XYZ ST ST

6.63

0

S S . W /XYZ ST ST

6.64

S T W /XYZ ST ST

6.65

Karena 0 1 . , kita dapatkan

dan, dengan simetri 00 0

T T . W /XYZ ST ST

6.66

Kembali pada rantai Markov umum pada state 0, 1, … … … , ', persamaan

diferensial (6.61) berdasarkan kondisi awal 0 ) dapat diselesaikan dengan metode

standard untuk menghasilkan formula W

ab

i

Ι6

j0

Αe t e g!

6.67


Ketika rantai markov irreducible (semua state terhubung) maka 0

untuk , , … … , ' dan lim

!i

!i m

l 0 ada dengan independen dari state awal i.

Distribusi limitnya dapat ditemukan dengan menghilangkan limit pada (6.61), mengingat bahwa lim

adalah

0 . Hasil persamaan untuk l l , l0 , … … , l

0 lΑ l ,

.5 50 … 5 5 .50 … 50 l0 , … … , l K L L L K 5 50 … .5

yang sama seperti l 5 6 l 5 , 7

0, 1, … … , '

Persamaan (6.68) bersama dengan

l l0 … … l 1

6.68 6.69

menentukan distribusi limitnya. Persamaan (6.68) mempunyai interpretasi keseimbangan massa yang membantu

kita dalam memahaminya. Pada ruas kiri l 5 menjelaskan tingkat jangka panjang ( the long run rate) pada partikel tersebut yang mengeksekusi proses rantai Markov yang bergerak pada state j. Tingkat ini harus sama dengan tingkat jangka panjang ( the long

Dengan kedatangan suatu partikel harus dari state $ , dan sebuah partikel bergerak run rate) pada partikel yang datang pada state j jika keseimbangan harus dipertahankan.

dari state $ ke state j pada tingkat 5 . Oleh karena itu, pada ruas kanan ∑ 7 l 5

memberikan total tingkat partikel yang datang.

Contoh Pergerakan Industri dan Prinsip Peter. Misalkan kita anggap bahwa sebuah posisi penggambar pada sebuah perusahaan mesin yang besar dapat ditempati oleh seorang pekerja pada setiap tiga level : T=Trainee , J=Junior, dan S=Senior Penggambar. Misalkan X(t) menunjukkan tingkat seseorang pada posisi waktu t, dan anggap bahwa X(t) muncul sebagai rantai Markov dimana matriks yang sangat kecil


o

o .rs A= p q rts F ru

p

F

rs .rt 0

0 rtu q .ru

eksponensial yang mempunyai parameter rs dan kemudian menjadi penggambar

Sehingga seorang Trainee tetap pada urutannya untuk distribusi waktu secara

Junior. Seorang penggambar Junior tetap pada level untuk sebuah rentang waktu yang

berdistribusi eksponensial berparameter rt rts rtu . Kemudian penggambar Junior meninggalkan posisi dan digantikan oleh Trainee dengan probabilitas dipromosikan untuk penggambar Senior dengan probabilitas

rts

vrt , atau

rtu vrt , dan seterusnya.

Sebagai alternatifnya, kita boleh mendeskripsikan model dengan menentukan Pr + p| o rs + >+,

perpindahan pada interval waktu pendek sesuai dengan

Pr + o| p rts + >+, Pr + F| p rtu + >+, Pr + o| F ru + >+,

Pr + | 1 . r + >+, untuk i = T, J,S dan

Persamaan untuk distribusi kesetimbangan (l s , lt , lu ) sesuai dengan (6.68) rs l s

rts lt ru lu

rt lt rs l s

ru lu

dan penyelesaiannya

ls lt

lu

1 ls

rtu lt

lt

lu

ru rt , ru rt ru rs rs rtu

ru rs , ru rt ru rs rs rtu

ru rtu , ru rt ru rs r s rtu


Misal kita anggap contoh numerik untuk perbandingan dengan sebuah model alternatif yang terbentuk kemudian. Kita anggap bahwa rata-rata waktu pada ketiga state adalah State

Waktu Rata-Rata

T

0.1

J

0.2

S

1.0

dan bahwa penggambar Junior tetap dan digantikan oleh Trainee dengan probabilitasnya x y

dan dipromosikan untuk penggambar Senior dengan probabilitas

mengarah

pada

penyelesaian

kesetimbangannya adalah

ls

z y

. Anggapan ini

rts 10, rts 2, rtu 3, r{ 1.

Probabilitas

15 5 0.11 15 110 103 45

dan

lt

10 0.22 45

lu |y=0.67 z

Tapi durasi yang dihabiskan orang dalam posisi yang diberikan secara umum tidak berdistribusi eksponensial. Distribusi bimodal adalah sering kali diamati pada banyak orang pergi agak cepat, sementara yang lain bertahan untuk waktu yang penting (substansial). Sebuah penjelasan yang mungkin untuk fenomena ini adalah ditemukan pada “Prinsip Peter”, dimana menyatakan bahwa seorang pekerja dipromosikan sampai akhirnya mencapai sebuah posisi dimana dia tidak kompeten. Ketika hal ini terjadi, pekerja tetap dalam pekerjaannya tersebut sampai pensiun. Kemudian kita modifikasi model

pergerakan

industri

untuk

mengakomodasikan

Prinsip

Peter

dengan

mempertimbangkan dua jenis dari penggambar Junior, Kompeten dan Tidak kompeten. Kita anggap bahwa p sebagian kecil dari Trainee yang kompeten, dan q = 1-p adalah Tidak Kompeten. Kita anggap bahwa penggambar Junior Kompeten tetap pada level untuk durasi berdistribusi eksponensial dengan parameter r} dan kemudian

dipromosikan ke penggambar Senior. Akhirnya, seorang penggambar Junior yang tidak

eksponensial dengan parameter r~ , dan kemudian dia digantikan oleh seorang Trainee.

kompeten tetap pada posisinya sampai ia pensiun, sebuah persinggahan berdistribusi

Matriks yang sangat kecil yang relevan didapatkan oleh


o ) J \ F

K

o .rs r~ ru

) 5rs .r~

\ rs

.r}

F

r} K .ru

Durasi pada posisi penggambar Junior sekarang mengikuti hukum probabilitas yang merupakan campuran dari densitas eksponensial. Untuk membandingkan model ini dengan model sebelumnya, misalkan y , 5 y, r~ 2.86 , dan r} 10. z

x

1 1 3 2 ^ 5 ] ^ ] ^ 0.10 ] ^ 0.35 0.2 r} r~ 5 5

Angka tersebut dipilih sehinngga membuat durasi rata-rata sebagai penggambar Junior, ]

4.0 2.0 1.0 0.6 0.4 0.2 0.1 0.06 0.04 0.02 0

0.2

0.4

0.6

0.8

1.0

Gambar 6.6. Densitas eksponensial (garis lurus) versus densitas eksponensial campuran (garis kurva) . Kedua distribusi mempunyai rata-rata yang sama. Sebuah skala logaritmik digunakan untuk menunjukkan perbedaan.

Sama dengan penghitungan sebelumnya. Densitas probabilitas durasi ini adalah = 10W /0 2.86W /x. untuk 0. z y

x y


eksponensial 5W /y , yang memiliki rata-rata yang sama. Kecenderungan bimodal Densitas ini digambarkan pada Gambar 6.6 untuk perbandingan dengan densitas

diindikasikan pada = ketika mendekati nol dan sangat besar.

Dengan angka yang telah didapatkan dan rs 10 dan ru 1 seperti

sebelumnya, distribusi stasioner (l s , l~ , l} , lu ) didapatkan dengan menyelesaikan 10l s

2.86l~ 4l s ,

10l} 6l s , 1lu

l s 0.111 , l~ 0.155 Penyelesaiannya

2.86l~ ,

1 l s l~

1lu

10l} ,

l}

lu .

lu 0.667 , l} 0.067 Kita gunakan dua pengamatan sebelum meninggalkan contoh ini. Pertama, limit

probabilitas l s , lu , dan lt =l~ l} tepat antara dua model. Ini adalah kejadian umum dalam pemodelan stokastik, dimana dalam perilaku limit dari sebuah proses agak sensitif terhadap rincian tertentu tentang model dan bergantung hanya pada kejadian

pertama atau probabilitas. Ketika hal ini terjadi, asumsi model matematika dapat ditentukan. Pengamatan kedua adalah pokok dari Prinsip Peter. Kita mengasumsikan bahwa

y dari Trainee adalah pengggambar Junior yang kompeten dan hanya 5 y yang z

x

Tidak Kompeten. Namun dalam jangka panjang, seorang Penggambar Junior ditemukan l tidak kompeten dengan probabilitas ~vl l = 0.155/(0.155+0.067)= 0.70 ! ~ } Contoh Redundansi dan Fenomena Burn-in Sebuah sistem reservasi maskapai memiliki dua oneksponensial memiliki parameter T dan digantikan dengan cadangan. Ada satu fasilitas

line, dan satu cadangan. Komputer gagal beroperasi setelah durasi berdistribusi perbaikan dan waktu perbaikan yang berdistribusi eksponensial dengan parameter S.

Anggap adalah jumlah komputer dalam kondisi operasi pada waktu t. Kemudian

adalah sebuah rantai Markov dengan matriks yang sangat kecil


0 J 1 2

0 .S qT 0

Distribusi stasioner l , l0, lx memenuhi

1 S .S T T

2 0 S q .T

Sl Sl Tl0 ,

S Tl0 Sl , Tlx ,

Tlx Sl0 ,

1 l l0

lx,

l l0 lx

1

S 1 T S/Tx

S/T S 1 T S/Tx

S/Tx S 1 T S/Tx

Ketersediaan atau probabilitas bahwa setidaknya satu computer sedang beroperasi

adalah 1 . l l0 lx .

Sering kali dalam praktek asumsi dari distribusi eksponensial tidak realistis maka

(bahaya) ? dihubungkan dengan fungsi densitas probabilitas (pdf) = dari waktu

dari itu disebut fenomena burn-in. Ide ini paling baik dijelaskan dari segi laju hazard kegagalan non negatif waktu T. Mengingat bahwa ?∆ mengukur probabilitas

bersyarat yang gagal dalam interval selanjutnya diberikan , ∆itu terus maju ke waktu t, dan oleh karena itu kita mempunyai ? 0/

, untuk 0

Dimana F(t) adalah fungsi comulatif probabilitas (cdf) dengan fungsi densitas Laju hazard konstan ? S untuk semua t yang sesuai untuk fungsi densitas

probabilitas (pdf)f(t).

probabilitas eksponensial = SW /X untuk 0. Fenomena burn-in digambarkan oleh laju hazard dengan awal yang tinggi dan kemudian menurun ke level yang konstan,


dimana masih terjadi, mungkin kemudian muncul lagi. Itu sesuai pada situasi barang pabrik baru atau baru diperbaiki memiliki probabilitas yang signifikan dari kegagalan awal penggunaannya. Jika item ini bertahan dalam periode ini, bagaimanapun juga akan dioperasikan secara eksponensial. Kesalahan awal mungkin sesuai dalam kegagalan memproduksi atau perbaikan yang salah atau mungkin properti lain yang digunakan. Setiap orang kenal dengan perbaikan automobile yang mempunyai pengalaman fenomena burn-in . Salah satu cara yang mungkin banyak model fenomena burn-in adalah menggunakan campuran dari densitas eksponensial.

r(t)

2

1

.2 Gambar 6.7

.4

.6

.8

laju hazard sesuai dengan densitas diberikan pada (6.70). laju hazard

tertinggi pada 1 nilai awal merupakanfenomena burn-in.

= W / 5W / , 0

(6.70)

dimana 0 1 . 5 1 dan , adalah positif. Fungsi densitas untuk 0.1,

10, 5 0.9, dan 0.909 … 1v1.1 berarti satu. Laju hazard digambarkan dalam gambar 6.7 dimana level awal burn-in tertinggi adalah jelas.

Mungkin kita menggabungkan kecocokan fenomena burn-in ke campuran densitas eksponensial (6.70) dengan mengembangkan state yang ditunjukkan dalam tabel :


Notasi

State

1

Keduanya rusak

0

1 operasi, mempunyai parameter


1


2

2


Persamaan (6.70) bersesuaian untuk probabilitas bahwa operasi akan dimulai

dalam distribusi eksponensial dengan parameter dan probabilitas 5 dengan parameter

. Karena itu mempunyai matriks seperti ini : 0 1 J 1 2 2

0 .S K K

1 S .S

1 5S

2

S .S 5 . 5

2 S

.

K K

Distribusi stasioner dapat ditentukan dengan cara yang biasa dengan mengaplikasikan (6.69)

Contoh Soal : Cuaca kota Bekasi dapat diperkirakan sebagai berikut 1. Jika hari ini cerah maka besok akan berpeluang 60% cuaca cerah, 30% berawan, dan 10% akan turun hujan. 2. Jika hari ini berawan maka besok akan berpeluang 40% cuaca cerah, 45% berawan, dan 15% akan turun hujan. 3. Jika hari ini hujan maka besok akan berpeluang 15% cuaca cerah, 60% berawan, dan 25% akan turun hujan Jika pada hari Jumat hujan maka perkiraan cuaca hari Senin adalah?

Penyelesaian : Time Markov Chain terdapat 3 fase, kita misalkan 1= cerah, 2= berawan, 3= hujan, dan sebelum hari Jumat kita anggap 0, maka

π (0) = (0, 0 ,1)


 .6 .3 .1  A =  .4 .45 .15 Matrik transisi .15 .6 .25 Cuaca pada hari Sabtu π (1)

 .6 .3 .1  π (1) = π (0) A = (0, 0 ,1)  .4 .45 .15 = (.15, .6, .25) .15 .6 .25 maka 15% peluang akan cerah, 60% akan berawan, dan 25% hujan

Cuaca pada hari Minggu π (2)

 .6 .3 .1  π (2) = π (1) A = (.15, .6, .25)  .4 .45 .15 = (.3675, .465, .1675) .15 .6 .25 Cuaca pada hari Senin π (3)

π (3) = π ( 2) A = (.4316, .42, .1484 ) maka 42% peluang akan cerah, 42% akan berawan, dan 15% hujan.

6.6 Rantai Markov Kontinu pada State Berhingga

Recommend Documents