Silabus Proses Stokastik (MMM 5403)
Proses Stokastik Stokastik (stochastic) Berasal dari bahasa Yunani stokhastikos ( stokhos: target
́ ) : able to guess
Studi tentang fenomena random atau proses random
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.
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 multidimensi Contoh: Kecepatan angin pada suatu lokasi * di bumi { + : * ∈ ℛ, } dengan lokasi ditentukan oleh lintang, bujur dan ketinggian
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}
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
Karakteristik Proses Stokastik
dan
•
dapat berupa bilangan random diskrit atau kontinu • Realisasi proses stokastik { } adalah - ∈ Ω, disebut juga sebagai sample paths
• 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
Random Walk
) (-)
#
#
=
$
2
#
+9
:
3
4
:;%
#
: adalah v.r. Bernoulli bernilai +1 atau −1
1 0 1 -1
2
5
6
'
0 -2
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
Proses stokastik { , ∈ } dikatakan memiliki “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
Rantai Markov
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 Homogen Definisi Rantai dikatakan homogen bila #(% = > # =G = % => untuk semua ', G, >
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% ∈
Contoh: Rantai Markov yang Homogen
$
=G ,
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
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. % ,
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 (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 (#) 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)
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 + ')
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/4 0 1/2 1/4 1/4 1/2 1/4 = 3/4 1/4 0 3/4 1/4 5/8 5/16 1/16 5/16 1/2 3/16 3/16 9/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 + c−N A − c−N A 2 2 2 2 A = 1 1 1 1 − c−N A + 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
Mean recurrent time
Mean recurrent time t: suatu status G t: = u v: $ =G
9 'q:: (') jika G persistent =w # ∞ jika G transient
(jhj: iff)
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)
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
,
=
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 (lanjutan) Secara umum .# = . ; .#(% = Periodik 2 N:: 2' > 0; N:: 2' + 1 = 0 untuk setiap G
Distribusi Stasioner
Persistensi Kunjungan
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
Teorema Jika status > persistent, maka untuk setiap status * yang dapat dikunjungi dari status >, qO+ = 1
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: ....
Bukti ....
Menghitung Menggunakan [ = [M atau [(M − ƒ) = 0 ...........................(1) dan ketentuan bahwa ∑O ZO = 1 .........(2) Dapat dicari [ = (ZO : > ∈ ) yang memenuhi (1) dan (2) − 1, bersama Matriks (M − ƒ) mempunyai rank 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 (2) Diberikan Rantai Markov 1−? ? = 0 < ?, @ < 1 @ 1−@ Hitung distribusi stasioner rantai di atas!
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
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 G, > = 1,2, … , S O;% ':O = ':⦁ dan ∑:;% ':O = '⦁O Dengan estimasi Maximum Likelihood (distribusi multinomial) diperoleh N̂ :O =
':O ':⦁
Uji Hipotesis
Contoh: 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
:;% O;%
Untuk _ besar, Š akan berdistribusi derajad bebas m(S − 1)
.
dengan
Diperoleh A
99 :;% O;%
':⦁ N‹:O − N$:O N$:O
1/2 1/2
dengan matriks transisi 1/2 1/2 ?
Latihan 1
Contoh: Uji Hipotesis A
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
.
= 86,875
Dengan derajad bebas 2. Diperoleh p-value yang sangat kecil, sehingga ‰$ ditolak.
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,
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:
dengan ∑NO = 1. Hitung distribusi limit [. 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)
