Proses Stokastik-2015 PDF [PDF]

Citation preview

Proses Stokastik (MMM 5403)



Silabus Status: Wajib Minat Statistika Rantai Markov, klasifikasi rantai Markov. Limit rantai Markov dan aplikasinya. Rantai Markov kontinu, contoh-contoh klasik. Proses renewal, variasi dan generalisasinya.



Proses Stokastik Stokastik (stochastic) Berasal dari bahasa Yunani stokhastikos ( stokhos: target



́ ) : able to guess



Studi tentang fenomena random atau proses random



Contoh 1. Banyaknya kecelakaan kendaraan bermotor di suatu kota di suatu waktu tertentu 2. Lama antrian pada suatu tempat pelayanan (kasir di mall, check in di bandara, counter di bank, dst) 3. Nilai stock (saham) pada saat tertentu 4. Kecepatan angin pada lokasi tertentu, ketinggian tertentu dan saat tertentu 5. Contoh lain ....



Definisi Suatu proses stokastik adalah kumpulan variabel random berindeks { : ∈ } pada ruang probabilitas {Ω, ℱ, } yang bernilai . Himpunan sering disebut sebagai state space; adalah himpunan indeks (index set) Himpunan indeks dapat berupa bilangan bulat ℤ atau bilangan real ℛ. Dalam banyak aplikasi himpunan indeks adalah waktu = { ≥ 0}



Klasifikasi menurut



Berindeks diskrit (waktu diskrit) bila = ℤ Contoh # adalah nilai stock (saham) harian, $, %, … , indeksnya ' ∈ ℤ(



Berindeks kontinu (waktu kontinu) bila = ℛ Contoh ) adalah banyaknya kecelakaan dalam suatu waktu tertentu { ) : ≥ 0}



Klasifikasi menurut multidimensi Contoh: Kecepatan angin pada suatu lokasi * di bumi { + : * ∈ ℛ, } dengan lokasi ditentukan oleh lintang, bujur dan ketinggian



Catatan terkait • Urutan dari indeks menunjukkan perkembangan, proses atau evolusi dari fenomena random yang menjadi perhatian • Urutan menjadi “hilang” atau lebih sulit ditentukan untuk indeks yang multidimensi. Proses seperti ini sering dinamakan random fields



Variabel random •



dan



dapat berupa bilangan random diskrit atau kontinu • Realisasi proses stokastik { } adalah - ∈ Ω, disebut juga sebagai sample paths



Karakteristik Proses Stokastik • State space (status) , yang merupakan kumpulan nilai-nilai yang mungkin dari proses stokastik ) • Himpunan indeks , yang sering disebut time parameter • Distribusi bersama variabel random )



Memodelkan Proses Stokastik Untuk sekumpulan pengamatan distribusi bersama ) adalah ( )0 ≤ x% ; )4 ≤ x. ; … ;



%, ., … , #



)5



≤ x6 )



,



Sample Path # (-)



0



1



2



3



...



'



Sample Path ) (-)



0



Random Walk #



#



=



$



2



#



+9



:



3



4



:;%



:



adalah v.r. Bernoulli bernilai +1 atau −1



1 0 1 -1 -2



2



#



5



6



'



Random Walk 1. Homogen secara spasial (spatially homogeneous), # => $ =? = # =>+@ $ =?+@ 2. Homogen menurut waktu (temporally homogeneous) # => $ =? = A(# = > A =? 3. Mempunyai sifat Markov A(# = > $, %, … , A = A(# = > A , '≥0



Independent Increments



, ∈ } dikatakan memiliki Proses stokastik { “penambahan independen” (independent increments) bila untuk semua % < . < ⋯ < # , berlaku variabel random . − % , , − . … # − #E% yang independen Untuk proses stokastik waktu diskrit = 0,1,2, … , : = G − 1, : = :E% , H: = : − :E% , G = 1,2, … dan H$ = $



Latihan 1. Amatilah suatu proses di sekitar saudara, jelaskan proses tersebut, klasifikasikan , dan distribusi ) (sesuai asumsi) 2. Tunjukkan bahwa proses dengan penambahan independen (independent increment process) selalu merupakan proses Markov



Rantai Markov Definisi Proses stokastik waktu diskrit # adalah suatu Rantai Markov (Markov Chain) bila memenuhi # =I $ = J$ , % = J% , … , #E% = J#E% = ( # = I ∣ #E% = J#E% ) Untuk semua ' ≥ 1 dan semua I, J$ , J% , … , J#E% ∈



Rantai Homogen Definisi Rantai dikatakan homogen bila #(% = > # =G = % => untuk semua ', G, >



$



=G ,



Contoh: Rantai Markov yang Homogen Tunjukkan bahwa barisan variabel random independen yang mempunyai nilai berhingga adalah suatu Rantai Markov. Dalam kondisi apa rantai tersebut homogen? Jawab:



Diketahui $ , % , … , # variabel random independen. # = J# $ = J$ , … , #E% = J#E% = ( # = J# , $ = J$ , … , #E% = J#E% )/ ( $ = J$ , … , #E% = J#E% ) karena independen, = # = J# (juga untuk ( # ∣ #E% ) = ( # = J# )) Homogen bila : berdistribusi identik (kondisi yg diberikan)



Matriks Transisi



Matriks transisi M = {N:O } adalah matriks bujursangkar ×| | N:O = #(% = > # =G



M suatu matriks stokastik, bila (a) Mempunyai elemen non-negatif, N:O ≥ 0, untuk semua G, > (b) Mempunyai jumlah baris 1, ∑O N:O = 1, untuk semua G



Matriks Transisi Matriks transisi n langkah M S, S + ' = N:O (S, S + ') dengan N:O S, S + ' =



A(#



=>



Dengan asumsi homegenitas M S, S + 1 = M



A



=G



Contoh 1: Matriks Transisi



Diberikan { # ; ' > 0} adalah rantai Markov dengan status 0,1,2 dan matriks transisi 3/4 1/4 0 1/4 1/2 1/4 0 3/4 1/4



dan distribusi awal



$



=G =



% ,G ,



= 0,1,2.



Contoh 1: Matriks Transisi (lanjutan) Hitung 1. N.% 2. N%.



3. 4. 5.



= 2, % = 1 ( . = 2, % = 1, ( , = 1, . = 2, .



=2 $ = 2) % = 1, $



$



= 2)



Persamaan Chapman-Kolmogorov Teorema N:O S, S + ' + Y



= 9 N:+ S, S + ' N+O (S + ', S + ' + Y) +



Bukti: ......(di papan tulis)



Persamaan Chapman-Kolmogorov Sehingga M S, S + ' + Y = M S, S + ' M(S + ', S + ' + Y) Dan M S, S + ' = M#



Karena M S, S + ' = M(0, '), M S, S + ' sering ditulis M# , dan N:O ' = N:O (S, S + ')



Persamaan Chapman-Kolmogorov (#) Z:



= (



Fungsi prob



#



#



= G) [



(#)



=



(#) Z: : G



∈



Lemma [(A(#) = [(A) M# ;untuk S = 0 [(#) = [($) M# Proses random dari rantai Markov ditentukan oleh matriks transisi M dan nilai probabilitas awal [($)



(Bukti menggunakan Teorema Chapman-Kolmogorov)



Contoh: Transisi 2 Langkah



Matriks transisi 2 langkah dari proses { 0} contoh di depan 3/4 1/4 0



1/4 0 3/4 1/2 1/4 1/4 3/4 1/4 0 5/8 5/16 5/16 1/2 3/16 9/16



#; '



1/4 0 1/2 1/4 = 3/4 1/4 1/16 3/16 1/4



>



Latihan 1 1. Suatu dadu dilempar berkali-kali. Yang mana dari pernyataan di bawah ini merupakan Rantai Markov? 1) 2) 3) 4)



Bilangan (mata dadu) terbesar # yang muncul pada lemparan ke-' Bilangan _# bernilai 6 dalam ' lemparan Pada saat Y, waktu `a sejak kemunculan 6 terakhir Pada saat Y, waktu ba sampai muncul 6 berikutnya



2. Diberikan { # : ' ≥ 0} adalah simple random walk dengan $ = 0, tunjukkan bahwa # = | # | adalah rantai Markov dan tuliskan probabilitas transisi dari rantai ini.



Latihan 2 Suatu sistem komunikasi melakukan transmisi digit 0 dan 1 melalui beberapa tahap. Diberikan { # ; ' ≥ 1} adalah proses digit melewati tahap ke-' dan $ adalah digit awal. Probabilitas digit tidak berubah ketika melewati suatu tahap adalah c, dan N jika digit berubah, N + c = 1. a. Tuliskan matriks transisi untuk proses ini. b. Tunjukkan bahwa 1 1 1 1 A + c−N − c−N A 2 2 A = 2 2 1 1 1 1 A − c−N + c−N A 2 2 2 2



Klasifikasi Status • • • • •



persistent (recurrent) transient null dan non-null periodic, aperiodic ergodik



Persistent dan Transient Status G disebut persistent (recurrent) bila # = G untuk beberapa ' ≥ 1 $ =G =1 Probabilitas kembali ke status G, untuk suatu proses yang dimulai dari G, adalah 1. Jika probabilitas kurang dari 1 disebut transient



Definisi



First Passage Time



Probabilitas kunjungan pertama ke status > diawali dari status G, dalam ' langkah q:O ' =



%



≠ >,



.



≠ >, … ,



#E%



≠ >,



#



=>



$



=G



Probabilitas bahwa rantai pernah mengunjungi >, dimulai dari G s



q:O = 9 q:O (') #;%



Status > persistent jhj qOO = 1



(jhj: iff)



Mean recurrent time



Mean recurrent time t: suatu status G t: = u v: $ =G



9 'q:: (') jika G persistent =w # ∞ jika G transient



Null dan Non-Null Definisi Status G yang persistent disebut Null bila t: = ∞ Status G yang persistent disebut Non-Null (positif) bila t: < ∞



Periode Definisi Periode suatu status { G = gcd ': N:: ' > 0 • Status G Neriodic jika { G > 1 • Status G ?periodic jika { G = 1 • Status G }rgodic jika persistent, non-null dan aperiodic (gcd=greatest common divisor => f p b)



Klasifikasi Rantai – G terhubung dengan >, ditulis G → > jika rantai pernah berada di > dengan probabilitas bukan nol, atau N:O S > 0, untuk S ≥ 0



• Communicates (terhubung)



– G dan > saling terhubung bila G → > dan > → G atau ditulis G ↔ >



• Intercommunicate (saling terhubung)



Klasifikasi Rantai



Himpunan status ` • Closed, bila N:O = 0 untuk semua G ∈ `, > ∉ `



– Tidak ada state di luar ` yang dapat dicapai dari ` – Jika hanya terdiri atas satu state dinamakan absorbing • G absorbing jhj N:: = 1 dan N:O = 0



• Irreducible, bila G ↔ > untuk semua G, > ∈ `



– Semua status dapat dicapai dari status yang lain



Contoh: Klasifikasi Diketahui matriks transisi suatu Rantai 0 1 0 = 1/2 0 1/2 0 1 0 irreducible, .



1/2 = 0 1/2



0 1/2 1 0 0 1/2



,



=



Contoh: Klasifikasi (lanjutan) Secara umum .# = . ; .#(% = Periodik 2 N:: 2' > 0; N:: 2' + 1 = 0 untuk setiap G



Distribusi Stasioner Definisi Vektor [ dikatakan distribusi stasioner suatu Rantai bila [ = (ZO : > ∈ ) sedemikian sehingga 1. ZO ≥ 0 untuk semua >, dan ∑O ZO = 1 2. [ = [M, yaitu ZO = ∑: Z: N:O , untuk semua > Dikatakan stasioner karena [M• = [M M = [M = [, jadi [M‚ = [ untuk semua ' ≥ 0



Persistensi Kunjungan Teorema Jika status > persistent, maka untuk setiap status * yang dapat dikunjungi dari status >, qO+ = 1 Bukti ....



Distribusi Stasioner sebagai suatu Limit Teorema Untuk suatu rantai yang irreducible dan ergodic, limit ZO = lim N:O (') #→s



ada dan independen terhadap status awal >. Bukti: ....



Menghitung Menggunakan [ = [M atau [(M − ƒ) = 0 ...........................(1) dan ketentuan bahwa ∑O ZO = 1 .........(2) Dapat dicari [ = (ZO : > ∈ ) yang memenuhi (1) dan (2) Matriks (M − ƒ) mempunyai rank − 1, bersama dengan ∑O ZO = 1, ZO dapat dicari penyele saiannya



Contoh: distribusi stasioner Diketahui matriks transisi suatu Rantai sbb.: 0 2/3 1/3 0 1/2 = 1/2 1/2 1/2 0



Hitung



.



,



,



,



„



untuk ' → ∞?



Contoh: distribusi stasioner Dapat disusun sistem persamaan linear [(M − ƒ) = 0 dan ∑O ZO = 1 1 1 −Z% + Z. + Z, = 0 2 2 2 1 Z% − Z. + Z, = 0 3 2 Z% + Z. + Z, =1 Diperoleh Z% = 1/3 , Z. = 10/27, Z, = 8/27



Contoh: distribusi stasioner (2) Diberikan Rantai Markov 1−? ? 0 < ?, @ < 1 = @ 1−@ Hitung distribusi stasioner rantai di atas!



Inferensi untuk Rantai Markov



Diberikan Rantai Markov dengan S status dan matriks transisi M = N:O , dan ':O , yaitu transisi empiris (data) dari status G ke >, dengan total banyaknya observasi (_ + 1) A ∑A ∑ ' = ' dan G, > = 1,2, … , S :⦁ O;% :O :;% ':O = '⦁O Dengan estimasi Maximum Likelihood (distribusi multinomial) diperoleh ':O N̂ :O = ':⦁



Uji Hipotesis Menguji apakah data mengikuti model rantai Markov dengan probabilitas transisi M ‰$ : M = M$ Digunakan statistik ':⦁ N̂ :O − N$:O Š = 99 N$:O A



A



.



,



G, > = 1,2, … , S



Untuk _ besar, Š akan berdistribusi derajad bebas m(S − 1) :;% O;%



.



dengan



Contoh: Uji Hipotesis Diperoleh data empiris curah hujan dengan status 0=hari kering ; 1=hari hujan sebagai berikut 0 1 total 0 175 49 224 1 48 96 144 total 223 145 368 Apakah data tersebut mengikuti model rantai Markov 1/2 1/2 dengan matriks transisi 1/2 1/2 ?



Contoh: Uji Hipotesis ':⦁ N‹:O − N$:O 99 N$:O



Diperoleh



A



A



.



= 86,875



:;% O;%



Dengan derajad bebas 2. Diperoleh p-value yang sangat kecil, sehingga ‰$ ditolak.



Latihan 1 Tiga anak bermain bola dalam formasi lingkaran, tiap anak diberi nama 1,2,3 . Setiap anak memiliki peluang yang sama untuk melempar ke dua anak yang lain. Carilah matriks transisi untuk proses Markov ini. Hitung . =1 $ =1 , . =2 $ =3 , . =3 $ =2



Latihan 2 Diketahui matriks transisi suatu Rantai sbb.: 1 0 0 = 0 1 0 N% N. N, dengan ∑NO = 1. Hitung distribusi limit [.



Latihan 3 Misalkan menurut ahli sosiologi dalam suatu komunitas atau populasi diasumsikan bahwa kelas sosial seseorang dipengaruhi oleh orang tuanya saja dan bukan oleh kakek/neneknya dengan matriks probabilitas transisi:



Dalam jangka panjang, berapa persentase orang yang akan berada di kelas menengah?



Latihan 3 (lanjutan) Apabila diperoleh data frekuensi empiris dari populasi tersebut sebagai berikut



apakah data empiris mengikuti model yang diajukan oleh ahli sosiologi tersebut? ( = 0,05)