BAB 4 ENTROPI PADA PROSES STOKASTIK RANTAI MARKOV

BAB 4 ENTROPI PADA PROSES STOKASTIK RANTAI MARKOV 4.1

Proses Stokastik

Dalam kehidupan nyata, seringkali orang ingin mengamati keterkaitan satu kejadian dengan kejadian lain dalam suatu interval waktu tertentu, yang merupakan suatu barisan kejadian. Misalnya banyaknya kecelakaan yang terjadi pada ruas jalan yang sama selama 40 hari. Dengan mengetahui kecelakaan hari ini kita dapat memprediksi peluang terjadi kecelakaan esok hari. Hal ini dapat dilakukan dengan proses stokastik. Proses stokastik ini banyak diaplikasikan pada bidang pemasaran (marketing), keuangan dan produksi barang. Proses Stokastik sendiri dapat didefinisikan sebagai berikut. Definisi 4.1 Proses Stokastik { X t , t ∈ T } merupakan barisan peubah acak,yaitu untuk setiap t ∈ T terdapat peubah acak Xt.

Nilai peubah acak Xt dinamakan keadaan (state) pada saat t. Himpunan T disebut ruang parameter atau ruang indeks dari proses stokastik X. Himpunan semua nilai

X ( t ) yang mungkin disebut ruang keadaan dari X.

38

BAB 4 ENTROPI PADA PROSES STOKASTIK RANTAI MARKOV

39

Proses-proses stokastik dapat diklasifikasikan berdasarkan jenis indeks parameter dan ruang keadaannya. 1. Proses Stokastik dengan ruang keadaan diskrit dan indeks parameternya diskrit atau kontinu. 2. Proses Stokastik dengan ruang keadaan kontinu dan indeks parameternya diskrit atau kontinu. Proses stokastik dengan indeks parameter diskrit dikatakan stasioner apabila distribusi gabungan hingga tidak berubah terhadap waktu, dapat dituliskan sebagai

(

)

(

P X t1 +t = x1 ,..., X tm +t = xm = P X t1 = x1 ,..., X tm = xm

)

(4.1)

untuk sebarang m∈ Ν dan semua t, ti ≥ 0 , 1 ≤ i ≤ m .

4.1

Laju Entropi dari Proses Stokastik

Ukuran ketidakpastian, entropi juga dapat diterapkan pada proses stokastik. Entropi ini dapat dilihat sebagai laju entropi dan didefinisikan dengan

Definisi 4.2 : Laju entropi dari suatu proses stokastik, {Xt} adalah H ( X ) = lim

H ( X 1 , X 2 ,..., X t )

t →∞

t

(4.2)

jika limitnya ada atau dapat pula dituliskan sebagai H ( X ) = lim H ( X t X t −1 , X t − 2 ,..., X 1 ) t →∞

(4.3)

Umumnya perhitungan laju entropi diterapkan jika proses stokastik {Xt} stasioner. Untuk {Xt} yang stasioner (saling bebas dan identik), aturan rantai dari entropi menunjukkan t

H ( X ) = lim t →∞

∑H( X ) i

i =1

t

= lim t →∞

tH ( X 1 ) t

= H ( X1 )

(4.4)


4.2

40

Rantai Markov

Sebagaimana telah diutarakan pada Sub Bab 4.1, terdapat klasifikasi dalam proses stokastik, dan salah satunya adalah proses stokastik khusus yang mempunyai ruang keadaan diskrit dan indeks parameternya diskrit yaitu rantai Markov. Contoh dalam kehidupan nyata adalah proses perubahan cuaca, dengan keadaan cuaca hari ini dipengaruhi oleh keadaan cuaca satu hari sebelumnya. Secara matematis, rantai Markov didefinisikan sebagai berikut.

Definisi 4.3 Proses stokastik diskrit {Xt, t=1,2,...,m} disebut rantai Markov jika untuk t>0 berlaku

P ( X t +1 = it +1 | X 1 = i1 ,..., X t −1 = it −1 , X t = it ) = P ( X t +1 = it +1 | X t = it )

(4.5)

Dalam memudahkan penulisan dalam bentuk matriks maka persamaan (4.5) dituliskan

P ( X t +1 = j | X1 = i1 ,..., X t −1 = it −1 , X t = j ) = P ( X t +1 = j | X t = j ) Sehingga

diperoleh

matriks

peluang

transisi

(satu

langkah)

(4.6) dari

{Xt,,t=1,2,...,m}dinotasikan P, adalah suatu matriks dengan elemen ke (i, j)nya adalah peluang transisi,pij. Jadi ⎛ p11 ⎜ p P = ⎜ 21 ⎜ # ⎜ ⎝ pm1

p12

"

p22

"

#

%

pm 2 "

p1m ⎞ ⎟ p2 m ⎟ # ⎟ ⎟ pmm ⎠

Elemen-elemen dari matriks transisi P bernilai non negatif dan jumlah elemenelemen pada setiap barisnya sama dengan satu,

m

∑p j =1

ij

= 1 , untuk setiap i = 1,2...,m.

Definisikan pula qi, peluang awal pada tiap keadaan (state), dengan P(X1=i) = qi. Vektor yang memuat nilai awal dari tiap keadaan, dinamakan distribusi peluang awal, K dengan q = [ q1 , q2 ,..., qt ] .


41

Dalam kasus ini, fmp dari peubah acak-peubah acak tersebut dituliskan sebagai

p ( x1 , x2 ,..., xt ) = p ( x1 ) p ( x2 | x1 ) p ( x3 | x2 ) ... p ( xt | xt −1 )

(4.7)

Sehingga jika pmf dari peubah acak pada waktu t adalah p(xt), maka pmf untuk t+1 adalah

p ( xt +1 ) = ∑ p ( xt ) Pxt xt +1

(4.8)

xt

Definisi 4.4: Rantai Markov dikatakan time invariant atau homogen jika peluang bersyarat p ( xt +1 | xt ) tidak bergantung pada t,

P ( X t +1 = b | X t = a ) = P ( X 2 = b | X 1 = a ) , untuk a,b ∈ X.

(4.9)

Definisi 4.5 : Suatu distribusi peluang pj, j ≥ 1 dikatakan stasioner untuk suatu rantai markov jika ∞

∞

i=2

i =2

P ( X 2 = j ) = ∑ P( X 2 = j X 1 = i ) P( X 1 = i) = ∑ Pj Pij

(4.10)

dengan induksi dapat diperoleh, ∞

∞

i=2

i =2

P ( X t = j ) = ∑ P( X t = j X 1 = i ) P( X 1 = i) = ∑ Pj Pijt

(4.11)

Dengan kata lain, peluang stasioner adalah peluang untuk suatu t → ∞ sehingga terjadinya transisi ke suatu keadaan, baik masuk maupun keluar dari suatu keadaan, nilainya relatif tidak berubah. Jadi, γj merupakan solusi tunggal dari sistem persamaan linear n

γ j = ∑ γ k Pij , j = 1, 2," , n dan i =1

n

∑γ i =1

k

=1

Penjelasan lebih dalam mengenai rantai Markov dapat dilihat pada buku seperti Taylor dan Karlin (1994).


42

Contoh 4.1 untuk rantai Markov orde satu, misalkan suatu barisan DNA. Bagian ini dimulai dari kromosom-X GATCATTGATATGTTGCTAGAACTATGAGTGTTAAAGGTGCTTGTGGTGA GTTATCAGACAGAAACGCAGAAGATGTTATTGGAAGCTTGAGGAAAAGT GATCCTGGATTTACAGTGCCAAGAATTGGCCTGTATTGTGTTCTCAATGTT TTTGAGGAAGGTAGAAACTGTAAGTGATGA

Pada kenyataannya barisan basa DNA ini lebih panjang, hampir mencapai tiga juta barisan. Dalam kasus ini ada empat (4) karakter yaitu basa A, G, C, T. Banyaknya kemunculan basa A pada bagian ini A = 54 kali, C = 19 kali, G = 51 kali, dan T= 56 kali. Dari contoh barisan ini dapat dibuat matriks transisi

Karakter pertama

Karakter kedua C G 5 17 3 1 6 8 5 24 19 50

A 17 7 20 10 54

A C G T Total

T 14 8 17 17 56

Total 53 19 51 56 179

Tabel 4.1 : Frekuensi transisi tiap basa Matriks transisi dapat dibuat menjadi matriks peluang transisi dengan membagi setiap nilai dengan jumlah pada setiap barisnya (frekuensi relatifnya) Karakter kedua A

C

G

T

Karakter

A

0,32075472

0,09434

0,320755

0,264151

pertama

C

0,36842105

0,157895

0,052632

0,421053

G

0,39215686

0,117647

0,156863

0,333333

T

0,17857143

0,089286

0,428571

0,303571

Tabel 4.2 : Peluang transisi tiap basa


43

Terlebih dahulu dihitung taksiran P dan hasilnya 1 ⎛ 0,3207 ⎜ ˆP = 2 ⎜ 0,3684 3 ⎜ 0,3922 ⎜ 4 ⎝ 0,1786

4.3

0, 0943 0,1579 0,1176 0, 0893

0,3208 0, 0526 0,1569 0, 4286

0, 2642 ⎞ ⎟ 0, 4211 ⎟ 0,3333 ⎟ ⎟ 0,3035 ⎠

Entropi pada Rantai Markov

Ukuran entropi juga dapat digunakan pada rantai Markov. Pada tulisan ini dibahas entropi untuk rantai Markov orde 1. Misalkan berada pada keadaan i, peluang pada akan berada di keadaan j, dinotasikan pij, dan ketidakpastian memilih keadaan selanjutnya dapat dilihat sebagai entropi yang didefinisikan sebagai

Hi = −∑ pij log ( pij ) n

(4.12)

j =1

Untuk pij = 0, didefinisikan pij log pij = 0. Nilai Hi adalah entropi keadaan ke i. Apabila rantai Markov stasioner pada keadaan i, yaitu γi, maka entropi state menjadi n

H = ∑ γ i Hi i =1

= −∑ γ i ∑ pij log ( pij ) n

n

i =1

j =1

(0.1)

Ekspresi ini menyatakan rata-rata jumlah bit yang dibutuhkan untuk menyandikan observasi pada state selanjutnya, dan dinamakan entropi (transisi) rantai Markov, dinyatakan dengan H. Jadi jika ditetapkan bahwa matriks transisi ⎛ ⎜ ⎜ P = ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

1 3 1 2 0

1 3 1 2 1 4

1 ⎞ 3 ⎟ ⎟ 0 ⎟ ⎟ ⎟ 3 ⎟ 4 ⎟⎠


44

maka entropi perbaris dari matriks tersebut adalah H1 = 1,5849 , H 2 = 1 , H 3 = 0,8113 . Apabila dibandingkan dengan matriks transisi yang berbentuk ⎛ ⎜ ⎜ P = ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

8 9 1 2 0

1 18 1 2 1 4

1 ⎞ 18 ⎟ ⎟ 0 ⎟ ⎟ ⎟ 3 ⎟ 4 ⎟⎠

entropinya menjadi H1 = 0, 6144 , H 2 = 1 , H 3 = 0,8113 .

Pandang kembali contoh 4.1 mengenai barisan DNA. Dari matriks peluang transisi

ˆ dengan formula pada persamaan (4.13) ini akan dicari taksiran entropi dari, H i dengan basis yang digunakan pada log adalah 2. Hasil yang didapat dengan menggunakan program pada Matlab 7.0 adalah

ˆ = −∑ p log ( p ) = 1,881 , H ˆ = −∑ p log ( p ) = 1, 7001 H 1 1j 1j 2 2j 2j n

n

j =1

j =1

ˆ = −∑ p log ( p ) = 1,8403 , H ˆ = −∑ p log ( p ) = 1,8011 H 3 3j 3j 4 4j 4j n

n

j =1

j =1

Sehingga entropi ini merupakan matriks berukuran 1 x 4 yaitu ˆ = (1,881 1,7001 1,8403 1,8011) H

4.4

Laju Entropi pada Rantai Markov

Pada rantai Markov ini juga dikenal laju entropi sebagai berikut. Definisi 4.6 : Misalkan rantai Markov tidak tereduksi (irreducible) dengan state yang hingga, laju entropi dapat dihitung melalui H ( X ) = lim H ( X t X t −1 , X t − 2 ,..., X 1 ) = H ( X 2 X 1 ) t →∞

(4.14)


45

Rantai Markov yang mempunyai distribusi stasioner, γ dan matriks transisi P, laju entropinya menjadi

H ( X ) = −∑∑ γ i Pij log ( Pij ) t

t

(4.15)

i =1 j =1

Sama seperti contoh kasus di atas, akan dihitung entropi dari distribusi stasioner rantai Markov, π dan taksiran peluang transisi 1 ⎛ 0,3207 ⎜ ˆP = 2 ⎜ 0,3684 3 ⎜ 0,3922 ⎜ 4 ⎝ 0,1786 dengan γ = [0.3014

0.1060

0, 0943 0,1579 0,1176 0, 0893

0,3208 0, 0526 0,1569 0, 4286

0, 2642 ⎞ ⎟ 0, 4211 ⎟ 0,3333 ⎟ ⎟ 0,3035 ⎠

0.2801 0.3125]. Maka dengan memanfaatkan

definisi entropi pada persamaan (2.4) didapat

H ( γ ) = ( 0.5215 0.34321 0.51426 0.5244 ) . Sedangkan laju entropi dari distribusi stasioner dan matriks transisi P diperoleh dengan memasukan nilai-nilai ke persamaan (2.43) sehingga

H ( X ) = −∑∑ γ i Pij log 2 ( Pij ) = 0.15859 4

4

i =1 j =1

BAB 4 ENTROPI PADA PROSES STOKASTIK RANTAI MARKOV

Recommend Documents