kuliah ke-2 uas proses stokastik

RANTAI MARKOV DENGAN WAKTU DISKRETKLASIFIKASI STATE

I Wayan Mangku & Hadi Sumarno

Departemen Matematika FMIPA IPB

18 April 2011

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 1 / 22

KLASIFIKASI STATE: STATE YANG TERAKSES,KOMUNIKATIF, IRREDUCIBLE, PENYERAP

DefinitionAccessible State

Suatu state j disebut terakses (accessible) dari state i , kita tulisi → j , jika ada minimal sebuah bilangan bulat k ≥ 0 sehinggap(k )ij > 0.

i

1

2

.

.

.

n

1

2

.

.

.

n

j

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 2 / 22

Bukti Matematis

Artinya, state j terakses dari state i jika dan hanya jika dimulai dari statei, sistem memungkinkan untuk sampai ke state j

Ini adalah benar, sebab jika state j tidak terakses dari state i, maka

P(proses pernah ke state j |dimulai dari state i)= P (

⋃∞

n=0{Xn = j |X0 = i})

≤∞

∑n=0

P(Xn = j |X0 = i) =∞

∑n=0

p(n)ij = 0

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 3 / 22

Dua State Saling Berkomunikasi

DefinitionBerkomunikasi

Dua sate i dan j disebut berkomunikasi (commmunicate), kita tulis i↔ j ,jika state i dapat diakses dari state j dan state j dapat diaksesdari state i.

DefinitionKelas dari state

Suatu kelas dari state adalah suatu himpunan tak kosong C sehinggasemua pasangan state yang merupakan anggota dari C adalahberkomunikasi satu dengan yang lainnya, serta tidak ada state yangmerupakan anggota C yang berkomunikasi dengan suatu state yangbukan anggota dari C.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 4 / 22

Kelas dari State (Himpunan Tertutup) dari State

Kelas dari state kadangkala disebut sebagai himpunan tertutup daristate.

Jika C adalah suatu kelas (himpunan tertutup) dari state makaberlaku bahwa pij = 0 untuk ∀i ∈ C dan j /∈ C .Sembarang state adalah berkomunikasi dengan dirinya sendiri, karenap(0)ij = P(X0 = i)|X0 = 1) = 1.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 5 / 22

Sifat Berkomunikasi dari State

1 State i berkomunikasi dengan state i untuk semua i≥0.2 Jika state i berkomunikasi dengan state j, maka state j berkomunikasidengan state i.

3 Jika state i berkomunikasi dengan state j, dan state j berkomunikasidengan state k, maka state i berkomunikasi dengan state k.

Bukti (3). Karena i ↔ j ,dan j ↔ k, maka i → j dan j → k, maka adam, n ∈ Z sehinggap(n)ij > 0 dan p(m)jk > 0.Dari persamaan Chapman-Kolmogorov didapat

p(n+m)ik =∞

∑r=0

p(n)ir p(m)rk ≥ p

(n)ir p

(m)rk . > 0

Artinya, state k terakses dari state i .(i → k).Sebaliknya, berdasarkan fakta bahwa j → i dan k → j ,dapat ditunjukkanpula bahwa i terakses dari k (k → i).Oleh karena itu, state i dan k saling berkomunikasi.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 6 / 22

Sifat Kelas

Berdasarkan sifat (1) , (2) dan (3), maka untuk sembarang dua kelasstate hanya berlaku salah satu dari dua hal, yaitu kedua kelas tersebutlepas (disjoint) atau identik.

Dengan kata lain, konsep dari berkomunikasi membagi ruang stateatas sejumlah kelas yang saling lepas.

DefinitionsDefinisi 6. Suatu rantai Markov disebut tak tereduksi (irreducible) jikahanya terdapat satu kelas state (satu himpunan tertutup state), yaitu jikasemua state-nya berkomunikasi satu dengan yang lainnya.

DefinitionsDefinisi 7. Suatu state i disebut state penyerap (absorbing state) jika pii= 1

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 7 / 22

Sifat Kelas

Berdasarkan sifat (1) , (2) dan (3), maka untuk sembarang dua kelasstate hanya berlaku salah satu dari dua hal, yaitu kedua kelas tersebutlepas (disjoint) atau identik.

Dengan kata lain, konsep dari berkomunikasi membagi ruang stateatas sejumlah kelas yang saling lepas.

DefinitionsDefinisi 6. Suatu rantai Markov disebut tak tereduksi (irreducible) jikahanya terdapat satu kelas state (satu himpunan tertutup state), yaitu jikasemua state-nya berkomunikasi satu dengan yang lainnya.

DefinitionsDefinisi 7. Suatu state i disebut state penyerap (absorbing state) jika pii= 1

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 7 / 22

Sifat Kelas

Berdasarkan sifat (1) , (2) dan (3), maka untuk sembarang dua kelasstate hanya berlaku salah satu dari dua hal, yaitu kedua kelas tersebutlepas (disjoint) atau identik.

Dengan kata lain, konsep dari berkomunikasi membagi ruang stateatas sejumlah kelas yang saling lepas.

DefinitionsDefinisi 6. Suatu rantai Markov disebut tak tereduksi (irreducible) jikahanya terdapat satu kelas state (satu himpunan tertutup state), yaitu jikasemua state-nya berkomunikasi satu dengan yang lainnya.

DefinitionsDefinisi 7. Suatu state i disebut state penyerap (absorbing state) jika pii= 1

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 7 / 22

Sifat Kelas

Berdasarkan sifat (1) , (2) dan (3), maka untuk sembarang dua kelasstate hanya berlaku salah satu dari dua hal, yaitu kedua kelas tersebutlepas (disjoint) atau identik.

Dengan kata lain, konsep dari berkomunikasi membagi ruang stateatas sejumlah kelas yang saling lepas.

DefinitionsDefinisi 6. Suatu rantai Markov disebut tak tereduksi (irreducible) jikahanya terdapat satu kelas state (satu himpunan tertutup state), yaitu jikasemua state-nya berkomunikasi satu dengan yang lainnya.

DefinitionsDefinisi 7. Suatu state i disebut state penyerap (absorbing state) jika pii= 1

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 7 / 22

Contoh 6. Kelas Tidak Tereduksi

Diberikan rantai Markov tiga state sebagai berikut.

P=

13

23 0

14

12

14

0 12

12

State 1 terakses dari state 0 karena p01( 23 ) > 0,dan state 0 teraksesdari state 1 karena p10( 14 ) > 0. Maka 0↔ 1.

State 2 terakses dari state 1 karena p12( 14 ) > 0,dan state 1 teraksesdari state 2 karena p21( 12 ) > 0. Maka 1↔ 2.

State 2 terakses dari state 0 karena 0 → 1 dan 1→ 2. State 0terakses dari state 2 karena 2 → 1 dan 1→ 0. Maka 0↔ 2.

Karena state 0, 1, dan 2 saling berkomunikasi, maka rantai Markovtersebut tidak tereduksi.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 8 / 22

Contoh 6. Kelas Tidak Tereduksi

Diberikan rantai Markov tiga state sebagai berikut.

P=

13

23 0

14

12

14

0 12

12

State 1 terakses dari state 0 karena p01( 23 ) > 0,dan state 0 teraksesdari state 1 karena p10( 14 ) > 0. Maka 0↔ 1.

State 2 terakses dari state 1 karena p12( 14 ) > 0,dan state 1 teraksesdari state 2 karena p21( 12 ) > 0. Maka 1↔ 2.

State 2 terakses dari state 0 karena 0 → 1 dan 1→ 2. State 0terakses dari state 2 karena 2 → 1 dan 1→ 0. Maka 0↔ 2.

Karena state 0, 1, dan 2 saling berkomunikasi, maka rantai Markovtersebut tidak tereduksi.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 8 / 22

Contoh 6. Kelas Tidak Tereduksi

Diberikan rantai Markov tiga state sebagai berikut.

P=

13

23 0

14

12

14

0 12

12

State 1 terakses dari state 0 karena p01( 23 ) > 0,dan state 0 teraksesdari state 1 karena p10( 14 ) > 0. Maka 0↔ 1.

State 2 terakses dari state 1 karena p12( 14 ) > 0,dan state 1 teraksesdari state 2 karena p21( 12 ) > 0. Maka 1↔ 2.

State 2 terakses dari state 0 karena 0 → 1 dan 1→ 2. State 0terakses dari state 2 karena 2 → 1 dan 1→ 0. Maka 0↔ 2.

Karena state 0, 1, dan 2 saling berkomunikasi, maka rantai Markovtersebut tidak tereduksi.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 8 / 22

Contoh 6. Kelas Tidak Tereduksi

Diberikan rantai Markov tiga state sebagai berikut.

P=

13

23 0

14

12

14

0 12

12

State 1 terakses dari state 0 karena p01( 23 ) > 0,dan state 0 teraksesdari state 1 karena p10( 14 ) > 0. Maka 0↔ 1.

State 2 terakses dari state 1 karena p12( 14 ) > 0,dan state 1 teraksesdari state 2 karena p21( 12 ) > 0. Maka 1↔ 2.

State 2 terakses dari state 0 karena 0 → 1 dan 1→ 2. State 0terakses dari state 2 karena 2 → 1 dan 1→ 0. Maka 0↔ 2.

Karena state 0, 1, dan 2 saling berkomunikasi, maka rantai Markovtersebut tidak tereduksi.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 8 / 22

Contoh 7. Kelas Rantai Markov

Diberikan rantai Markov empat state sebagai berikut.

P=

13

23 0 0

12

12 0 0

14

14

14

14

0 0 0 1

State 0 ↔ 1,karena 0→ 1 dan 1→ 0. Sedangkan state 0= 2, &1= 2 karena 0 atau 1 dapat diakses dari 2, tetapi state 2 tidak dapatdiakses dari 0 atau 1. Artinya state 2 tidak sekelas dengan state 1.

Karena state 3 merupakan state penyerap, maka tidak ada state yangdapat diakses dari state 3. Artinya state 3 tidak sekelas dengan state0 & 1, atau state 2. Sehingga kelas dari rantai Markov adalah{0,1},{2},{3}.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 9 / 22

Contoh 7. Kelas Rantai Markov

1/3 1/2

1/4

1/2

1/4 1/4

1/4

1

2/3

.IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 10 / 22

First-Passage Time Probability

Misalkan f (n)i ,j menyatakan peluang bahwa, mulai dari state i, prosesbertransisi untuk pertama kalinya ke state j, dan terjadi pada waktun, yaitu

f (n)i ,j = P(Xn = j ,Xk 6= j , ∀ 1 ≤ k ≤ n− 1|X0 = 1)dan

f (0)i ,j = 0

untuk semua i , j ∈ {0, 1, 2, 3, .....}.Selanjutnya untuk setiap i , j ∈ {0, 1, 2, 3, .....} kita definisikan

fij =∞

∑n=1

f (n)i ,j (1)

Jadi, untuk setiap i , j ∈ {0, 1, 2, 3, .....}, fij menyatakan peluangbahwa suatu proses yang dimulai pada state i akan pernah bertransisike state j .

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 11 / 22

First-Passage Time Probability

Misalkan f (n)i ,j menyatakan peluang bahwa, mulai dari state i, prosesbertransisi untuk pertama kalinya ke state j, dan terjadi pada waktun, yaitu

f (n)i ,j = P(Xn = j ,Xk 6= j , ∀ 1 ≤ k ≤ n− 1|X0 = 1)

dan

f (0)i ,j = 0

untuk semua i , j ∈ {0, 1, 2, 3, .....}.Selanjutnya untuk setiap i , j ∈ {0, 1, 2, 3, .....} kita definisikan

fij =∞

∑n=1

f (n)i ,j (1)

Jadi, untuk setiap i , j ∈ {0, 1, 2, 3, .....}, fij menyatakan peluangbahwa suatu proses yang dimulai pada state i akan pernah bertransisike state j .

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 11 / 22

First-Passage Time Probability

Misalkan f (n)i ,j menyatakan peluang bahwa, mulai dari state i, prosesbertransisi untuk pertama kalinya ke state j, dan terjadi pada waktun, yaitu

f (n)i ,j = P(Xn = j ,Xk 6= j , ∀ 1 ≤ k ≤ n− 1|X0 = 1)dan

f (0)i ,j = 0

untuk semua i , j ∈ {0, 1, 2, 3, .....}.Selanjutnya untuk setiap i , j ∈ {0, 1, 2, 3, .....} kita definisikan

fij =∞

∑n=1

f (n)i ,j (1)

Jadi, untuk setiap i , j ∈ {0, 1, 2, 3, .....}, fij menyatakan peluangbahwa suatu proses yang dimulai pada state i akan pernah bertransisike state j .

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 11 / 22

First-Passage Time Probability

Misalkan f (n)i ,j menyatakan peluang bahwa, mulai dari state i, prosesbertransisi untuk pertama kalinya ke state j, dan terjadi pada waktun, yaitu

f (n)i ,j = P(Xn = j ,Xk 6= j , ∀ 1 ≤ k ≤ n− 1|X0 = 1)dan

f (0)i ,j = 0

untuk semua i , j ∈ {0, 1, 2, 3, .....}.Selanjutnya untuk setiap i , j ∈ {0, 1, 2, 3, .....} kita definisikan

fij =∞

∑n=1

f (n)i ,j (1)

Jadi, untuk setiap i , j ∈ {0, 1, 2, 3, .....}, fij menyatakan peluangbahwa suatu proses yang dimulai pada state i akan pernah bertransisike state j .

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 11 / 22

First-Passage Time Probability

Misalkan f (n)i ,j menyatakan peluang bahwa, mulai dari state i, prosesbertransisi untuk pertama kalinya ke state j, dan terjadi pada waktun, yaitu

f (n)i ,j = P(Xn = j ,Xk 6= j , ∀ 1 ≤ k ≤ n− 1|X0 = 1)dan

f (0)i ,j = 0

untuk semua i , j ∈ {0, 1, 2, 3, .....}.

Selanjutnya untuk setiap i , j ∈ {0, 1, 2, 3, .....} kita definisikan

fij =∞

∑n=1

f (n)i ,j (1)

Jadi, untuk setiap i , j ∈ {0, 1, 2, 3, .....}, fij menyatakan peluangbahwa suatu proses yang dimulai pada state i akan pernah bertransisike state j .

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 11 / 22

First-Passage Time Probability

Misalkan f (n)i ,j menyatakan peluang bahwa, mulai dari state i, prosesbertransisi untuk pertama kalinya ke state j, dan terjadi pada waktun, yaitu

f (n)i ,j = P(Xn = j ,Xk 6= j , ∀ 1 ≤ k ≤ n− 1|X0 = 1)dan

f (0)i ,j = 0

untuk semua i , j ∈ {0, 1, 2, 3, .....}.Selanjutnya untuk setiap i , j ∈ {0, 1, 2, 3, .....} kita definisikan

fij =∞

∑n=1

f (n)i ,j (1)

Jadi, untuk setiap i , j ∈ {0, 1, 2, 3, .....}, fij menyatakan peluangbahwa suatu proses yang dimulai pada state i akan pernah bertransisike state j .

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 11 / 22

First-Passage Time Probability

Misalkan f (n)i ,j menyatakan peluang bahwa, mulai dari state i, prosesbertransisi untuk pertama kalinya ke state j, dan terjadi pada waktun, yaitu

f (n)i ,j = P(Xn = j ,Xk 6= j , ∀ 1 ≤ k ≤ n− 1|X0 = 1)dan

f (0)i ,j = 0

untuk semua i , j ∈ {0, 1, 2, 3, .....}.Selanjutnya untuk setiap i , j ∈ {0, 1, 2, 3, .....} kita definisikan

fij =∞

∑n=1

f (n)i ,j (1)

Jadi, untuk setiap i , j ∈ {0, 1, 2, 3, .....}, fij menyatakan peluangbahwa suatu proses yang dimulai pada state i akan pernah bertransisike state j .

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 11 / 22

First-Passage Time Probability

Misalkan f (n)i ,j menyatakan peluang bahwa, mulai dari state i, prosesbertransisi untuk pertama kalinya ke state j, dan terjadi pada waktun, yaitu

f (n)i ,j = P(Xn = j ,Xk 6= j , ∀ 1 ≤ k ≤ n− 1|X0 = 1)dan

f (0)i ,j = 0

untuk semua i , j ∈ {0, 1, 2, 3, .....}.Selanjutnya untuk setiap i , j ∈ {0, 1, 2, 3, .....} kita definisikan

fij =∞

∑n=1

f (n)i ,j (1)

Jadi, untuk setiap i , j ∈ {0, 1, 2, 3, .....}, fij menyatakan peluangbahwa suatu proses yang dimulai pada state i akan pernah bertransisike state j .

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 11 / 22

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 12 / 22

,

State yang Recurent (berulang)

DefinitionDefinisi 8. State i disebut recurrent (berulang) jika fii = 1, dan disebuttransient jika fii < 1.)

Untuk setiap state i, fii menyatakan peluang bahwa suatu proses yangdimulai pada state i akan pernah bertransisi kembali ke state i.Jika state i recurrent, maka dengan peluang 1, proses itu akhirnyaakan masuk kembali ke state i. Akan tetapi, berdasarkan definisirantai Markov, kita peroleh bahwa ketika proses itu masuk kembali kestate i maka proses tersebut dimulai lagi. Jadi jika state i adalahrecurrent, maka proses yang dimulai dari state i akan berulang kalimasuk kembali ke state i, dan pada kenyataannya akan kembali kestate i sebanyak tak hingga kali.Berdasarkan argumen di atas, kita peroleh bahwa state i adalahrecurrent (berulang) jika dan hanya jika, untuk suatu proses yangmulai dari state i, nilai harapan dari banyaknya kunjungan prosestersebut ke state i adalah tak terhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 12 / 22

State yang Recurent (berulang)

DefinitionDefinisi 8. State i disebut recurrent (berulang) jika fii = 1, dan disebuttransient jika fii < 1.)

Untuk setiap state i, fii menyatakan peluang bahwa suatu proses yangdimulai pada state i akan pernah bertransisi kembali ke state i.

Jika state i recurrent, maka dengan peluang 1, proses itu akhirnyaakan masuk kembali ke state i. Akan tetapi, berdasarkan definisirantai Markov, kita peroleh bahwa ketika proses itu masuk kembali kestate i maka proses tersebut dimulai lagi. Jadi jika state i adalahrecurrent, maka proses yang dimulai dari state i akan berulang kalimasuk kembali ke state i, dan pada kenyataannya akan kembali kestate i sebanyak tak hingga kali.Berdasarkan argumen di atas, kita peroleh bahwa state i adalahrecurrent (berulang) jika dan hanya jika, untuk suatu proses yangmulai dari state i, nilai harapan dari banyaknya kunjungan prosestersebut ke state i adalah tak terhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 12 / 22

State yang Recurent (berulang)

DefinitionDefinisi 8. State i disebut recurrent (berulang) jika fii = 1, dan disebuttransient jika fii < 1.)

Untuk setiap state i, fii menyatakan peluang bahwa suatu proses yangdimulai pada state i akan pernah bertransisi kembali ke state i.Jika state i recurrent, maka dengan peluang 1, proses itu akhirnyaakan masuk kembali ke state i. Akan tetapi, berdasarkan definisirantai Markov, kita peroleh bahwa ketika proses itu masuk kembali kestate i maka proses tersebut dimulai lagi. Jadi jika state i adalahrecurrent, maka proses yang dimulai dari state i akan berulang kalimasuk kembali ke state i, dan pada kenyataannya akan kembali kestate i sebanyak tak hingga kali.

Berdasarkan argumen di atas, kita peroleh bahwa state i adalahrecurrent (berulang) jika dan hanya jika, untuk suatu proses yangmulai dari state i, nilai harapan dari banyaknya kunjungan prosestersebut ke state i adalah tak terhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 12 / 22

State yang Recurent (berulang)

DefinitionDefinisi 8. State i disebut recurrent (berulang) jika fii = 1, dan disebuttransient jika fii < 1.)

Untuk setiap state i, fii menyatakan peluang bahwa suatu proses yangdimulai pada state i akan pernah bertransisi kembali ke state i.Jika state i recurrent, maka dengan peluang 1, proses itu akhirnyaakan masuk kembali ke state i. Akan tetapi, berdasarkan definisirantai Markov, kita peroleh bahwa ketika proses itu masuk kembali kestate i maka proses tersebut dimulai lagi. Jadi jika state i adalahrecurrent, maka proses yang dimulai dari state i akan berulang kalimasuk kembali ke state i, dan pada kenyataannya akan kembali kestate i sebanyak tak hingga kali.Berdasarkan argumen di atas, kita peroleh bahwa state i adalahrecurrent (berulang) jika dan hanya jika, untuk suatu proses yangmulai dari state i, nilai harapan dari banyaknya kunjungan prosestersebut ke state i adalah tak terhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 12 / 22

State yang Recurrent/Transient: banyaknya kunjungantakhingga/terhingga

Jika state i transient, maka setiap proses itu memasuki state i, makaada peluang positif, yaitu (1− fii ), bahwa proses tersebut tidak akanpernah kembali ke state i.

Jadi, jika proses mulai dari state i, peluang bahwa proses akan beradapada state i tepat n kali periode adalah f (n−1)ii (1− fii ), n ≥ 1.Dengan kata lain, jika state i adalah transient dan proses mulai daristate i, maka banyaknya frekuensi periode waktu bahwa proses akanberada pada state i adalah menyebar geometrik dengan nilai harapan

finite (terhingga)1

1− fii.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 13 / 22

State yang Recurrent/Transient: banyaknya kunjungantakhingga/terhingga

Jika state i transient, maka setiap proses itu memasuki state i, makaada peluang positif, yaitu (1− fii ), bahwa proses tersebut tidak akanpernah kembali ke state i.

Jadi, jika proses mulai dari state i, peluang bahwa proses akan beradapada state i tepat n kali periode adalah f (n−1)ii (1− fii ), n ≥ 1.

Dengan kata lain, jika state i adalah transient dan proses mulai daristate i, maka banyaknya frekuensi periode waktu bahwa proses akanberada pada state i adalah menyebar geometrik dengan nilai harapan

finite (terhingga)1

1− fii.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 13 / 22

State yang Recurrent/Transient: banyaknya kunjungantakhingga/terhingga

Jika state i transient, maka setiap proses itu memasuki state i, makaada peluang positif, yaitu (1− fii ), bahwa proses tersebut tidak akanpernah kembali ke state i.

Jadi, jika proses mulai dari state i, peluang bahwa proses akan beradapada state i tepat n kali periode adalah f (n−1)ii (1− fii ), n ≥ 1.Dengan kata lain, jika state i adalah transient dan proses mulai daristate i, maka banyaknya frekuensi periode waktu bahwa proses akanberada pada state i adalah menyebar geometrik dengan nilai harapan

finite (terhingga)1

1− fii.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 13 / 22

State yang Recurrent/Transient: banyaknya kunjungantakhingga/terhingga

Misalkan

In ={1 , jika Xn = i0 , jika Xn 6= i

(2)

Maka ∑∞n=0 In menyatakan banyaknya kunjungan ke i .

E(∑∞n=0 In |X0 = i) = ∑∞

n=0 P (Xn = i |X0 = i) = ∑∞n=0 p

(n)ii

Theorem

Teorema 2. State i adalah recurrent jika ∑∞n=0 p

(n)ii = ∞, dan transient

jika ∑∞n=0 p

(n)ii < ∞.

Suatu state yang transient akan terkunjungi sebanyak bilanganterhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 14 / 22

State yang Recurrent/Transient: banyaknya kunjungantakhingga/terhingga

Misalkan

In ={1 , jika Xn = i0 , jika Xn 6= i

(2)

Maka ∑∞n=0 In menyatakan banyaknya kunjungan ke i .

E(∑∞n=0 In |X0 = i) = ∑∞

n=0 P (Xn = i |X0 = i) = ∑∞n=0 p

(n)ii

Theorem

Teorema 2. State i adalah recurrent jika ∑∞n=0 p

(n)ii = ∞, dan transient

jika ∑∞n=0 p

(n)ii < ∞.

Suatu state yang transient akan terkunjungi sebanyak bilanganterhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 14 / 22

State yang Recurrent/Transient: banyaknya kunjungantakhingga/terhingga

Misalkan

In ={1 , jika Xn = i0 , jika Xn 6= i

(2)

Maka ∑∞n=0 In menyatakan banyaknya kunjungan ke i .

E(∑∞n=0 In |X0 = i) = ∑∞

n=0 P (Xn = i |X0 = i) = ∑∞n=0 p

(n)ii

Theorem

Teorema 2. State i adalah recurrent jika ∑∞n=0 p

(n)ii = ∞, dan transient

jika ∑∞n=0 p

(n)ii < ∞.

Suatu state yang transient akan terkunjungi sebanyak bilanganterhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 14 / 22

State yang Recurrent/Transient: banyaknya kunjungantakhingga/terhingga

Misalkan

In ={1 , jika Xn = i0 , jika Xn 6= i

(2)

Maka ∑∞n=0 In menyatakan banyaknya kunjungan ke i .

E(∑∞n=0 In |X0 = i) = ∑∞

n=0 P (Xn = i |X0 = i) = ∑∞n=0 p

(n)ii

Theorem

Teorema 2. State i adalah recurrent jika ∑∞n=0 p

(n)ii = ∞, dan transient

jika ∑∞n=0 p

(n)ii < ∞.

Suatu state yang transient akan terkunjungi sebanyak bilanganterhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 14 / 22

State yang Recurrent/Transient: banyaknya kunjungantakhingga/terhingga

Misalkan

In ={1 , jika Xn = i0 , jika Xn 6= i

(2)

Maka ∑∞n=0 In menyatakan banyaknya kunjungan ke i .

E(∑∞n=0 In |X0 = i) = ∑∞

n=0 P (Xn = i |X0 = i) = ∑∞n=0 p

(n)ii

Theorem

Teorema 2. State i adalah recurrent jika ∑∞n=0 p

(n)ii = ∞, dan transient

jika ∑∞n=0 p

(n)ii < ∞.

Suatu state yang transient akan terkunjungi sebanyak bilanganterhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 14 / 22

State yang Recurrent/Transient: banyaknya kunjungantakhingga/terhingga

Misalkan

In ={1 , jika Xn = i0 , jika Xn 6= i

(2)

Maka ∑∞n=0 In menyatakan banyaknya kunjungan ke i .

E(∑∞n=0 In |X0 = i) = ∑∞

n=0 P (Xn = i |X0 = i) = ∑∞n=0 p

(n)ii

Theorem

Teorema 2. State i adalah recurrent jika ∑∞n=0 p

(n)ii = ∞, dan transient

jika ∑∞n=0 p

(n)ii < ∞.

Suatu state yang transient akan terkunjungi sebanyak bilanganterhingga.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 14 / 22

State yang Transient : banyaknya kunjungan terhingga

Hal ini menghasilkan suatu kesimpulan bahwa pada kasus rantaiMarkov dengan banyak state yang terhingga, tidak mungkin semuastate adalah transient.Untuk melihat hal ini, misalkan statenya adalah 0; 1; : : : ; M, danmisalkan semuanya transient. Maka setelah waktu bilangan terhingga(sebut T0), maka state 0 tidak akan pernah dikunjungi lagi; setelahselama waktu (terhingga), setelah T1, state 1 tidak akan pernahdikunjungi lagi, dan seterusnya.Sehingga, setelah waktu (terhingga) T = max(T0; T1; : : : ; TM ),tidak akan ada state yang dikunjungi lagi.Di lain pihak, setelah waktu T, proses tersebut harus berada padasuatu state.Maka kita berakhir dengan suatu kontradiksi, yang sekaligusmemperlihatkan bahwa pasti ada paling sedikit satu state yangberulang (recurrent)

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 15 / 22

State yang Transient : banyaknya kunjungan terhingga

Hal ini menghasilkan suatu kesimpulan bahwa pada kasus rantaiMarkov dengan banyak state yang terhingga, tidak mungkin semuastate adalah transient.

Untuk melihat hal ini, misalkan statenya adalah 0; 1; : : : ; M, danmisalkan semuanya transient. Maka setelah waktu bilangan terhingga(sebut T0), maka state 0 tidak akan pernah dikunjungi lagi; setelahselama waktu (terhingga), setelah T1, state 1 tidak akan pernahdikunjungi lagi, dan seterusnya.Sehingga, setelah waktu (terhingga) T = max(T0; T1; : : : ; TM ),tidak akan ada state yang dikunjungi lagi.Di lain pihak, setelah waktu T, proses tersebut harus berada padasuatu state.Maka kita berakhir dengan suatu kontradiksi, yang sekaligusmemperlihatkan bahwa pasti ada paling sedikit satu state yangberulang (recurrent)

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 15 / 22

State yang Transient : banyaknya kunjungan terhingga

Hal ini menghasilkan suatu kesimpulan bahwa pada kasus rantaiMarkov dengan banyak state yang terhingga, tidak mungkin semuastate adalah transient.Untuk melihat hal ini, misalkan statenya adalah 0; 1; : : : ; M, danmisalkan semuanya transient. Maka setelah waktu bilangan terhingga(sebut T0), maka state 0 tidak akan pernah dikunjungi lagi; setelahselama waktu (terhingga), setelah T1, state 1 tidak akan pernahdikunjungi lagi, dan seterusnya.

Sehingga, setelah waktu (terhingga) T = max(T0; T1; : : : ; TM ),tidak akan ada state yang dikunjungi lagi.Di lain pihak, setelah waktu T, proses tersebut harus berada padasuatu state.Maka kita berakhir dengan suatu kontradiksi, yang sekaligusmemperlihatkan bahwa pasti ada paling sedikit satu state yangberulang (recurrent)

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 15 / 22

State yang Transient : banyaknya kunjungan terhingga

Hal ini menghasilkan suatu kesimpulan bahwa pada kasus rantaiMarkov dengan banyak state yang terhingga, tidak mungkin semuastate adalah transient.Untuk melihat hal ini, misalkan statenya adalah 0; 1; : : : ; M, danmisalkan semuanya transient. Maka setelah waktu bilangan terhingga(sebut T0), maka state 0 tidak akan pernah dikunjungi lagi; setelahselama waktu (terhingga), setelah T1, state 1 tidak akan pernahdikunjungi lagi, dan seterusnya.Sehingga, setelah waktu (terhingga) T = max(T0; T1; : : : ; TM ),tidak akan ada state yang dikunjungi lagi.

Di lain pihak, setelah waktu T, proses tersebut harus berada padasuatu state.Maka kita berakhir dengan suatu kontradiksi, yang sekaligusmemperlihatkan bahwa pasti ada paling sedikit satu state yangberulang (recurrent)

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 15 / 22

State yang Transient : banyaknya kunjungan terhingga

Hal ini menghasilkan suatu kesimpulan bahwa pada kasus rantaiMarkov dengan banyak state yang terhingga, tidak mungkin semuastate adalah transient.Untuk melihat hal ini, misalkan statenya adalah 0; 1; : : : ; M, danmisalkan semuanya transient. Maka setelah waktu bilangan terhingga(sebut T0), maka state 0 tidak akan pernah dikunjungi lagi; setelahselama waktu (terhingga), setelah T1, state 1 tidak akan pernahdikunjungi lagi, dan seterusnya.Sehingga, setelah waktu (terhingga) T = max(T0; T1; : : : ; TM ),tidak akan ada state yang dikunjungi lagi.Di lain pihak, setelah waktu T, proses tersebut harus berada padasuatu state.

Maka kita berakhir dengan suatu kontradiksi, yang sekaligusmemperlihatkan bahwa pasti ada paling sedikit satu state yangberulang (recurrent)

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 15 / 22

State yang Transient : banyaknya kunjungan terhingga

Hal ini menghasilkan suatu kesimpulan bahwa pada kasus rantaiMarkov dengan banyak state yang terhingga, tidak mungkin semuastate adalah transient.Untuk melihat hal ini, misalkan statenya adalah 0; 1; : : : ; M, danmisalkan semuanya transient. Maka setelah waktu bilangan terhingga(sebut T0), maka state 0 tidak akan pernah dikunjungi lagi; setelahselama waktu (terhingga), setelah T1, state 1 tidak akan pernahdikunjungi lagi, dan seterusnya.Sehingga, setelah waktu (terhingga) T = max(T0; T1; : : : ; TM ),tidak akan ada state yang dikunjungi lagi.Di lain pihak, setelah waktu T, proses tersebut harus berada padasuatu state.Maka kita berakhir dengan suatu kontradiksi, yang sekaligusmemperlihatkan bahwa pasti ada paling sedikit satu state yangberulang (recurrent)

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 15 / 22

Recurrent merupakan sifat dari kelas

CorollaryCorollary 3 Jika state i adalah recurrent (berulang) dan state iberkomunikasi dengan state j, maka state j adalah recurrent.

Bukti:Karena state i berkomunikasi dengan state j, maka ada bilangan bulatk dan m sedemikian sehingga p(k )ij > 0 dan p(m)ji > 0.Selanjutnya, untuk sembarang bilangan bulat n kita memilikip(m+n+k )jj ≥ p(m)ji p(n)ii p

(k )ij .

Dengan menjumlahkan kedua ruas terhadap n diperoleh

∑∞n=0 p

(m+n+k )jj ≥ ∑∞

n=0 p(m)ji p(n)ii p

(k )ij

∑∞n=0 p

(m+n+k )jj ≥ p(m)ji p(k )ij ∑∞

n=0 p(k )ij .

Karena p(k )ij > 0 dan p(m)ji > 0,maka p(m)ji p(k )ij > 0.Demikian pula,

karena state i adalah recurrent,maka ∑∞n=0 p

(n)ii = ∞.Sehingga

∑∞n=0 p

(m+n+k )jj = ∞,atau state j recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 16 / 22

Recurrent merupakan sifat dari kelas

CorollaryCorollary 3 Jika state i adalah recurrent (berulang) dan state iberkomunikasi dengan state j, maka state j adalah recurrent.

Bukti:

Karena state i berkomunikasi dengan state j, maka ada bilangan bulatk dan m sedemikian sehingga p(k )ij > 0 dan p(m)ji > 0.Selanjutnya, untuk sembarang bilangan bulat n kita memilikip(m+n+k )jj ≥ p(m)ji p(n)ii p

(k )ij .

Dengan menjumlahkan kedua ruas terhadap n diperoleh

∑∞n=0 p

(m+n+k )jj ≥ ∑∞

n=0 p(m)ji p(n)ii p

(k )ij

∑∞n=0 p

(m+n+k )jj ≥ p(m)ji p(k )ij ∑∞

n=0 p(k )ij .

Karena p(k )ij > 0 dan p(m)ji > 0,maka p(m)ji p(k )ij > 0.Demikian pula,

karena state i adalah recurrent,maka ∑∞n=0 p

(n)ii = ∞.Sehingga

∑∞n=0 p

(m+n+k )jj = ∞,atau state j recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 16 / 22

Recurrent merupakan sifat dari kelas

CorollaryCorollary 3 Jika state i adalah recurrent (berulang) dan state iberkomunikasi dengan state j, maka state j adalah recurrent.

Bukti:Karena state i berkomunikasi dengan state j, maka ada bilangan bulatk dan m sedemikian sehingga p(k )ij > 0 dan p(m)ji > 0.

Selanjutnya, untuk sembarang bilangan bulat n kita memilikip(m+n+k )jj ≥ p(m)ji p(n)ii p

(k )ij .

Dengan menjumlahkan kedua ruas terhadap n diperoleh

∑∞n=0 p

(m+n+k )jj ≥ ∑∞

n=0 p(m)ji p(n)ii p

(k )ij

∑∞n=0 p

(m+n+k )jj ≥ p(m)ji p(k )ij ∑∞

n=0 p(k )ij .

Karena p(k )ij > 0 dan p(m)ji > 0,maka p(m)ji p(k )ij > 0.Demikian pula,

karena state i adalah recurrent,maka ∑∞n=0 p

(n)ii = ∞.Sehingga

∑∞n=0 p

(m+n+k )jj = ∞,atau state j recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 16 / 22

Recurrent merupakan sifat dari kelas

CorollaryCorollary 3 Jika state i adalah recurrent (berulang) dan state iberkomunikasi dengan state j, maka state j adalah recurrent.

Bukti:Karena state i berkomunikasi dengan state j, maka ada bilangan bulatk dan m sedemikian sehingga p(k )ij > 0 dan p(m)ji > 0.Selanjutnya, untuk sembarang bilangan bulat n kita memiliki

p(m+n+k )jj ≥ p(m)ji p(n)ii p(k )ij .

Dengan menjumlahkan kedua ruas terhadap n diperoleh

∑∞n=0 p

(m+n+k )jj ≥ ∑∞

n=0 p(m)ji p(n)ii p

(k )ij

∑∞n=0 p

(m+n+k )jj ≥ p(m)ji p(k )ij ∑∞

n=0 p(k )ij .

Karena p(k )ij > 0 dan p(m)ji > 0,maka p(m)ji p(k )ij > 0.Demikian pula,

karena state i adalah recurrent,maka ∑∞n=0 p

(n)ii = ∞.Sehingga

∑∞n=0 p

(m+n+k )jj = ∞,atau state j recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 16 / 22

Recurrent merupakan sifat dari kelas

CorollaryCorollary 3 Jika state i adalah recurrent (berulang) dan state iberkomunikasi dengan state j, maka state j adalah recurrent.

Bukti:Karena state i berkomunikasi dengan state j, maka ada bilangan bulatk dan m sedemikian sehingga p(k )ij > 0 dan p(m)ji > 0.Selanjutnya, untuk sembarang bilangan bulat n kita memilikip(m+n+k )jj ≥ p(m)ji p(n)ii p

(k )ij .

Dengan menjumlahkan kedua ruas terhadap n diperoleh

∑∞n=0 p

(m+n+k )jj ≥ ∑∞

n=0 p(m)ji p(n)ii p

(k )ij

∑∞n=0 p

(m+n+k )jj ≥ p(m)ji p(k )ij ∑∞

n=0 p(k )ij .

Karena p(k )ij > 0 dan p(m)ji > 0,maka p(m)ji p(k )ij > 0.Demikian pula,

karena state i adalah recurrent,maka ∑∞n=0 p

(n)ii = ∞.Sehingga

∑∞n=0 p

(m+n+k )jj = ∞,atau state j recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 16 / 22

Recurrent merupakan sifat dari kelas

CorollaryCorollary 3 Jika state i adalah recurrent (berulang) dan state iberkomunikasi dengan state j, maka state j adalah recurrent.

Bukti:Karena state i berkomunikasi dengan state j, maka ada bilangan bulatk dan m sedemikian sehingga p(k )ij > 0 dan p(m)ji > 0.Selanjutnya, untuk sembarang bilangan bulat n kita memilikip(m+n+k )jj ≥ p(m)ji p(n)ii p

(k )ij .

Dengan menjumlahkan kedua ruas terhadap n diperoleh

∑∞n=0 p

(m+n+k )jj ≥ ∑∞

n=0 p(m)ji p(n)ii p

(k )ij

∑∞n=0 p

(m+n+k )jj ≥ p(m)ji p(k )ij ∑∞

n=0 p(k )ij .

Karena p(k )ij > 0 dan p(m)ji > 0,maka p(m)ji p(k )ij > 0.Demikian pula,

karena state i adalah recurrent,maka ∑∞n=0 p

(n)ii = ∞.Sehingga

∑∞n=0 p

(m+n+k )jj = ∞,atau state j recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 16 / 22

Recurrent merupakan sifat dari kelas

CorollaryCorollary 3 Jika state i adalah recurrent (berulang) dan state iberkomunikasi dengan state j, maka state j adalah recurrent.

Bukti:Karena state i berkomunikasi dengan state j, maka ada bilangan bulatk dan m sedemikian sehingga p(k )ij > 0 dan p(m)ji > 0.Selanjutnya, untuk sembarang bilangan bulat n kita memilikip(m+n+k )jj ≥ p(m)ji p(n)ii p

(k )ij .

Dengan menjumlahkan kedua ruas terhadap n diperoleh

∑∞n=0 p

(m+n+k )jj ≥ ∑∞

n=0 p(m)ji p(n)ii p

(k )ij

∑∞n=0 p

(m+n+k )jj ≥ p(m)ji p(k )ij ∑∞

n=0 p(k )ij .

Karena p(k )ij > 0 dan p(m)ji > 0,maka p(m)ji p(k )ij > 0.Demikian pula,

karena state i adalah recurrent,maka ∑∞n=0 p

(n)ii = ∞.Sehingga

∑∞n=0 p

(m+n+k )jj = ∞,atau state j recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 16 / 22

Recurrent merupakan sifat dari kelas

CorollaryCorollary 3 Jika state i adalah recurrent (berulang) dan state iberkomunikasi dengan state j, maka state j adalah recurrent.

Bukti:Karena state i berkomunikasi dengan state j, maka ada bilangan bulatk dan m sedemikian sehingga p(k )ij > 0 dan p(m)ji > 0.Selanjutnya, untuk sembarang bilangan bulat n kita memilikip(m+n+k )jj ≥ p(m)ji p(n)ii p

(k )ij .

Dengan menjumlahkan kedua ruas terhadap n diperoleh

∑∞n=0 p

(m+n+k )jj ≥ ∑∞

n=0 p(m)ji p(n)ii p

(k )ij

∑∞n=0 p

(m+n+k )jj ≥ p(m)ji p(k )ij ∑∞

n=0 p(k )ij .

Karena p(k )ij > 0 dan p(m)ji > 0,maka p(m)ji p(k )ij > 0.Demikian pula,

karena state i adalah recurrent,maka ∑∞n=0 p

(n)ii = ∞.Sehingga

∑∞n=0 p

(m+n+k )jj = ∞,atau state j recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 16 / 22

Recurrent merupakan sifat dari kelas

CorollaryCorollary 3 Jika state i adalah recurrent (berulang) dan state iberkomunikasi dengan state j, maka state j adalah recurrent.

Bukti:Karena state i berkomunikasi dengan state j, maka ada bilangan bulatk dan m sedemikian sehingga p(k )ij > 0 dan p(m)ji > 0.Selanjutnya, untuk sembarang bilangan bulat n kita memilikip(m+n+k )jj ≥ p(m)ji p(n)ii p

(k )ij .

Dengan menjumlahkan kedua ruas terhadap n diperoleh

∑∞n=0 p

(m+n+k )jj ≥ ∑∞

n=0 p(m)ji p(n)ii p

(k )ij

∑∞n=0 p

(m+n+k )jj ≥ p(m)ji p(k )ij ∑∞

n=0 p(k )ij .

Karena p(k )ij > 0 dan p(m)ji > 0,maka p(m)ji p(k )ij > 0.Demikian pula,

karena state i adalah recurrent,maka ∑∞n=0 p

(n)ii = ∞.Sehingga

∑∞n=0 p

(m+n+k )jj = ∞,atau state j recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 16 / 22

Transient merupakan sifat dari kelas

(i) Corollary 3 juga berimplikasi bahwa ketransienan adalah merupakansuatu sifat kelas. Misalnya, jika state i adalah transient dan berkomunikasidengan state j, maka state j juga transient. Karena jika state j adalahrecurrent, maka berdasarkan Corollary 3, state i juga pasti recurrent danbukan transient.(ii) Corollary 3 bersama dengan kesimpulan kita sebelumnya bahwa tidaksemua state pada rantai Markov yang banyak statenya terbatas adalahtransient, menghasilkan suatu kesimpulan bahwa seluruh state dari suaturantai Markov tak tereduksi yang banyak statenya terhingga adalahrecurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 17 / 22

Contoh 8. State Transient dan Recurrent

Diberikan rantai Markov empat state sebagai berikut.

P=

0 0 0 11 0 0 01 0 0 00 1

323 0

Untuk memeriksa apakahr antai Markov tersebut recurrent atautrensient akan ditunjukkan bahawa semua state saling berkomunikasi.

0↔ 2 karena 0→ 3, 3→ 2 dan 2→ 0.0↔ 3 karena 0→ 3 dan 3→, 1→ 0.1↔ 2 karena 1→ 0, 0→ 3, 3→ 2 dan 2→ 0, 0→ 3, 3→ 1.1↔ 3 karena 1→ 0, 0→ 3 dan 3→ 1.2↔ 3 karena 2→ 0, 0→ 3 dan 3→ 2.

Karena banyaknya state terhingga, maka semua state recurrent.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 18 / 22

Contoh 8. State Transient dan Recurrent

Diberikan rantai Markov lima state sebagai berikut.

P=

12

14

14 0 0

0 12 0 1

2 00 0 1

2 0 12

0 12 0 1

2 00 0 1

2 0 12

Terdiri dari tiga kelas {0}(transient), {1,3},{2,4} (recurrent)

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 19 / 22

Contoh 10. Jalan Acak (Random Walk)

DefinitionDefinisi 9. Jalan acak sederhana adalah suatu rantai Markov dengan ruangstate himpunan bilangan bulat, dan mempunyai peluang transisi pi ,i+1 = pdan pi ,i−1 = 1− p; i = 0,±1,±2, · · · dengan 0<p<1. Artinya pada tiaptransisi proses akan bergerak satu step kekanan dengan peluang p ataubergerak satu step kekiri dengan peluang 1- p.

Karena semua state saling berkomunikasi, maka state tersebutsemuanya recurrent atau semuanya transient.

Untuk memeriksa hal tersebut, kita periksa salah satu state apakahrecurrent atau transient, misalnya state 0. State tersebut recurrentjika ∑∞

n=0 p(n)0,0 = ∞ sebaliknya disebut transient jika ∑∞

n=0 p(n)0,0 < ∞.

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 20 / 22

Contoh 10. Jalan Acak (Random Walk)

Dengan menggunakan intepretasi model judi bisa kita lihat bahwa, jikadimulai dari state 0, maka state tersebut tidak mungkin bernilai 0 setelahsebanyak bilangan ganjil permainan(transisi). Jadi

p(2n+1)0,0 = 0; n = 0, 1, 2, · · · .State akan bernilai 0 setelah 2n kali permainan, jika dan hanya jika n kalimenang dan n kali kalah.

Karena setiap kali permainan akan menang dengan peluang p dankalah dengan peluang 1− p, maka berdasarkan kaidah binomial,peluang menang sebanyak n kali dalam 2n permainan kita peroleh

p(2n)0,0 =

(2nn

)pn (1− p)n

=(2n)!n!n!

pn (1− p)n ; n = 1, 2, 3, · · · .

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 21 / 22

Contoh 10. Jalan Acak (Random Walk)

Dengan menggunakan pendekatan Stirling, kita perolehn! ∼ nne−n

√2πn,

dimana kita katakan an ∼ bn jika limn→∞ an/bn = 1.Akhirnya kita perolehp(2n)0,0 = [4p(1−p)]n√

πn

Adalah mudah untuk memperlihatkan jika an ∼ bn, maka∑∞n=0 an < ∞ jika dan hanya jika ∑∞

n=0 an < ∞.Jadi ∑∞

n=0 p(2n)0,0 < ∞ jika dan hanya jika ∑∞

n=0[4p(1−p)]n√

πn< ∞

∑∞n=0

[4p(1−p)]n√πn

< ∞ jika 4p (1− p) < 1.4p (1− p) maksimum sama dengan 1, terjadi bila p = 1

2 .Kesimpulannya, rantai akan recurrent (berulang) jika p = 1

2dantransient jika p 6= 1

2 .Jika p = 1

2 , proses di atas disebut jalan acak simetri (symmetricrandom walk).

IWM & HSU (MATH-IPB) RANTAI MARKOV 18 April 2011 22 / 22