BAB IV APLIKASI PADA MATRIKS STOKASTIK

BAB IV : APLIKASI PADA MATRIKS STOKASTIK

BAB IV APLIKASI PADA MATRIKS STOKASTIK Salah satu aplikasi dari Teori Perron-Frobenius yang paling terkenal adalah penurunan secara aljabar untuk beberapa sifat yang dimiliki oleh matriks stokastik. Penurunan sifat matriks stokastik ini lebih dikhusukan untuk matriks stokastik berdasarkan teori rantai Markov diskrit. Pada bab ini akan difokuskan aplikasi Teori Perron-Frobenius dalam mencari distribusi limit dari rantai Markov tersebut.

4.1

Matriks Stokastik dan Rantai Markov Matriks persegi nonnegatif disebut stokastik baris, yaitu jika jumlah pada setiap barisnya adalah satu. Secara umum, stokastik baris ini cukup disebut dengan stokastik. Matriks stokastik kolom sendiri didefinisikan serupa, yaitu jika jumlah pada setiap kolomnya adalah satu.. Namun, pada pembahasan tugas akhir ini dibatasi hanya untuk kasus matriks stokastik (baris).

Matriks stokastik berperan penting dalam teori rantai Markov yang merupakan bagian dari proses stokastik. Proses stokastik itu sendiri didefinisikan sebagai barisan peubah acak

{ X t , t ∈T} ,

yaitu untuk setiap t ∈ T kita mempunyai

Teori Perron-Frobenius untuk Matriks Stokastik Madona Yunita (10103035)

56


peubah acak X t . Seringkali kita menginterpretasikan indeks t sebagai waktu, karena banyak sekali proses stokatik yang terjadi pada suatu selang waktu. Nilai peubah acak X t disebut dengan keadaan pada saat t . Himpunan T disebut ruang parameter atau ruang indeks dari proses stokastik dan himpunan semua nilai X t yang mungkin disebut dengan ruang keadaan (state). Proses stokastik dengan ruang parameter diskrit dan ruang keadaan diskrit ini dikenal dengan rantai Markov. Rantai Markov ini memiliki sifat khusus, yaitu

(

)

(

P X t +1 = S j / X t = Sit , X t −1 = Sit −1 ,....., X 0 = Si0 = P X t +1 = S j / X t = Sit untuk

setiap t = 0,1, 2.... , dengan ruang keadaannya adalah

)

{S1 , S2 ,...., Sn } .

Sifat khusus tersebut menyatakan bahwa prosesnya bersifat memoryless, yaitu peluang kejadian pada periode berikutnya hanya dipengaruhi periode saat ini sedangkan periode sebelumnya tidak memiliki pengaruh apapun.

Rantai Markov dapat dinyatakan dengan menggunakan matriks stokastik. Untuk membuktikan hal tersebut, perhatikan bahwa nilai pij = P ( X t = S j / X t −1 = Si ) adalah peluang berada di state S j pada periode ke- t diberikan bahwa pada periode ke- ( t − 1) berada di states Si . Nilai pij disebut dengan peluang transisi dari state Si ke state S j pada periode ke- t . Matriks peluang transisi Pn×n ( t ) = ⎡⎣ pij ( t ) ⎤⎦ merupakan matriks nonnegatif dan jumlah dari elemen pada

setiap barisnya pasti bernilai satu, sehingga P ( t ) adalah matriks stokastik. Jika, peluang transisi tidak bergantung pada waktu (yaitu pij ( t ) = pij untuk setiap t ), maka rantai tersebut dikatakan stasioner atau homogen dan matriks transisinya adalah matriks stokastik konstan P = ⎡⎣ pij ⎤⎦ .


57


Selanjutnya, akan disajikan beberapa teorema yang menunjukkan sifat matriks stokastik. Pada teorema berikut ini diberikan nilai spectral radius untuk matriks stokastik. Teorema 4.1 Misalkan Pn×n adalah matriks stokastik, maka ρ ( P ) = 1 .

Bukti. Matriks Pn×n adalah matriks dengan jumlah elemen pada setiap barisnya adalah satu atau P

∞

= 1 atau secara ekivalen, Pe = e , dimana e adalah vektor

dengan elemennya bernilai satu. Karena (1, e ) adalah pasangan karakteristik untuk setiap matriks stokastik dan karena ρ ( ∗) ≤ ∗ untuk setiap norm matriks, maka 1 ≤ ρ ( P ) ≤ P

∞

= 1 ⇒ ρ (P) = 1.

Lebih jauh lagi, e adalah vektor karakteristik positif yang berkorespondensi dengan ρ ( P ) = 1 . Namun, hal ini bukan berarti bahwa e adalah vektor Perron untuk P karena P bisa tidak tak tereduksi. Sebagai contoh, perhatikan matriks ⎛ 0.5 0.5 ⎞ P=⎜ ⎟ . Matriks P tidak tak tereduksi dan e bukan vektor Perron 1 ⎠ ⎝ 0 untuk P .

4.2

Vektor Distribusi Peluang Vektor

distribusi

peluang

pT = ( p1 , p2 ,..., pn ) dimana

didefinisikan

n

∑p j =1

j

sebagai

vektor

nonnegatif

= 1 . Untuk Rantai Markov dengan n buah

state, vektor distribusi peluang langkah ke- k didefinisikan sebagai

pT ( k ) = ( p1 ( k ) , p2 ( k ) ,..., pn ( k ) ) , k = 0,1, 2,... , dimana p j ( k ) = P ( X k = S j ) . Dengan kata lain, p j ( k ) adalah peluang berada di state S j setelah k buah langkah tetapi sebelum langkah ke-( k + 1 ). Vektor distribusi awal adalah


58


pT ( 0 ) = ( p1 ( 0 ) , p2 ( 0 ) ,..., pn ( 0 ) ) , dimana p j ( 0 ) = P ( X 0 = S j ) , yaitu peluang bahwa rantai dimulai dari state S j .

Langkah ke- k dari distribusi dapat diuraikan dengan menggunakan teori peluang. Kita tahu bahwa P ( E ∪ F ) = P ( E ) + P ( F ) jika E dan F kejadian yang saling bebas. Peluang bersyarat E jika diberikan kejadian F adalah

P ( E \ F ) = P ( E ∩ F ) / P ( F ) . Untuk menentukan komponen ke- j , yaitu

p j (1) pada pT (1) diberikan pT ( 0 ) , tulis p j (1) = P ( X 1 = S j ) = P ⎡⎣ X 1 = S j ∩ ( X 0 = S1 ∪ X 0 = S 2 ∪ .... ∪ X 0 = Sn ) ⎤⎦

= P ⎡⎣( X 1 = S j ∩ X 0 = S1 ) ∪ ( X 1 = S j ∩ X 0 = S 2 ) ∪ ..... ∪ ( X 1 = S j ∩ X 0 = S n ) ⎤⎦ = ∑ P ⎡⎣( X 1 = S j ∩ X 0 = Si ) ⎤⎦ n

i =1

= ∑ P ⎡⎣( X 0 = Si ) ⎤⎦ P ⎡⎣( X 1 = S j / X 0 = Si ) ⎤⎦ n

i =1 n

= ∑ pi ( 0 ) pij , untuk setiap j = 1, 2,..., n i =1

Akibatnya, pT (1) = pT ( 0 ) P . Hal ini menunjukkan bahwa distribusi yang terjadi satu langkah selanjutnya setelah kita mulai dengan pT ( 0 ) . Namun, sifat khusus memoryless pada rantai Markov menyatakan bahwa kejadian pada langkah ke- k hanya bergantung kejadian pada langkah ke- ( k − 1) . Akibatnya

pT ( 2 ) = pT (1) P ,

pT ( 3) = pT ( 2 ) P , dan seterusnya. Dengan melakukan

subtitusi, kita bisa memperoleh

pT ( k ) = pT ( k − 1) P = pT ( k − 2 ) P 2 = ..... = pT ( 0 ) P k . Jadi, distribusi pada langkah ke- k tersebut ditentukan dari distribusi awal dan matriks transisi dari hasil kali vektor-matriks adalah

p T ( k ) = pT ( 0 ) P k .


(4.1)

59

BAB IV : APLIKASI PADA MATRIKS STOKASTIK k Misalkan P k = ⎡⎣ pij( ) ⎤⎦ dan jika kita tuliskan pT ( 0 ) = eTi untuk (4.1), maka kita

peroleh p j ( k ) = pij( k ) untuk setiap i = 1, 2,..., n . Dengan demikian, kita peroleh kesimpulan bahwa elemen ke- ( i, j ) dari matriks P k adalah peluang transisi dari state Si ke state S j dengan tepat k langkah. Oleh karena itu, P k biasa disebut dengan matriks transisi langkah ke- k .

4.3

Distribusi Limit dari Rantai Markov

Dalam menganalisis limit dari rantai Markov, kita dapat membagi matriks stokastik menjadi dua bagian berdasarkan sifat tereduksinya, yaitu matriks stokastik tak tereduksi dan matriks stokastik tereduksi. Untuk matriks stokastik tak tereduksi, kita bisa melihat kasus dimana lim P k ada (yaitu P primitif) dan k →∞

lim P k tidak ada (yaitu P imprimitif). Begitu pula untuk matriks stokastik k →∞

tereduksi, kita bisa melihat kasus dimana lim P k ada dan lim P k tidak ada. k →∞

k →∞

4.3.1 Distribusi Limit dari Matriks Stokastik Tak Tereduksi

Untuk kasus matriks stokastik tak tereduksi, kita bisa membaginya menjadi dua bagian, yaitu matriks primitif dan matriks imprimitif. Jika P adalah matriks primitif, maka kita tahu bahwa nilai dari

lim P k ada. k →∞

Vektor Perron untuk P adalah e / n , yaitu vektor distribusi seragam. Misalkan π = (π 1 , π 2 ,...., π n ) adalah vektor Perron untuk P T , maka T

⎡π 1 π 2 ( e / n ) π = eπ = eπ T = ⎢⎢π1 π 2 lim P k = T k →∞ ⎢ π (e / n) π T e ⎢ ⎣π 1 π 2 T

T

πn ⎤ π n ⎥⎥ ⎥ ⎥ πn ⎦

>0

(4.2)

berdasarkan Teorema 3.19. Oleh karena itu, jika P primitif maka distribusi limit peluangnya ada dan diberikan oleh


60


lim pT ( k ) = lim pT ( 0 ) P k = pT ( 0 ) eπ T = π T . k →∞

(4.3)

k →∞

Selanjutnya, jika P adalah matriks imprimitif, kita tahu bahwa terdapat

h > 1 buah nilai karakteristik pada lingkaran spektral dan lim P k tidak ada k →∞

(Definisi 3.18 dan Teorema 3.19). Akibatnya, lim pT ( k ) juga tidak ada. k →∞

Dalam statistika, lim P k ini tidak ada disebabkan oleh setiap state pada k →∞

rantai Markov bersifat periodik, yaitu untu periode lebih besar dari satu, suatu state akan kembali pada state yang sama. Akibatnya, nilai lim P k k →∞

akan konvergen ke suatu bentuk tertentu untuk k ganjil dan akan konvergen ke suatu bentuk yang berbeda untuk k genap. Namun, pada tugas akhir ini pembahasan mengenai bentuk lim P k tersebut tidak akan k →∞

dibahas. Kita akan melihat bentuk limit yang lain dari matriks transisi ini.

Kita tahu bahwa setiap nilai karakteristik pada lingkaran satuan adalah simple berdasarkan Teorema 3.22, artinya P adalah Cesaro Summable dari Teorema 3.23. Akibatnya jika e / n adalah vektor Perron untuk P maka terdapat vektor Perron kiri, sebut π = (π 1 , π 2 ,...., π n ) , sehingga T

lim

k →∞

+ P k −1

I+P+ k

⎡π 1 π 2 ⎢π π e / n)π ( eπ T 2 T = T = T = eπ = ⎢ 1 ⎢ π (e / n) π e ⎢ ⎣π 1 π 2 T

πn ⎤ π n ⎥⎥ ⎥ ⎥ πn ⎦

>0

yang mempunyai nilai limit yang sama pada (4.2) untuk kasus primitif. Jadi, distribusi peluang langkah ke- k mempunyai limit Cesaro yang diberikan oleh


61


⎡ pT ( 0 ) + pT (1) + lim ⎢ k →∞ k ⎣

+ pT ( k − 1) ⎤ ⎥= ⎦

⎡ I + P + + P k −1 ⎤ = pT ( 0 ) eπ T = π T lim p ( 0 ) ⎢ ⎥ k →∞ k ⎣ ⎦ T

yang memiliki bentuk yang sama dengan kasus primitif pada (4.3). Limit Cesaro ini tidak bergantung pada distribusi awal sama halnya untuk kasus ketika limitnya ada.

Selanjutnya, kita akan menginterpretasikan maksud dari limit Cesaro ini. Caranya adalah dengan memfokuskan pada salah satu state, sebut S j . Kemudian, kita definisikan sebuah barisan peubah acak

{ Z k }k = 0 ∞

yang

menyatakan jumlah kunjungan ke state S j . Misal, ⎧1, jika rantai dimulai dari state S j Z0 = ⎨ lainnya ⎩0, dan untuk i > 1 , ⎧ 1, Zi = ⎨ ⎩0,

jika rantai berada di state S j setelah langkah ke - i lainnya

Perhatikan bahwa Z 0 + Z1 + .... + Z k −1 adalah jumlah kunjungan ke state S j sebelum langkah ke- k , maka ( Z 0 + Z1 + .... + Z k −1 ) / k menyatakan fraksi dari waktu untuk sampai di S j sebelum langkah ke- k . Nilai ekspetasi dari Z i adalah

E [ Zi ] = 1.P ( Zi = 1) + 0.P ( Zi = 0 ) = P ( Zi = 1) = p j ( i ) . Karena ekspetasi bersifat linear, maka ekspetasi dari waktu berada di S j sebelum langkah ke- k adalah


62


⎡ Z + Z1 + .... + Z k −1 ⎤ E [ Z 0 ] + E [ Z1 ] + .... + E [ Z k −1 ] E⎢ 0 ⎥= k k ⎣ ⎦ =

p j ( 0 ) + p j (1) + .... + p j ( k − 1) k

⎡ pT ( 0 ) + pT (1) + .... + pT ( k − 1) ⎤ =⎢ ⎥ →π j k ⎣ ⎦j

Dengan kata lain, fraksi waktu untuk kurun waktu yang cukup lama yang dihabiskan di state S j adalah π j , yaitu komponen ke- j dari limit Cesaro atau komponen ke- j dari vektor Perron kiri P . Ketika lim pT ( k ) ada, maka k →∞

⎡ pT ( 0 ) + pT (1) + lim p ( k ) = lim ⎢ k →∞ k →∞ k ⎣ T

+ pT ( k − 1) ⎤ ⎥. ⎦

Jadi, interpretasi dari distribusi limit, lim pT ( k ) , untuk kasus matriks k →∞

primitif akan sama halnya dengan interpretasi dari limit Cesaro untuk kasus matriks imprimitif.

Berikut ini adalah ringkasan mengenai sifat-sifat yang dimiliki oleh rantai Markov tak tereduksi.

Teorema 4.2 Misal P adalah matriks peluang transisi untuk rantai

Markov tak tereduksi dengan state {S1 , S2 ,..., Sn } , yaitu P adalah matriks stokastik tak tereduksi berukuran n × n . Misalkan pula π T adalah vektor Perron kiri untuk P . Pernyataan berikut benar untuk setiap vektor distribusi awal pT ( 0 ) . (a).

Matriks transisi langkah ke- k adalah P k karena elemen ke- ( i, j ) dari P k adalah peluang transisi dari state S j ke state Si dalam k langkah.


63


(b).

Vektor distribusi langkah ke- k diberikan oleh pT ( k ) = pT ( 0 ) P k .

(c).

Jika P primitif dan jika e adalah vektor dengan elemennya bernilai satu maka lim P k = eπ T

dan

k →∞

(d).

k →∞

Jika P imprimitif, maka lim

+ P k −1

I+P+

k →∞

k

⎡ pT ( 0 ) + pT (1) + lim ⎢ k →∞ k ⎣ (e).

lim pT ( k ) = π T .

= eπ T

dan

+ pT ( k − 1) ⎤ T ⎥ =π . ⎦

Tanpa memperhatikan P primitif ataupun imprimitif, elemen ke-

j , yaitu π j , pada π T menyatakan fraksi waktu untuk kurun waktu yang cukup lama bahwa rantai berada di state S j . (f).

Vektor π T biasa disebut dengan vektor distribusi stasioner untuk rantai karena vektor distribusi ini tunggal yang memenuhi

πTP = πT . 4.3.2 Distribusi Limit dari Matriks Stokastik Tereduksi Karena Teorema Perron-Frobenius tidak secara langsung dapat dipakai untuk rantai Markov tereduksi (rantai untuk matriks P tereduksi), strateginya adalah dengan melakukan manipulasi untuk matriks tereduksi tersebut.

Jika P tereduksi maka terdapat matriks permutasi Q dan matriks persegi ⎡X Y⎤ X dan Z sehingga Q T PQ = ⎢ ⎥ . Untuk mempermudah penulisan, ⎣ 0 Z⎦ ⎡X Y⎤ kita notasikan dengan P ~ ⎢ ⎥ . Jika X atau Z tereduksi, maka 0 Z ⎣ ⎦ permutasi simetri lainnya bisa diperoleh untuk menghasilkan


64


⎡R S T ⎤ ⎡X Y⎤ ⎥ ⎢ ⎢ 0 Z ⎥ ~ ⎢ 0 U V ⎥ , dimana R , U , dan W adalah matriks ⎣ ⎦ ⎢⎣ 0 0 W ⎥⎦ persegi. Dengan mengulang proses yang sama sehingga dihasilkan ⎡ X11 ⎢X P ~ ⎢ 21 ⎢ ⎢ ⎣ 0

X12 … X1k ⎤ X 22 … X 2 k ⎥⎥ , ⎥ ⎥ 0 … X kk ⎦

dimana setiap Xii tak tereduksi atau Xii = [ 0]1×1 . Jika terdapat baris dengan elemen tak nol hanya terdapat pada blok diagonal, maka permutasikan secara simetris semua baris ke bagian bawah sehingga diperoleh ⎡ P11 ⎢0 ⎢ ⎢ ⎢ 0 P ~ ⎢ ⎢0 ⎢ ⎢0 ⎢ ⎢ ⎢⎣ 0

P12

P1r

P1,r +1

P1, r + 2

P22

P2 r

P2,r +1

P2,r + 2

0

Prr

Pr , r +1

Pr ,r + 2

0 0

0 0

Pr +1,r +1 0

0 Pr + 2,r + 2

0

0

0

0

P1m ⎤ P2 m ⎥⎥ ⎥ ⎥ Prm ⎥ 0 ⎥ ⎥ 0 ⎥ ⎥ ⎥ Pmm ⎥⎦

(4.4)

dimana setiap P11 ,..., Prr tak tereduksi atau [ 0]1×1 , dan Pr +1,r +1 ,..., Pmm tak tereduksi (setiap bloknya tidak mungkin nol karena setiap barisnya harus berjumlah 1).

Seperti yang telah disebutkan dalam bab sebelumnya pada Definisi 3.9, efek dari permutasi simetri adalah mengubah posisi titik pada G ( P ) atau pada rantai Markov. Ketika state dalam rantai diubah posisinya sehingga

P memiliki bentuk seperti (4.4), kita sebut P dalam bentuk cannonical untuk matriks tereduksi. Ketika P dalam bentuk cannonical, subset dari


65


state yang berkorespondensi dengan Pkk untuk 1 ≤ k ≤ r disebut dengan kelas transien ke- k (karena ketika kita keluar dari state tersebut, maka kelas transien ini tidak dapat dimasuki kembali) sedangkan subset dari

state yang berkorespondensi dengan Pr + j ,r + j untuk j ≥ 1 disebut dengan kelas ergodik ke- j . Setiap kelas ergodik adalah rantai Markov tak tereduksi yang kembali ke state dirinya sendiri yang berada pada rantai tereduksi berukuran besar. Untuk selanjutnya, kita akan mengasumsikan bahwa state dalam rantai tereduksi telah diurutkan atau diubah sehingga

P dalam bentuk cannonical. Matriks stokastik P yang berada dalam bentuk cannonical tersebut akan dinotasikan dengan P .

Pada bab sebelumnya dinyatakan bahwa jika P matriks stokastik tak tereduksi mempunya h buah nilai karakteristik pada lingkaran satuannya maka h buah nilai karakteristik ini adalah akar ke- h dan setiap akarnya adalah nilai karakteristik simple untuk P . Hal yang sama tidak bisa dikatakan untuk matriks stokastik tereduksi, tetapi dengan bentuk

cannonical (4.4) bisa berlaku seperti pada teorema berikut ini.

Teorema 4.3 Nilai karakteristik satuan untuk matriks stokastik

didefinisikan sebagai nilai karakteristik pada lingkaran satuan. Untuk setiap matriks stokastik Pn×n , pernyataan berikut benar.

Setiap nilai karakteristik satuan dari P adalah semisimple.

Setiap nilai karakteristik satuan mempunyai bentuk λ = e 2 kπ i / h untuk suatu k < h ≤ n .

Bukti. Jika P tak tereduksi maka hal ini telah dibuktikan pada Teorema 3.22. Jika P tereduksi, misalkan terdapat permutasi simetri sehingga P berada dalam bentuk cannonical seperti pada (4.4)


maka ρ ( Pkk ) < 1

66


untuk setiap k = 1, 2,..., r . Hal ini berlaku jika Pkk = [ 0]1×1 . Perhatikan untuk Pkk (1 ≤ k ≤ r ) tak tereduksi. Karena pasti terdapat blok Pkj , k ≠ j yang mempunyai elemen tak nol, maka Pkk e ≤ e dan Pkk e ≠ e dimana e adalah vektor dengan elemennya bernilai 1. Jika ρ ( Pkk ) = 1 , maka hal ini akan membuat Pkk e = e berdasarkan Teorema 3.20 (kontradiksi). Jadi haruslah

ρ ( Pkk ) < 1 untuk setiap k = 1, 2,..., r .

(4.5)

Akibatnya, nilai karakteristik satuan untuk P adalah koleksi atau kumpulan dari nilai karakteristik satuan dari matriks tak tereduksi

Pr +1,r +1 ,..., Pmm . Namun, setiap nilai karakteristik dari Pr +i ,r +i adalah simple dan merupakan akar semesta (Teorema 3.22). Akibanya, jika λ adalah nilai karakteristik satuan untuk P maka λ pasti merupakan suatu akar semesta. Walaupun nilai λ bisa muncul lebih dari satu kali karena λ muncul lebih dari satu Pr +i ,r +i , hal ini pasti merupakan kasus dimana

ma ( λ ) = mg ( λ ) . Jadi, λ adalah nilai karakteristik semisimple untuk P .

Untuk mencari bentuk distribusi limit dari rantai Markov tereduksi maka kita asumsikan bahwa P berada dalam bentuk cannonical (4.4). Namun sebelumnya, kita akan membuktikan terlebih dahulu bahwa setiap matriks stokastik bersifat Cesaro Summable (Teorema 2.28).

Teorema 4.4 Setiap matriks stokastik adalah Cesaro Summable, yaitu I + P + .... + P k −1 ada. k →∞ k

lim


67


Nilai dari limitnya adalah proyektor G pada N ( I − P ) sepanjang

R (I − P) .

Bukti. Bentuk dan interpretasi dari Cesaro Summable untuk P matriks tak tereduksi telah dibuktikan sebelumnya. Jadi, kita hanya perlu membuktikan untuk kasus P adalah matriks tereduksi. Misalkan ⎛T P = ⎜ 11 ⎝ 0

T12 ⎞ ⎟ bentuk cannonical (4.4), dimana T22 ⎠

⎛ P1,r +1 … P1m ⎞ ⎛ P11 … P1r ⎞ ⎜ ⎟ ⎜ ⎟ T11 = ⎜ ⎟ , dan ⎟ , T12 = ⎜ ⎜ ⎟ ⎜ ⎟ Prr ⎠ ⎝ ⎝ Pr , r +1 … Prm ⎠ ⎛ Pr +1,r +1 ⎞ ⎜ ⎟ T12 = ⎜ ⎟ ⎜ ⎟ P mm ⎠ ⎝

(4.6)

Kita tahu dari (4.5) bahwa ρ ( Pkk ) < 1 untuk setiap k = 1, 2,..., r , sehingga

ρ ( T11 ) < 1 . Akibatnya, lim

I + T11 + .... + T11k −1

k →∞

= lim T11k = 0 . k →∞

k

Selanjutnya, masing-masing dari Pr +1,r +1 ,..., Pmm adalah matriks stokastik tak tereduksi, maka jika π Tj

adalah vektor Perron kiri untuk Pjj ,

r + 1 ≤ j ≤ m , maka berdasarkan hasil sebelumnya pada (4.2) kita peroleh

lim

I + T22 + .... + T22k −1

k →∞

k

⎛ eπ rT+1 ⎜ =⎜ ⎜ ⎝

⎞ ⎟ ⎟ = E. eπ mT ⎟⎠

Lebih jauh lagi, jelas berdasarkan Teorema 3.19 bahwa lim T22k ada jika k →∞

dan hanya jika masing-masing dari Pr +1,r +1 ,..., Pmm adalah primitif. Dalam hal ini, lim T22k = E . k →∞


68


Oleh karena itu, semua limitnya (baik untuk limit Cesaro ataupun limit biasa) akan berbentuk

I + P + .... + P lim k →∞ k

k −1

k ⎛0 Z⎞ P (jika ada). =⎜ ⎟ = G = lim k →∞ ⎝0 E⎠

Untuk menentukan bentuk dari Z , kita akan menggunakan fakta bahwa

(

R (G ) = N I − P

)

(

)

(karena G adalah proyektor pada N I − P ) untuk

menuliskan

(I − P ) G = 0

⎛ I − T11 ⇒ ⎜ ⎝ 0

−T12 ⎞ ⎛ 0 Z ⎞ =0 ⇒ ⎟ I − T22 ⎠ ⎜⎝ 0 E ⎟⎠

( I − T11 ) Z = T12E .

Karena I − T11 adalah matriks nonsingular ( karena ρ ( T11 ) < 1 ), akibatnya Z = ( I − T11 ) T12 E . −1

Berikut ini adalah ringkasan mengenai sifat-sifat yang dimiliki oleh rantai Markov tereduksi.

Teorema 4.5 Misalkan state pada rantai Markov tereduksi telah diurutkan sedemikian rupa sehingga matriks transisi berada dalam bentuk cannonical ⎛T P = ⎜ 11 ⎝ 0

T12 ⎞ ⎟ T22 ⎠

seperti pada (4.4) dan (4.6). Misalkan pula π Tj adalah vektor Perron kiri untuk Pjj ( r + 1 ≤ j ≤ m ) , maka I − T11 nonsingular dan I + P + .... + P lim k →∞ k

k −1

⎛0 =⎜ ⎜0 ⎝

⎛ eπ rT+1 T12 E ⎞ ⎜ ⎟⎟ , dimana E = ⎜ E ⎠ ⎜ ⎝

( I − T11 )


−1

⎞ ⎟. ⎟ eπ mT ⎟⎠

69

BAB IV : APLIKASI PADA MATRIKS STOKASTIK k

Lebih jauh lagi, lim P ada jika dan hanya jika masing-masing dari k →∞

Pr +1,r +1 ,..., Pmm adalah primitif. Dalam hal ini, ⎛0 lim P = ⎜ ⎜0 k →∞ ⎝ k

( I − T11 )

T12 E ⎞ ⎟⎟ . E ⎠ −1

Berdasarkan Teorema 4.5, kita bisa menyimpulkan bahwa setiap rantai Markov tereduksi pada akhirnya akan terabsorpsi (terperangkap) pada salah satu dari kelas-kelas ergodik, yaitu pada salah satu bagian rantai yang didefinisikan di Pr + j ,r + j , untuk suatu j ≥ 1 . Jika Pr + j ,r + j imprimitif, maka prosesnya akan terus berosilasi kelas ergodik ke- j selamanya sedangkan jika Pr + j ,r + j primitif maka prosesnya akan berakhir pada steady-state yang didefinisikan oleh vektor Perron dari Pr + j ,r + j .

Tidak banyak yang bisa dikatakan mengenai limit dari matriks stokastik tereduksi ini. Namun, masih terdapat beberapa pertanyaan mengenai kelas ergodik manakah suatu rantai akan berakhir dan berapa lama waktu yang diperlukan untuk mencapainya tersebut. Sampai sejauh ini, jawaban atas pertanyaan tersebut masih bergantung pada state mana rantai dimulai atau kita perlu mengetahui distribusi awalnya.

4.4

Contoh Kasus Perhitungan Distribusi Limit dari Rantai Markov Untuk mendapatkan gambaran atau deskripsi yang jelas mengenai perhitungan mengenai limit distribusi dari matriks transisi rantai Markov, berikut ini akan diberikan dua contoh kasus, yaitu kasus 1 dimana matriks stokastiknya bersifat tak tereduksi dan kasus 2 dimana matriks stokastiknya bersifat tereduksi. Contoh kasus ini diperoleh dari buku An Introduction to Stochastic Modeling (Taylor and Karlin).


70


4.4.1 Kasus 1 : Matriks Stokastik Tak Tereduksi Dalam ilmu sosiologi, kelas sosial untuk generasi berikutnya secara berturut-turut dalam suatu keluarga dapat dipandang sebagai rantai Markov. Dalam hal ini, pekerjaan seorang anak diasumsikan hanya bergantung pada pekerjaan ayahnya dan tidak bergantung pada pekerjaan kakeknya. Pekerjaan tersebut membagi kelas sosial masyarakat menjadi tiga kelas, yaitu kelas bawah, kelas menengah, dan kelas atas. Dengan kata lain, pekerjaan ini menentukan sesorang untuk masuk kelas sosial tertentu. Misalkan peluang transisi tersebut diberikan sebagai berikut.

Pekerjaan Anak Kelas Bawah

Pekerjaan Ayah

Kelas Menengah

Kelas Atas

Kelas Bawah

0.40

0.50

0.10

Kelas Menengah

0.05

0.70

0.25

Kelas Atas

0.05

0.50

0.45

(4.7)

Sebut matriks transisi pada (4.7) adalah P . Berdasarkan matriks transisi diatas bisa kita peroleh σ ( P ) = {1, 1/ 5, 7 / 20} . Hal ini jelas bahwa P adalah matriks nonnegatif dengan spectral radius ρ ( P ) = 1 .

Dengan memisalkan dalam populasi tertentu, kondisi sosial pada kasus ini memiliki distribusi awal seragam, yaitu pT ( 0 ) = (1/ 3,1/ 3,1/ 3) . Jika matriks transisi seperti yang diberikan pada (4.7), maka peluang seorang anak memiliki pekerjaan dengan kelas bawah setelah 3 turunan adalah ⎡⎣ pT ( 3) ⎤⎦ = ⎡⎣ pT ( 0 ) P 3 ⎤⎦ = 0.0879 . Secara keseluruhan, distribusi pada 1 1

langkah ke-3 adalah pT ( 3) = ( 0.0879; 0.6227; 0.2894 ) .


71


Karena P primitif, maka lim P k dan lim pT ( k ) ada. Nilai limit tersebut k →∞

k →∞

ditentukan oleh vektor Perron kiri dari matriks P yang bisa diperoleh dengan

menghitung

vektor

tak

nol

v ∈ N ( I − PT )

dan

menormalisasikannya sehingga diperoleh π T = vT / v 1 . Dari persamaan

(I − P ) v = 0 T

diperoleh bahwa

vT = ( 0.1104; 0.8971; 0.4278 )

maka

π T = ( 0.0769; 0.6250; 0.2981) dan ⎛ 0.0769 0.6250 0.2981⎞ ⎜ ⎟ lim P = ⎜ 0.0769 0.6250 0.2981⎟ dan k →∞ ⎜ 0.0769 0.6250 0.2981⎟ ⎝ ⎠ k

lim pT ( k ) = ( 0.0769; 0.6250; 0.2981) . k →∞

Limit dari distribusi ini bisa diinterpretasikan bahwa setelah kurun waktu yang lama, sebesar 7.69% dari populasi akan berada pada kelas bawah, sebesar 62.50% dari populasi akan berada kelas menengah, dan sisanya sebesar 29.81% dari populasi akan berada pada kelas atas.

4.4.2 Kasus 2 : Matriks Stokastik Tereduksi Salah satu hal yang mempengaruhi kelajuan suatu populasi adalah usia produktif dari wanita. Perubahan struktur dalam masyarakat seperti peningkatan usia nikah dini, banyaknya janda yang menikah lagi, dan perceraian mempunyai dampak yang cukup signifikan dalam pertumbuhan rata-rata populasi. Untuk melihat kecenderungan pertambahan populasi beberapa tahun kedepan berdasarkan usia produktif wanita berdasarkan statusnya, salah satu model yang dapat dikembangkan adalah dengan membaginya menjadi 7 state. Kita bisa memandang model ini sebagai rantai Markov. Ketujuh state tersebut adalah

E1 : Migrasi E2 : Masa Pertumbuhan Teori Perron-Frobenius untuk Matriks Stokastik Madona Yunita (10103035)

72


E3 : Belum Menikah E4 : Menikah E5 : Bercerai E6 : Janda E7 : Meninggal

E1

E2

E3

E4

E5

E6

E7

E1 E2

1 0.02

0 0

0 0.90

0 0

0 0

0 0

0 0.08

E3 P = E4 E5

0.02 0.03 0.02

0 0 0

0.50 0 0

0.40 0.60 0.40

0 0.20 0.50

0 0.10 0

0.08 0.07 0.08

E6 E7

0.01 0

0 0

0 0

0.40 0

0 0

0.50 0

0.09 1

(4.8)

Berdasarkan matriks transisi (4.8), kita bisa perhatikan bahwa state untuk migrasi

dan

meninggal

merupakan

state

terabsorpsi.

Dengan

menggunakan Progrma Matlab, kita permutasikan matriks P sehingga P berada dalam bentuk canonical seperti berikut ini.

E2

E3

E4

E5

E6

E1

E7

E2 E3

0 0

0.90 0.50

0 0.40

0 0

0 0

0.02 0.02

0.08 0.08

E4 P = E5 E6

0 0 0

0 0 0

0.60 0.40 0.40

0.20 0.50 0

0.10 0 0.50

0.03 0.02 0.01

0.07 0.08 0.09

E1 E7

0 0

0 0

0 0

0 0

0 0

1 0

0 1

Selanjutnya, matriks dalam bentuk cannoncial tersebut kita cari nilai limitnya berdasarkan Teorema 4.5 dengan menggunakan program Matlab, yaitu


73


⎛0 ⎜ ⎜0 ⎜0 ⎛ 0 ( I − T11 )−1 T12I ⎞ ⎜ k lim P = ⎜ ⎟⎟ = ⎜ 0 ⎜0 k →∞ I ⎝ ⎠ ⎜0 ⎜ ⎜0 ⎜0 ⎝

0 0

0 0

0 0

0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0.236 0.764 ⎞ ⎟ 0.240 0.760 ⎟ 0.250 0.750 ⎟ ⎟ 0.240 0.760 ⎟ 0.220 0.780 ⎟ ⎟ 1 0 ⎟ ⎟ 0 1 ⎠

Berdasarkan hasil tersebut, bisa kita perhatikan bahwa untuk periode yang cukup lama, setiap wanita akan terperangkap dalam

state terabsorpsi.

Dalam hal ini, state terabsorpsi tersebut adalah migrasi dan meninggal. Sebelum memasuki state terabsorpsi, setiap wanita akan berada pada status masa pertumbuhan, belum menikah, menikah, bercerai, atau janda yang disebut dengan state transien. Peluang transisi setiap wanita untuk terperangkap di suatu state terabsorpsi masih bergantung pada state awalnya seperti yang terlihat pada (4.8). Namun, peluang seseorang meninggal lebih besar dibandingkan peluang seseorang melakukan migrasi setelah jangka waktu yang cukup lama.


74

BAB IV APLIKASI PADA MATRIKS STOKASTIK

Recommend Documents