Download - 6 Rantai Markovklasifikasi State
6. RANTAI MARKOV WAKTU DISKRIT
KLASIFIKASI RUANG KEADAAN
1
Prostok-6-firda
2
Untuk mempelajari prilaku dari suatu rantai Markov,kita perlu membuat klasifikasi dari ruang keadaan(ruang state) rantai Markov tersebut.
Prostok-6-firda
6.1 Keadaan Accessible (dapat dicapai)
Keadaan j dikatakan accessible (dapat dicapai)dari keadaan i , dinotasikan dengan
3
Pandang suatu rantai Markov, ( ) , 0,1, 2,...X n n
0n 0.nijp
,i jsehinggajika terdapat bilangan bulat
Sudah tentu setiap keadaan dapat dicapai oleh dirinya sendiri, sehingga karena,i i 0 1.iip
Prostok-6-firda
4
1 20
3 31
0 1P
Contoh:
Jika
maka kita katakan keadaan 1 dapat dicapai dari 0
( 0 1)
tapi tidak sebaliknya, keadaan 0 tidak dapat
dicapai dari 1.
0 1
2/3
1/31
karena 101 2 / 3 0.p
Prostok-6-firda
5
Jika i j dan ,j i yaitu terdapat bilangan
bulat 0dan 0m n sehingga 0dan 0,m nij jip p
maka keadaan i dan j dikatakan saling berkomunikasi, dinotasikan, .i j
Contoh: 0 0 1/ 3 2 / 3
1 0 1 0
2 1 0 0
P
Dalam hal ini, 0 22 1 (karena 2 0,0 1) 1 dan 2 tidak saling berkomunikasi.
0 1
2
1/3
2/3
11
Prostok-6-firda
6
Teorema 1(sifat komunikasi kelas rantai Markov)
Komunikasi adalah suatu relasi ekivalen, artinya
(i) i i
(ii) makai j j i
(iii) dan makai j j k i k
Prostok-6-firda
7
Bukti:
(i) dan (ii) jelas berdasarkan definisi.
(iii) Asumsikan terdapat bilangan bulat 0dan 0m n
sehingga 0dan 0,m nij jkp p
maka dengan persamaan Chapman-Kolmogorov diperoleh,
0
0m n m n m nik ij jk ij jk
j
p p p p p
Artinya, .i k Hal serupa berlaku untuk .k iSehingga terbukti .i k
Prostok-6-firda
8
Berdasarkan relasi komunikasi, semua keadaandalam rantai Markov dapat diklasifikasikan kedalam kelas-kelas komunikasi yang terpisah (disjoint) dan lengkap (exhaustive).
Contoh:
01
10P
1. Tentukan kelas komunikasi dari matriks peluang transisi berikut:
Prostok-6-firda
• Diagram transisinya untuk
0 1
1
1
• Kelas komunikasi :
Jawab :
9
{0,1}
01
10P
karena 0 1
Prostok-6-firda
10
2. Jika diberikan matriks peluang transisi
1 0
0 1P
• Diagram transisinya:
101 1
• Kelas komunikasinya:{0} dan {1}.
Maka
Prostok-6-firda
11
3. Jika diberikan matriks peluang transisi 1 0 0
0 1 0
0 0 1
P
• Diagram transisinya:
101 1
• Kelas komunikasinya:{0} , {1}, dan {2}.
Maka
21
Prostok-6-firda
12
4. Jika diberikan matriks peluang transisi
0 1 0 0
1 0 1/ 2 1/ 2
2 1/ 3 1/ 3 1/ 3
P
• Diagram transisinya:
101 1/3
• Kelas komunikasinya:{0} , {1,2}.
Maka
21/2
1/2
1/31/3
Prostok-6-firda
13
5. 0 1/ 4 0 3 / 4 0
1 1/ 2 0 1/ 2 0
2 0 0 1/ 4 3 / 4
3 1 0 0 0
P
• Diagram transisinya:
3
01/4
• Kelas komunikasinya:{0,2,3} , {1}.
Maka
1
1/2
1/4
1/2
3/4
3/4
2
Prostok-6-firda
14
• Jika suatu rantai Markov hanya mempunyai satu kelas komunikasi, maka rantai Markov disebut Irreducible .
Dalam hal ini semua keadaan saling berkomunikasi.
Contoh:0 0 1 0
1 0 0 1
2 1 0 0
P
01
11
1
diagram transisi
Kelas komunikasi : {0,1,2}.
Jadi {0,1,2} rantai Markov Irreducible.
0 1 2 02
15
• Keadaan i dikatakan memiliki perode d(i) jika d(i) merupakan FPB (faktor persekutuan terbesar) / gcd (greatest common divisor) dari seluruh n = 1,2,… dimana
0.niip
• Jika d(i) = 1, maka keadaan i disebut aperiodik.
• Jika d(i) > 1, maka keadaan i disebut periodik.
6.2 Periodisitas
( ) gcd 1| 0niid i n p
Prostok-6-firda
16
Teorema 2
i j Jika maka ( ) ( ).d i d jBukti:
Asumsikan terdapat bilangan bulat 0 dan 0m n sehingga 0dan 0.m n
ij jip p Jika 0 makas
iip 0m n n mjj ji ijp p p
0n s m n s mjj ji ii ijp p p p
Dari definisi periode, d(j) membagi kedua n+m dann+s+m dan juga (n+m)-(n+s+m)=s dengan 0.s
iip
Artinya, d(j) membagi d(i), dan berlaku sebaliknya,d(i) membagi d(j). Jadi d(i)=d(j).
Prostok-6-firda
17
Contoh:
0 0 1/ 2 1/ 2
1 1 0 0
2 1 0 0
P
01
1/2
diagram transisi 1 1/2
1
Tentukan periodisitas dari setiap keadaan.
Jawab:
21210
21210
001
001
001
21210
001
001
212102 PPP
Prostok-6-firda
18
001
001
21210
001
001
21210
21210
21210
00123 PPP
21210
21210
001
21210
21210
001
21210
21210
001224 PPP
• keadaan 0:
001, 0.nn p 2002 1 0n p 4004 1 0n p
00(0) 1| 0nd FPB n p 2, 4,...FPB
(0) 2.d state 0 periodik.
Prostok-6-firda
19
• keadaan 1: periodik
111, 0.nn p 2002 1/ 2n p 4114 1/ 2n p
22(2) 1| 0nd FPB n p
2, 4,...FPB(2) 2.d
• keadaan 2: periodik
221, 0.nn p 2222 1/ 2n p 4224 1/ 2n p
11(1) 1| 0nd FPB n p
2, 4,...FPB(1) 2.d
• Sesuai teorema 2, 0 1,1 2 0 2.
Sehingga, (0) (1) (2).d d d
( (1) 1).d
( (2) 1).d
Prostok-6-firda
20
6.3 Keadaan Recurrent dan Transient
iXnrjrXjnXPf nij 01,...,2,1,,
Didefinisikan
yaitu peluang dimana keadaan j dicapai dari keadaan ipertama kali setelah n langkah.
00 ijf
ijij pf 1
1
21 ...n
ijijn
ijij ffff 1ijij ff
(dalam 0 langkah, keadaan j tidak tercapai dari i)
(dalam 1 langkah ,keadaan j dapat dicapai dari i)
Definisikan,
Prostok-6-firda
21
Definisi 1
Jika 1iif keadaan i disebut recurrent.
keadaan i disebut transient.1iif
Ingat!,
Jika
iif keadaan i dicapai dari keadaan i (kembali dikunjungi)
( ) 1 2
1
...nii ii ii ii
n
f f f f
1,2,…=langkah (bukan pangkat)
Prostok-6-firda
22
Teorema 3
• Keadaan i recurrent jika dan hanya jika1
nii
n
p
(syarat perlu dan cukup keadaan recurrent dan transient)
• Keadaan i transient jika dan hanya jika1
nii
n
p
Prostok-6-firda
23
ContohMatriks peluang transisi suatu rantai Markov,
0 1 0
1 1/ 2 1/ 2P
0 111/2
1/2
Tentukan setiap keadaan apakah recurrent atau transient.
Jawab:
1 0 1 0
1 1/ 2 1/ 2
P P
2 0 1 0 1 0 1 0.
1 1/ 2 1/ 2 1/ 2 1/ 2 3 / 4 1/ 4
P P P
•Jika gunakan teorema 3,
Prostok-6-firda
24
2 1 0 1 0 1 0.
3 / 4 1/ 2 1/ 2 1/ 2 7 / 8 1/ 8
3P P P
Sehingga,
1 2 300 00 00 00
1
... 1 1 1 ... .n
n
p p p p
1 2 311 11 11 11
1
...n
n
p p p p
state 0 recurrent.
state 1 transient.
2 31 1 1
...2 2 2
1/ 21
1 1/ 2
Prostok-6-firda
25
0 11/2
1/2
• Jika dengan definisi 1,
1 2 300 00 00 00 00
1
...n
n
f f f f f
00 001
1.n
n
f f
state 0 recurrent
1 200 00 00 01 101 , 0(1/ 2) 0f p f p p 3 2
00 01 10 01 11 10 0(1/ 2)(1/ 2) 0f p p p p p • • •
00 0 , 2nf n
1
Prostok-6-firda
26
0 1
1/2
1/2
1 2 311 11 11 11 11
1
...n
n
f f f f f
11 111
1/ 2 0 0 ... 1/ 2 1.n
n
f f
State 1 transient.
1 211 11 11 10 011/ 2 , (1/ 2).0 0f p f p p
3 211 10 01 10 00 01 (1/ 2)(1).0 0f p p p p p
• • •
11 0 , 2nf n
1
Prostok-6-firda
27
Teorema 4
Jika keadaan i recurrent dan i jmaka keadaan j recurrent .
Bukti :
Asumsikan terdapat bilangan bulat 0dan 0.m n
ji ijp p sedemikian sehingga0dan 0m n
Maka untuk sebarang 0,s nij
sii
mji
nsmjj pppp
Jika dijumlahkan atas s, diperoleh
yang menyatakan bahwa j recurrent. (terbukti)
28
Akibat:
Suatu rantai Markov yang irreducible memilikiruang keadaan yang recurrent atau transient.
Prostok-6-firda
29
6.4 Keadaan Absorbing (menyerap)
Keadaan i dikatakan Absorbing (menyerap) jika 1.iip
(sekali i dicapai, tidak pernah keluar lagi)
Disebut juga sebagai rantai Markov terserap (absorbing Markov chain) jika paling sedikit terdapat satu keadaan terserap.
Prostok-6-firda
30
Contoh
0 1 0
1 1/ 2 1/ 2
P
Matriks peluang transisi suatu rantai Markov,
Keadaan 0 dikatakan absorbing, karena 00 1.p
Periodisitas keadaan 0 :
001, 0.nn p 1001 1n p 2002 1n p 3003 1n p 4004 1n p
(0) 1, 2,3, 4,...d FPB
(0) 1.d (keadaan 0 aperiodik).
Prostok-6-firda
31
Teorema berikut menunjukkan rantai Markov dapatmembentuk beberapa kelas recurrent dan suatuhimpunan keadaan transient.
Teorema 5
Dari suatu rantai Markov , semua keadaan dapatdiklasifikasikan menjadi beberapa kelas recurrent dan sisanya merupakan keadaan transient. 1 2, , ...C C
Prostok-6-firda
32
Contoh
Tunjukkan rantai Markov dengan peluang transisi berikut memiliki suatu kelas recurrent dan sebuah himpunan keadaan transient.
0 3 / 4 1/ 4 0 0
1 1/ 3 2 / 3 0 0
2 0 0 1/ 2 1/ 2
3 0 1/ 3 1/ 3 1/ 3
P
Prostok-6-firda
33
• Diagram transisinya:
3
0
3/4
• Rantai Markov ini mempunyai kelas recurrent {0,1} dan himpunan state transient {2,3}.
1
1/3
1/3
1/3
2/3
1/3
1/2
1/2
1/4
Prostok-6-firda
34
Contoh :
Diketahui peluang transisi suatu rantai Markov,
0 0 0 1 0
1 0.1 0.8 0 0.1
2 0.4 0.4 0.1 0.1
3 0 0 0.2 0.8
P
a. Tunjukkan bahwa rantai Markov tsb irreducible.
b. Tentukan periodisitas setiap keadaan.
Prostok-6-firda
35
• Diagram transisinya:
3
0
•
1
0.1
0.2
0.8
0.8
0.1
0.1
0.1
0.41 0.4
201 02 210 1, karena (0.1)(0.4) 0p p p
10dan 0.1 0.p
a.
Prostok-6-firda
36
02 200 2, karena 1 0 0.4 0.p dan p •
•
•
• 203 02 230 3, karena (1)(0.1) 0p p p
230 32 20dan (0.2)(0.4) 0.p p p
212 10 021 2, karena (0.1)(1) 0p p p
21dan 0.4 0.p
131 3, karena 0.1 0danp 231 32 21 (0.2)(0.4) 0.p p p
23 322 3, karena 0.1 0dan =0.2>0.p p •
Jadi kelas komunikasinya: {0,1,2,3} rantai Markov irreducible.
Prostok-6-firda
37
b. periodisitas:
• keadaan 0, 001, 0.nn p 200 02 202, 1(0.4) 0n p p p
300 02 22 20 02 21 103, 1(0.1)(0.4) 1(0.4)(0.1) 0n p p p p p p p
400 02 23 32 20 02 22 21 10 02 21 11 104,
1(0.1)(0.2)(0.4) 1(0.1)(0.4)(0.1) 1(0.4)(0.8)(0.1) 0
n p p p p p p p p p p p p p
(0) {2,3, 4,...} 1d FPB Keadaan 0 aperiodik.
Karena 0 1,1 2 , 2 3 3 0
Maka dengan teorema 2, (1) (2) (3) (0)d d d d
Sehingga keadaan 1,2,3 aperiodik. Prostok-6-firda
38
1. Diketahui peluang transisi suatu rantai Markov,
Tentukan klasifikasi semua keadaan (state), yaitu kelas ekivalen, keadaan recurrent, dan transient.
3
0 0.4 0.6 0 0
1 0.2 0.8 0 0.
2 0 0 1 0
3 0 0 0.5 0.5
c
P
2
0 0.2 0.5 0.3
. 1 0 1 0
2 0.9 0.1 0
b
P
1
0 0 1 0
. 1 0 0 1
2 0.5 0.5 0
a
P
Soal Latihan:
Prostok-6-firda
39
2. Diketahui peluang transisi suatu rantai Markov,
0 1/ 4 0 3 / 4 0
1 1/ 2 0 1/ 2 0
2 0 0 1/ 4 3 / 4
3 1 0 0 0
P
Tentukan klasifikasi semua keadaan (state), yaitu kelas ekivalen, keadaan recurrent, dan transient.
Prostok-6-firda
40
3. Diketahui peluang transisi suatu rantai Markov,
(i) Tunjukkan bahwa rantai Markov tersebut irreducible
3
0 0 0 0 0.4 0.6
1 0 0 0 0.2 0.8
. 2 0 0 0 0 1
3 0.5 0.5 0 0 0
4 0 1 0 0 0
c
P
2
0 0 1 0
. 1 0 0 1
2 0.5 0.5 0
b P
(ii) Tentukan periodisitasnya.
1
0 0 1 0
. 1 0 0 1
2 1 0 0
a
P
Prostok-6-firda
41
Limiting Probability
Untuk suatu rantai Markov, semua keadaan recurrent diklasifikasikan menjadi keadaan positif (non-null) recurrent atau null recurrent dengan memperhatikan atau ,denganj j
1
. nj jj
n
n f
menyatakan rata-rata waktu recurrent (mean recurrent time) untuk keadaan j.
Prostok-6-firda
42
Teorema
• Jika keadaan j recurrent dan aperiodic, maka
1, untuk .n
jjj
p n
• Jika keadaan j recurrent dan periodik dengan periode d(j), maka
( ) ( ), untuk .nd j
jjj
d jp n
Kita interpretasikan bahwa 1
0, jika jj
(artinya keadaan j null recurrent).Prostok-6-firda
43
Corollary (Akibat)
Jika keadaan j transient, maka
0, untuk .njjp n
Prostok-6-firda
44
Definisi 5
Misalkan P matriks peluang transisi (m state)dari rantai Markov Homogen.
0 1, , ..., m Maka
Jika 0
dan 1m
jj
P
disebut distribusi stasioner untuk rantai Markov Homogen.
Prostok-6-firda
45
Teorema 8
• Jika suatu rantai Markov Irreducible, positive recurrrent dan aperiodic (Rantai Markov Ergodik) maka terdapat limit peluang,
lim 0 ( , 0,1, 2,...)nij j
np i j
, 0,1, 2,...j j yang bebas dari keadaan awal i, dengan
tunggal dan merupakan solusi
positif dari
0j i ij
i
p
0
1,jj
ini dinamakan distribusi stasioner dari rantai Markov.
dan 0,1, 2,...j
j
Prostok-6-firda
46
Ilustrasi
Misal rantai Markov dengan 3 ruang keadaan, {0,1,2}.
00 01 02
0 1 2 0 1 2 10 11 12
20 21 22
( ) , ,
p p p
i p p p
p p p
Cara menentukan distribusi stasioner 0 1 2, , :
Selesaikan
0 00 0 10 1 20 2p p p
1 01 0 11 1 21 2p p p
2 02 0 12 1 22 2p p p
0 1 2( ) 1ii
0 1 2 1
Atau (i)(ii)(iii)
(iv)
Selesaikansecara simultan
47
Contoh Misal kondisi cuaca (hujan atau tidak hujan) bergantung pada cuaca hari ini (hujan atau tidak hujan).
1. Misalkan , jika hari ini hujan maka besok akan hujan dengan peluang dan jika hari ini tidak hujan, maka besok akan hujan dengan peluang
.
a. Tentukan peluang empat hari ke depan akan hujan jika hari ini hujan. b. Dalam jangka panjang, berapakah proporsi waktu (distribusi stasioner) untuk proses setiap keadaan.
Prostok-6-firda
48
Jawab:
Misalkan keadaan 0 = keadaan hujan. keadaan 1 = keadaan tidak hujan.
Maka matriks peluang transisi untuk masalah tersebut adalah:
0 1
1 1P
0.7 dan 0.3, 0 0.7 0.3
1 0.3 0.7P
Jika
Prostok-6-firda
49
4 0.513 0.487
0.487 0.513P
0 0.7 0.3
1 0.3 0.7P
Jadi, jika hari ini hujan, maka peluang empat hari ke depan akan hujan adalah 0.513 atau 51%.
a.
Prostok-6-firda
50
b. Distribusi stasioner :
Dari matriks peluang transisi0 0.7 0.3
1 0.3 0.7P
diperoleh
0 0 10.7 0.3
1 0 10.3 0.7
0 1 1
… (i)
… (ii)
… (iii)
Dari (i) dan (ii) diperoleh, 0 10.3 0.3
0 1
0 1dan 1P
Prostok-6-firda
51
1 1 1
11 .
2
0 1
1.
2
0 1
1 1, , .
2 2
Jadi, distribusi stasioner:
Substitusikan ke (iii), diperoleh
Artinya untuk jangka panjang, peluang hujan 50%dan tidak hujan 50%.
Prostok-6-firda
52
2. Tentukan distribusi stasioner dari rantai Markov dengan matriks peluang transisi :
0 1/ 2 1/ 2
1 0 0
1 0 0
P
Jawab : 0 1 2dan 1P
0 1 2
1 0
1
2
0 1 2 1
2 0
1
2
… (i)
… (ii)
… (iii)
… (iv)
53
Substitusi (i) ke (iv) :
0 1 2 1
0 0
12 1
2
1 2
1 1,
4 4
Sehingga distribusi stasioner :
0 1 2
1 1 1, , , , .
2 4 4
Artinya untuk jangka panjang, keadaan 0 50%,keadaan 1 25%, dan keadaan 2 25%.
Prostok-6-firda
54
1. Diketahui peluang transisi suatu rantai Markov,
Tentukan distribusi stasioner untuk setiap rantai Markov tersebut.
3
0 1.
1 0c
P
2
1/ 2 1/ 2.
1/ 2 1/ 2b
P
1
2 / 3 1/ 3.
1/ 3 2 / 3a
P
Soal Latihan:
4
0 0 1 0
. 1 0 0 1
2 0.5 0.5 0
d P
Prostok-6-firda