DR. Rahma Fitriani, S.Si., M.Sc

Proses Stokastik

Semester Ganjil 2013

The Long Run Behaviour of Markov Chains Menganalisis peluang transisi n langkah dari rantai

markov untuk n → ∞: The Limiting Probability Distribution Tidak tergantung pada state awal

Peluang transisi n langkah tersebut ada jika rantai markov mempunyai matriks peluang yang bersifat regular Semua elemen Pk >0

NjforP jn

ijn

,,1,0 ,0)(lim

NjforiXjX jnn

,,1,0 ,0Pr 0lim

Apapun state awalnya (initial state) rantai markov akan berakhir di state j dengan peluang πj

Contoh: Rantai Markov dua State

25.075.067.033.0

10

1 0P

1,0 ,1

110

1 0

babb

aaP

baa

bab

baa

bab

Pn

nlim

528169.075.067.0

75.0

bab

471831.0528169.0471831.0528169.0

lim n

nP

471831.075.067.0

67.0

baa

P dengan beberapa pangkat:

565.0435.0

3886.06114.010

1 02P

488266.0511734.0457149.0542851.0

10

1 04P

472342.0527658.0471374.0528626.0

10

1 08P

471831.0528169.0471831.0528169.0

10

1 016P

π0 π1

471831.0528169.0π

Syarat Keberadaan the Limiting probability Rantai markov mempunya matriks peluang

transisi yang bersifat regular Matriks peluang transisi bersifat regular jika:

Setiap pasang state i, j, terdapat jalur k1, k2, …, kr di mana Pik1

P k1k2 ... Pkrj>0

Terdapat paling sedikit satu i di mana Pii>0

The Limiting Probability Distribution Jika P matriks peluang transisi yang bersifat regular di

mana terdapat 0, 1, 2, …, N, kemungkinan state, maka: The limiting probability distribution =(0, 1, 2, …,N)

adalah solusi unik dari persamaan:

= P

1i

i

Contoh Untuk rantai markov dengan matriks peluang transisi

berikut ini:

45.050.005.025.070.005.010.050.040.0

210

2 1 0

P

Tentukan the limiting probability distribution. Sistem persamaan: πPπ

45.050.05.025.070.005.010.05.040.0

210210

1i

i

1210

45.050.005.025.070.005.010.05.040.0

210210

(4) 1210

)1( 05.005.04.0 2100

(2) 5.07.05.0 2101

(3) 45.025.01.0 2102

Karena adanya batasan linier, maka satu persamaan bersifat redundan dan akan dibuang dari sistem persamaan-Pada kasus ini persamaan 3 yang dibuang

(4) 1210

)1( 5.005.04.0 2100

(2) 5.07.05.0 2101

005.005.06.0 210

005.03.05.0 210

298077.010431,625.0

85,07692.0

131

210

Dengan substitusi dan eliminasi, solusinya adalah:

Berdasarkan definisi dari the limiting probability:

NjforP jn

ijn

,,1,0 ,0)(lim

298077.0625.0076923.0298077.0625.0076923.0298077.0625.0076923.0

210

2 1 0

P16

Dengan mengoperasikan pangkat tinggi pada matriks peluang transisi:

π0 π1 π2

Klasifikasi State-State Definisi:

State j dapat dijangkau (reachable) dari state i jika peluang untuk menuju dari i ke j dalam n >0 langkah adalah positif (Jika teradapat jalur dari i ke j pada diagram rantai markov).

Himpunan bagian S dari himpunan state X bersifat tertutup (closed) jika pij=0 untuk setiap iS and j S

Statei dikatakan absorbing jika terdapat closed set dengan satu anggota (state) saja.

Himpunan tertutup (closed set) S dikatakan irreducible jika sembarang state jS dapat dijangkau dari setiap state iS.

Rantai markov dikatakan irreducible jika himpunan state-nya X adalah irreducible.

Contoh

Irreducible Markov Chain

0 1 2

p01 p12

p00p10

p21

p22

Reducible Markov Chain p01 p12

p00p10

p14

p224

p23

p32

p33

0 1 2 3

Absorbing State

Closed irreducible set

Transient and Recurrent States Hitting Time Recurrence Time Tii adalah waktu yang

dibutuhkan untuk state i kembali ke state i untuk pertama kalinya

Diberikan ρi sebagai peluang bahwa state akan kembali ke i dengan syarat rantai markov berawal di state i, maka,

0min 0 : ,ij kT k X i X j

State i recurrent jia ρi=1 dan transient jika ρi<1

State i bersifat transient jika terdapat peluang bahwa rantai markov tidak akan kembali ke state i.

Teorema-teorema Jika rantai markov mempunyai himpunan state

yang finite, maka paling sedikit satu dari state-nya bersifat recurrent.

Jika i adalah state yang bersifat recurrent dan state j dapat dijangkau dari state i maka state j juga recurrent.

Jika S adalah himpunan state yang irreducible yang finite dan closed, maka setiap state di S adalah recurrent.

Positive and Null Recurrent States Diberikan Mi sebagai rata-rata waktu recurrence

bagi state i

State i dikatakan positive recurrent jika Mi<∞. Jika Mi=∞ maka state tersebut dikatakan null-recurrent.

1

Pri ii iik

M E T k T k

Example

p01 p12

p00p10

p14

p224

p23

p32

p33

0 1 2 3

Recurrent State

Transient States Positive

Recurrent States

17

Klasifikasi State-State

j

recurrent transient

positive

non-absorbingabsorbing

null

State Periodic dan Aperiodic Misalkan bahwa struktur rantai markov adalah

sedemikian sehingga terdapat beberapa jalur dari state i kembali ke state i, di mana jumlah langkah dari setiap jalur adalah kelipatan bilangan bulat d >1 state i disebut periodic dengan periode d.

Jika tidak terdapat bilangan bulat sedemikian (d =1) maka state tersebut bersifat aperiodic.

Contoh: 1 0.5

0.5

0 1 2

1

Periodic State d = 2

0 1 00.5 0 0.50 1 0

P