Pengantar Proses Stokastik

Pengantar Proses Stokastik Bab 6: Rantai Markov Waktu Kontinu Atina Ahdika, S.Si, M.Si

Statistika FMIPA Universitas Islam Indonesia 2015

Atina Ahdika, S.Si, M.Si ()

Pengantar Proses Stokastik

Statistika FMIPA Universitas Islam Indonesia / 44

Rantai Markov Waktu Kontinu

Pendahuluan

Pendahuluan

Pada bab ini, kita akan belajar mengenai rantai markov waktu kontinu yang analog dengan rantai markov diskrit yang telah dibahas sebelumnya. Rantai markov waktu kontinu juga memiliki sifat Markov, yaitu diberikan keadaan sekarang, maka keadaan pada masa yang akan datang saling bebas dengan keadaan pada masa lampau.





Pendahuluan

Salah satu contoh dari rantai markov waktu kontinu telah kita temui sebelumnya, yaitu proses Poisson. Misalkan banyaknya kedatangan sampai waktu t (yaitu Nt ) adalah keadaan dari suatu proses pada waktu t, maka proses Poisson merupakan rantai Markov waktu kontinu dengan keadaan-keadaan 0, 1, 2, . . . di mana keadaan selalu bertambah dari keadaan n ke keadaan n + 1, n ≥ 0. Proses demikian dikenal dengan istilah proses kelahiran murni karena ketika sebuah transisi terjadi, maka keadaan akan selalu bertambah satu.





Pendahuluan

Lebih jauh lagi, model Eksponensial yang dapat berpindah hanya dari keadaan n baik ke keadaan n − 1 maupun ke keadaan n + 1 dalam satu kali transisi dinamakan model kelahiran-kematian. Untuk model tersebut, transisi dari keadaan n ke keadaan n + 1 dianggap sebagai proses kelahiran, sedangkan transisi dari keadaan n ke keadaan n − 1 dianggap sebagai proses kematian.





Pendahuluan

Model kelahiran dan kematian secara luas banyak diaplikasikan pada studi tentang sistem biologi dan studi tentang sistem antrian di mana keadaan yang ada merepresentasikan banyaknya nasabah dalam sistem.





Proses Markov

Rantai Markov Waktu Kontinu Misalkan suatu proses stokastik waktu kontinu {Xt , t ≥ 0} bernilai bilangan bulat tak negatif. Sesuai analogi dengan definisi rantai Markov waktu diskrit, suatu proses {Xt , t ≥ 0} adalah rantai Markov waktu kontinu (RMWK) jika untuk semua s, t ≥ 0 dan bilangan bulat tak negatif i, j, xu , 0 ≤ u < s P(Xt+s = j|Xs = i, Xu = xu , 0 ≤ u < s) = P(Xt+s = j|Xs = i) Dengan kata lain, sebuah RMWK adalah suatu proses stokastik yang memiliki sifat Markov yaitu peluang bersyarat dari keadaan Xt+s diberikan keadaan sekarang Xs dan keadaan pada masa lampau Xu , 0 ≤ u < s, hanya bergantung pada keadaan pada masa sekarang dan saling bebas dengan keadaan pada masa lampau.





Proses Markov

Sebagai tambahan, jika P(Xt+s = j|Xs = i) saling bebas dari s, maka RMWK dikatakan memiliki peluang transisi homogen atau stasioner. Semua rantai Markov pada materi ini akan diasumsikan memiliki peluang transisi stasioner.





Proses Markov

Misalkan sebuah RMWK masuk ke keadaan i pada suatu waktu, misalkan, waktu 0, dan misalkan proses tersebut tidak meninggalkan keadaan i (tidak terjadi transisi) selama 10 menit ke depan. Berapa peluang bahwa proses tidak akan meninggalkan keadaan i selama 5 menit selanjutnya? Karena proses berada di keadaan i pada waktu 10, maka berdasarkan sifat Markov, peluang bahwa proses akan tetap berada di keadaan i selama interval [10, 15] merupakan peluang (tak bersyarat) bahwa proses tetap berada di keadaan i selama minimal 5 menit. Misalkan Ti menyatakan lamanya waktu proses berada di keadaan i sebelum berpindah ke keadaan lain, maka P(Ti > 15|Ti > 10) = P(Ti > 5) atau secara umum, P(Ti > s + t|Ti > s) = P(Ti > t) untuk semua s, t ≥ 0. Dengan demikian, peubah acak Ti bersifat memoryless dan berdistribusi eksponensial. Atina Ahdika, S.Si, M.Si ()




Proses Markov

Perhatikan proses Markov (stasioner) dengan ruang parameter kontinu (parameternya biasanya adalah waktu). Transisi dari satu keadaan ke keadaan lain dapat terjadi dalam waktu yang singkat. Berdasarkan sifat Markov, waktu yang dihabiskan dalam sebuah sistem diberikan sebarang keadaan bersifat memoryless; distribusi dari waktu yang tersisa bergantung semata-mata hanya pada keadaan namun tidak pada lamanya waktu yang telah dihabiskan di keadaan tersebut.





Proses Markov

Sebuah proses Markov Xt ditentukan oleh matriks generator atau matriks laju transisi. qi,j = lim

∆t→0

P(Xt+∆t = j|Xt = i) , ∆t

i 6= j

Peluang per satuan waktu bahwa sistem melakukan transisi dari keadaan i ke keadaan j laju transisi atau intensitas transisi Total laju transisi keadaan i adalah X qi,j , umur suatu keadaan ∼ Eksp(qi ) qi = j6=i

Berikut ini adalah laju di mana peluang keadaan i berkurang. Definisikan qi,i = −qi Atina Ahdika, S.Si, M.Si ()




Matriks Laju Transisi


Matriks laju transisi dituliskan sebagai berikut     −q0 q0,1 · · · q0,0 q0,1 · · ·     Q = q1,0 q1,1 · · · =  q1,0 −q1 · · · .. .. .. .. .. .. . . . . . . Jumlah tiap baris adalah nol.






Laju Transisi dan Peluang Transisi

Kaitan antara laju transisi dengan peluang transisi adalah sebagai berikut pi,j = lim P(Xt+∆t = j|Xt+∆t 6= i, Xt = i) ∆t→0

P(Xt+∆t = j, Xt+∆t 6= i|Xt = i) = lim ∆t→0 P(Xt+∆t 6= i|Xt = i)  q  P i,jq i 6= j i,j j =  0 i =j






Jika dituliskan dalam bentuk matriks peluang transisi, maka   q0,1 q0,2 P P 0 · · · qi,j qi,j   j6=i j6=i  Pq1,0  q 1,2 P   0 · P =  qi,j qi,j  j6 = i j6 = i   .. .. .. .. . . . . Total jumlah per baris adalah satu.






Peluang Keadaan Vektor peluang keadaan πi (t) = P(Xt = i) sekarang adalah fungsi yang bergantung waktu, yaitu d π(t) = π(t) · Q dt dengan π(t) = (π0 (t) π1 (t) π2 (t) · · · ) Berdasarkan sistem persamaan diferensial, misalkan π(t) = Ce Qt , maka d d π(t) = (Ce Qt ) dt dt = QCe Qt = Qπ(t)






Misalkan nilai awal C = π(0), maka solusi formal untuk vektor peluang keadaan yang bergantung waktu adalah π(t) = π(0)e Qt






Global Balance Conditions

Solusi stasioner π = lim π(t) tidak tergantung waktu, dengan demikian t→∞

π·Q =0 Kondisi kesetimbangan tersebut memperlihatkan kesetimbangan antara peluang kejadian masuk dan kejadian keluar dari i.





π · Q = (π0 π1 π2


  −q0 q0,1 q0,2 · · ·   · · · )  q1,0 −q1 q1,2 · · · = 0 .. .. .. .. . . . .

−q0 π0 + q1,0 π1 + q2,0 π2 + . . . = 0 q0,1 π0 − q1 π1 + q2,1 π2 + . . . = 0 .. . Jika bagian yang negatif dipindah ruas ke kanan, maka q1,0 π1 + q2,0 π2 + . . . = q0 π0 q0,1 π0 + q2,1 π2 + . . . = q1 π1 .. .






Secara umum, kita peroleh persamaan kesetimbangan tersebut yaitu Untuk baris ke-j X qj πj = πi qi,j i6=j

X

qj,i πj =

i6=j

X

πi qi,j

i6=j

atau dengan kata lain X i6=j


πj qj,i =

X

πi qi,j

i6=j




Proses Kelahiran-Kematian


Perhatikan sebuah sistem di mana keadaan di setiap waktu direpresentasikan oleh banyaknya orang yang berada dalam sistem tersebut. Misalkan setiap kali ada i orang dalam sistem, maka kedatangan baru masuk ke dalam sistem dengan laju eksponensial sebesar λi orang meninggalkan sistem dengan laju eksponensial sebesar µi






Dengan kata lain, setiap kali ada i orang di dalam sistem, maka waktu sampai kedatangan berikutnya berdistribusi eksponensial dengan mean λ1i dan saling bebas dengan waktu sampai keberangkatan berikutnya di mana keberangkatan tersebut berdistribusi eksponensial dengan mean µ1i . Sistem seperti ini disebut proses kelahiran-kematian. Parameter {λi }∞ i=0 dan {µi }∞ secara berturut-turut adalah laju kedatangan (kelahiran) dan laju i=1 keberangkatan (kematian).






Dengan demikian, sebuah proses kelahiran-kematian merupakan RMWK dengan keadaan {0, 1, . . .} di mana transisi dari keadaan i hanya bisa berpindah ke keadaan j = i + 1 atau j = i − 1.   λi jika j = i + 1 qi,j = µi jika j = i − 1   0 lainnya Atau jika digambarkan






Matriks untuk Q adalah  −λ0 λ0 0 0  µ1 −(λ1 + µ1 ) λ 0 1   0 µ2 −(λ2 + µ2 ) λ2 Q=  0 0 µ −(λ + µ3 ) 3 3  .. .. .. .. . . . .



 ... . . .  . . .  . . .  .. .




Dengan menggunakan hubungan di atas, maka diperoleh matriks P sebagai berikut   0 1 0 0 ... λ1  µ1 0 0 . . .  λ1 +µ1  λ1 +µ1   µ2 λ2  0 0 . . . P= λ2 +µ2 λ2 +µ2   µ3  0  0 0 . . . λ +µ 3 3   .. .. .. .. .. . . . . .






Dengan demikian, diperoleh hubungan antara laju transisi dengan peluang transisinya secara umum adalah: P01 = 1 λi ,i > 0 λi + µ i µi = ,i > 0 λi + µ i

Pi,i+1 = Pi,i−1





Peluang Kesetimbangan Proses Kelahiran-Kematian

Peluang Kesetimbangan Proses Kelahiran-Kematian Untuk menyelesaikan kasus di atas, kita akan menggunakan global balance condition pada keadaan-keadaan 0, 1, . . . , k. Berdasarkan kesetimbangan proses masuk dan keluar, maka λk πk = µk+1 πk+1 , k = 0, 1, 2, . . . Selanjutnya kita peroleh bentuk rekursif πk+1 =

λk πk µk+1

Berdasarkan persamaan rekursif di atas, kita bisa menuliskan semua peluang keadaan dalam bentuk π0 yaitu πk =


λk−1 λk−2 . . . λ0 k−1 λi π0 = Πi=0 π0 µk µk−1 . . . µ1 µi+1 Pengantar Proses Stokastik



Ingat! Peluang keadaan memiliki sifat

∞ P


πk = 1. Dengan menggunakan sifat

k=0

tersebut, kita peroleh ∞ X

πk = π0 +

k=0

∞ X

k−1 Πi=0

k=1

" 1 = π0 1 +

∞ X

λi π0 µi+1

Πk−1 i=0

k=1

λi µi+1

#

1

π0 = 1+

∞ P k=1

λi Πk−1 i=0 µi+1

Setelah memperoleh nilai π0 , maka kita juga bisa mendapatkan nilai dari πk . Atina Ahdika, S.Si, M.Si ()





Contoh

1. Misalkan suatu proses kelahiran dan kematian memiliki konstan birth rate λ = 2 dan konstan death rate µ = 3. Tentukan nilai π0 dan πk pada model tersebut dengan menggunakan analisis persamaan kesetimbangan!






Solusi: Perhatikan proses berikut






Dengan menggunakan persamaan kesetimbangan diperoleh 2π0 = 3π1 2π1 = 3π2

2 ⇒ π1 = π0 3 2 2 2 ⇒ π2 = π1 = π0 3 3

.. . 2πk−1 = 3πk


k 2 ⇒ πk = π0 3




Selanjutnya, gunakan sifat

∞ P


πk = 1

k=0 ∞ X

πk =

k=0

∞ k X 2 k=0

3

1 = π0 + π0 " 1 = π0 1 +

π0

∞ k X 2 k=1 ∞ X k=1

π0 = 1+

1 ∞ P k=1

3 2 3

k #

1 1 = = 1+2 3 2 k 3

Substitusikan nilai π0 ke dalam persamaan πk sehingga diperoleh k 2 1 2 k πk = π0 = 3 3 3 Atina Ahdika, S.Si, M.Si ()





2. Misalkan di sebuah Bank terdapat tiga orang teller dan dua buah kursi tunggu. Misalkan setiap nasabah datang dengan laju λ dan waktu layanan di setiap teller adalah sebesar µ. Hitunglah peluang bahwa tidak ada nasabah yang datang ke Bank jika diketahui λ = 1 dan µ = 2! Tentukan pula peluang terdapat 4 nasabah di dalam Bank!






Solusi: Perhatikan ilustrasi berikut:






Jadi, prosesnya dapat digambarkan dalam diagram:






Maka λπ0 = µπ1 λπ1 = 2µπ2 λπ2 = 3µπ3 λπ3 = 3µπ4 λπ4 = 3µπ5


→ π1 =

λ π0 µ

2 λ π0 µ λ 1 λ 3 π0 → π3 = π2 = 3µ 6 µ 1 λ 4 λ → π4 = π3 = π0 3µ 18 µ λ 1 λ 5 → π5 = π4 = π0 3µ 54 µ 1 λ π1 = → π2 = 2µ 2





Dengan menggunakan sifat jumlah total peluang maka diperoleh 2 1 λ 3 1 λ 4 1 λ 5 λ π0 + π0 + π0 + π0 = 1 µ 6 µ 18 µ 54 µ # λ 1 λ 2 1 λ 3 1 λ 4 1 λ 5 1+ + + + + =1 µ 2 µ 6 µ 18 µ 54 µ

λ 1 π0 + π0 + µ 2 " π0

Diketahui λ = 1 dan µ = 2, maka peluang tidak ada nasabah datang ke Bank adalah 1 1 1 1 1 1 1 1 1 π0 1 + + . + . + . + . =1 2 2 4 6 8 18 16 54 32 1.6499π0 = 1 π0 = 0.606






Selanjutnya, peluang terdapat empat nasabah di Bank adalah: 1 λ 5 π4 = π0 54 µ 1 1 = . .0.606 54 32 = 0.0003507






3. (Model Perbaikan Sebuah Mesin) Di dalam sebuah toko terdapat M mesin dan seorang tukang. Misalkan lamanya waktu untuk masing-masing mesin bekerja sebelum akhirnya rusak berdistribusi Eksponensial dengan rate λ dan lamanya waktu mesin tersebut diperbaiki oleh tukang berdistribusi Eksponensial dengan rate µ. Berapa peluang bahwa sebanyak n mesin akan tidak digunakan? Berapa rata-rata banyaknya mesin yang tidak digunakan? (Petunjuk: Gunakan persamaan kesetimbangan untuk menyelesaikan masalah tersebut, keadaannya menyatakan banyaknya mesin yang rusak).






Solusi: Misalkan sistem berada di keadaan n jika sebanyak n mesin tidak digunakan, maka proses tersebut merupakan proses birth and death dengan parameter: µn = µ n≥1 (M − n)λ n ≤ M λn = 0 n>M






Proses tersebut dapat digambarkan sebagai berikut:






Dengan menggunakan persamaan kesetimbangan maka, Mλπ0 = µπ1 (M − 1)λπ1 = µπ2 (M − 2)λπ2 = µπ3

Mλ π0 µ (M − 1)λ (M − 1)Mλ2 ⇒ π2 = π1 = π0 µ µ2 (M − 2)λ (M − 2)(M − 1)Mλ3 ⇒ π3 = π2 = π0 µ µ3 ⇒ π1 =

.. . (M − n)λπn = µπn+1 Secara umum diperoleh πn yaitu (M − n + 1)(M − n + 2) . . . (M − 1)Mλn π0 µn n M! λ = π0 (M − n)! µ

πn =





Selanjutnya gunakan sifat

M P


πn = 1 sehingga diperoleh:

n=0 M X

M X

n λ πn = π0 µ n=0 n=0 n M X M! λ 1 = π0 + π0 (M − n)! µ n=1 " n # M X λ M! 1 = π0 1 + (M − n)! µ M! (M − n)!

n=1

1

π0 = 1+

M P n=1


M! (M−n)!

n λ µ





Substitusikan nilai π0 ke dalam persamaan πn dan diperoleh peluang bahwa sebanyak n mesin tidak digunakan yaitu n λ M! n (M−n)! µ M! λ πn = π0 = n M (M − n)! µ P M! λ 1+ (M−n)! µ n=1






Selanjutnya, rata-rata banyaknya mesin yang tidak digunakan adalah M X n=0

M P

nπn =

n=0

1+

M! n (M−n)!

M P n=1


n

M! (M−n)!


λ µ

n λ µ




4. Di dalam suatu kantor kecamatan, terdapat tiga petugas yang melayani proses pembuatan KK (P1 , P2 , P3 ). Setiap warga yang akan mengurus KK harus menyelesaikan urusan kelengkapan administrasi di P1 , kemudian perekapan data di P2 , dan terakhir adalah tandatangan serta menerima berkas KK sementara di P3 . Petugas P1 melayani dengan laju µ = 3, petugas P2 dengan laju µ = 2, dan petugas P3 dengan laju µ = 4. Setiap warga datang ke kantor kecamatan dengan laju λ = 3. Berapa peluang ada n orang di dalam kantor kecamatan?




Pustaka

Pustaka

Pustaka

Ross, Sheldon M. 2007. Introduction to Probability Models; 9th Edition. New York: Academic Press. Taylor, Howard M. dan Samuel Karlin. 1975. A First Course in Stochastic Processes; Second Edition. New York: Academic Press. Virtamo, J. 38.143 Queueing Theory/ Probability Theory.




Pengantar Proses Stokastik

Recommend Documents