Dalam kajian rantai Markov waktu diskret, terutama perilaku limitnya, selang waktu acak antarkunjungan ke suatu keadaan memegang peranan penting. Sifat selang-selang tersebut menimbulkan dikotomi mendasar pada keadaan-keadaan rantai.
Teori Dasar
Seperti biasa, titik awal kita adalah ruang probabilitas \( (\Omega, \mathscr{F}, \P) \), dengan \( \Omega \) sebagai ruang sampel, \( \mathscr{F} \) sebagai \( \sigma \)-aljabar kejadian, dan \( \P \) sebagai ukuran probabilitas pada \( (\Omega, \mathscr{F}) \). Misalkan sekarang \( \bs{X} = (X_0, X_1, X_2, \ldots) \) adalah rantai Markov waktu diskret (homogen terhadap waktu) dengan ruang keadaan (terhitung) \( S \) dan matriks probabilitas transisi \( P \). Untuk membahas semua keadaan—termasuk keadaan yang mungkin berpeluang nol di bawah \(\P\)—pilih keluarga hukum Markov \((\P_x)_{x\in S}\) dengan \(\P_x(X_0=x)=1\), dan tulis \(\E_x\) untuk nilai harapannya. Tetapkan \[ P(x,y)=\P_x(X_1=y),\qquad P^n(x,y)=\P_x(X_n=y),\qquad x,y\in S,\ n\in\N. \] Pada halaman ini, ungkapan \(\P(\,cdot\mid X_0=x)\) dan \(\E(\,cdot\mid X_0=x)\) selanjutnya merupakan notasi singkat untuk \(\P_x\) dan \(\E_x\). Misalkan \( \mathscr{F}_n = \sigma\{X_0, X_1, \ldots, X_n\} \), yaitu \( \sigma \)-aljabar kejadian yang ditentukan oleh rantai hingga waktu \( n \in \N \), sehingga \( \mathfrak{F} = (\mathscr{F}_0, \mathscr{F}_1, \ldots) \) adalah filtrasi alami yang berkaitan dengan \( \bs{X} \).
Waktu dan Probabilitas Pencapaian
Misalkan \( A \) adalah himpunan bagian tak kosong dari \( S \). Ingat bahwa waktu pencapaian ke \( A \) adalah peubah acak yang memberikan waktu positif pertama ketika rantai berada di \( A \): \[ \tau_A = \min\{n \in \N_+: X_n \in A\} \] Karena rantai mungkin tidak pernah mencapai \( A \), peubah acak \( \tau_A \) mengambil nilai dalam \( \N_+ \cup \{\infty\} \) (ingat konvensi kita bahwa minimum himpunan kosong adalah \( \infty \)). Ingat pula bahwa \( \tau_A \) adalah waktu henti bagi \( \bs{X} \). Artinya, \( \{\tau_A = n\} \in \mathscr{F}_n \) untuk \( n \in \N_+ \). Secara intuitif, ini berarti bahwa kita dapat menentukan apakah \( \tau_A = n \) dengan mengamati rantai hingga waktu \( n \). Hal ini jelas berlaku karena, secara eksplisit, \[ \{\tau_A=n\} =\bigcap_{j=1}^{n-1}\{X_j\notin A\}\cap\{X_n\in A\}, \qquad n\in\N_+, \] dengan konvensi bahwa irisan kosong sama dengan \(\Omega\). Ketika \( A = \{x\} \) untuk \( x \in S \), kita akan menyederhanakan notasinya menjadi \( \tau_x \). Peubah acak ini memberikan waktu positif pertama ketika rantai berada pada keadaan \( x \). Ketika rantai mencapai suatu himpunan keadaan \( A \) untuk pertama kalinya, rantai itu harus mengunjungi suatu keadaan dalam \( A \) untuk pertama kalinya, sehingga jelas bahwa \[ \tau_A = \min\{\tau_x: x \in A\}, \quad A \subseteq S \] Selanjutnya, kita mendefinisikan dua fungsi pada \( S \) yang berkaitan dengan waktu pencapaian.
Untuk \( x \in S \), \( A \subseteq S \) (tak kosong), dan \( n \in \N_+ \), definisikan
- \( H_n(x, A) = \P(\tau_A = n \mid X_0 = x)\)
- \(H(x, A) = \P(\tau_A \lt \infty \mid X_0 = x) \)
Dengan demikian, \( H(x, A) = \sum_{n=1}^\infty H_n(x, A) \).
Pemetaan \( n \mapsto H_n(x, A) \) merupakan fungsi massa probabilitas \( \tau_A \) bersyarat pada \( X_0 = x \). Fungsi ini dapat defektif: jumlah \( H(x, A) \) mungkin kurang dari 1. Dalam hal itu, tentu saja \( 1 - H(x, A) = \P(\tau_A = \infty \mid X_0 = x) \). Sekali lagi, ketika \( A = \{y\} \), kita menyederhanakan notasinya masing-masing menjadi \( H_n(x, y) \) dan \( H(x, y) \). Secara khusus, \( H(x, x) \) adalah probabilitas bahwa rantai yang dimulai dari \( x \) pada akhirnya kembali ke \( x \). Jika \( x \ne y \), \( H(x, y) \) adalah probabilitas bahwa rantai yang dimulai dari \( x \) pada akhirnya mencapai \( y \). Mengetahui apakah \( H(x, y) \) bernilai 0, positif, atau 1 sangat penting bagi struktur keseluruhan dan perilaku limit rantai. Sebagai fungsi pada \( S^2 \), kita menyebut \( H \) matriks pencapaian dari \( \bs{X} \). Namun, tidak seperti matriks transisi \( P \), matriks ini tidak memiliki struktur kernel. Artinya, \( A \mapsto H(x, A) \) bukan suatu ukuran; khususnya, secara umum tidak benar bahwa \( H(x, A) = \sum_{y \in A} H(x, y) \). Hal yang sama berlaku untuk \( H_n \) dengan \( n \in \N_+ \). Meskipun demikian, terdapat hubungan menarik antara matriks transisi dan matriks pencapaian.
\( H(x, y) \gt 0 \) jika dan hanya jika \( P^n(x, y) \gt 0 \) untuk suatu \( n \in \N_+ \).
Rincian:
Perhatikan bahwa \( \{X_n = y\} \subseteq \{\tau_y \lt \infty\} \) untuk semua \( n \in \N_+ \), dan \( \{\tau_y<\infty\}=\{X_k=y\text{ untuk suatu }k\in\N_+\} \). Dari sifat menaik probabilitas dan pertidaksamaan Boole, diperoleh bahwa untuk setiap \( n \in \N_+ \), \[ P^n(x, y) \le H(x, y) \le \sum_{k=1}^\infty P^k(x, y) \]
Hasil berikut memberikan hubungan dasar antara barisan probabilitas pencapaian dan barisan probabilitas transisi.
Misalkan \( (x, y) \in S^2 \). Maka \[ \begin{gathered} P^n(x,y)=\sum_{k=1}^{n}H_k(x,y)P^{n-k}(y,y),\\ n\in\N_+. \end{gathered} \]
Rincian:
Untuk \(n\in\N_+\), kejadian-kejadian \(\{\tau_y=k,X_n=y\}\), \(1\le k\le n\), mempartisi \(\{X_n=y\}\). Karena \(\tau_y\) adalah waktu henti dan \(X_{\tau_y}=y\) pada \(\{\tau_y<\infty\}\), sifat Markov kuat pada \(\tau_y\) memberikan \[ \begin{aligned} P^n(x,y) &=\P_x(X_n=y)\\ &=\sum_{k=1}^{n}\P_x(X_n=y,\tau_y=k)\\ &=\sum_{k=1}^{n} \E_x\!\left[\bs{1}_{\{\tau_y=k\}} P^{n-k}(X_{\tau_y},y)\right]\\ &=\sum_{k=1}^{n}H_k(x,y)P^{n-k}(y,y). \end{aligned} \] Inilah identitas yang dinyatakan di atas.
Misalkan \(x\in S\) dan \(A\subseteq S\) tak kosong. Maka
- \( H_{n+1}(x, A) = \sum_{y \notin A} P(x, y) H_n(y, A) \) untuk \( n \in \N_+ \)
- \( H(x, A) = P(x, A) + \sum_{y \notin A} P(x, y) H(y, A) \)
Rincian:
Hasil-hasil ini diperoleh dengan mengondisikan pada \( X_1 \).
- Untuk \(n\in\N_+\), dekomposisi menurut keadaan pada waktu 1 dan sifat Markov memberikan \[ \begin{aligned} H_{n+1}(x,A) &=\sum_{y\notin A}\P_x(\tau_A=n+1,X_1=y)\\ &=\sum_{y\notin A}P(x,y)\P_y(\tau_A=n)\\ &=\sum_{y\notin A}P(x,y)H_n(y,A). \end{aligned} \] Argumen ini berlaku untuk setiap keadaan karena memakai keluarga \((\P_x)_{x\in S}\), bukan pengondisian pada kejadian nol.
- Pisahkan kemungkinan \(X_1\in A\) dari kemungkinan \(X_1=y\notin A\). Sifat Markov memberikan \[ \begin{aligned} H(x,A) &=\P_x(X_1\in A) +\sum_{y\notin A}\P_x(X_1=y)\P_y(\tau_A<\infty)\\ &=P(x,A)+\sum_{y\notin A}P(x,y)H(y,A). \end{aligned} \]
Definisi berikut mendasar bagi kajian rantai Markov.
Misalkan \( x \in S \).
- Keadaan \( x \) rekuren jika \( H(x, x) = 1 \).
- Keadaan \( x \) transien jika \( H(x, x) \lt 1 \).
Jadi, rantai yang dimulai pada keadaan rekuren pada akhirnya kembali ke keadaan itu dengan probabilitas 1. Seperti yang akan kita lihat, rantai bahkan kembali tak hingga kali dengan probabilitas 1, dan waktu-waktu kunjungannya menjadi waktu kedatangan suatu proses pembaruan. Fakta ini penting dalam mengkaji perilaku limit rantai. Sebaliknya, dari keadaan transien terdapat probabilitas positif bahwa rantai tidak pernah kembali.
Peubah Pencacahan dan Potensial
Misalkan kembali bahwa \( A \) adalah himpunan keadaan tak kosong. Pelengkap alami bagi waktu pencapaian ke \( A \) adalah peubah pencacahan yang memberikan banyaknya kunjungan ke \( A \) (pada waktu positif). Jadi, misalkan \[ N_A = \sum_{n=1}^\infty \bs{1}(X_n \in A) \] Perhatikan bahwa \( N_A \) mengambil nilai dalam \( \N \cup \{\infty\} \). Kita terutama akan menaruh perhatian pada kasus khusus \( A = \{x\} \) untuk \( x \in S \), dan dalam kasus ini kita akan menyederhanakan notasinya menjadi \( N_x \).
Misalkan \( G(x, A) = \E(N_A \mid X_0 = x) \) untuk \( x \in S \) dan \( A \subseteq S \). Maka \( G \) adalah kernel pada \( S \) dan \[ G(x, A) = \sum_{n=1}^\infty P^n(x, A) \]
Rincian:
Perhatikan bahwa \[ \begin{aligned} G(x,A) &=\E_x\!\left[\sum_{n=1}^{\infty}\bs1(X_n\in A)\right]\\ &=\sum_{n=1}^{\infty}\P_x(X_n\in A) =\sum_{n=1}^{\infty}P^n(x,A). \end{aligned} \] Pertukaran urutan penjumlahan dan nilai harapan sah karena suku-sukunya nonnegatif. Untuk \( x \in S \) yang tetap, \( A \mapsto G(x, A) \) adalah ukuran positif pada \( S \) karena \( A \mapsto P^n(x, A) \) adalah ukuran probabilitas pada \( S \) untuk setiap \( n \in \N_+ \). Perhatikan pula bahwa \( A \mapsto N_A \) adalah ukuran pencacahan acak pada \( S \), sehingga \( A \mapsto G(x, A) \) adalah ukuran positif (deterministik) pada \( S \).
Jadi, \( G(x, A) \) adalah nilai harapan banyaknya kunjungan ke \( A \) pada waktu positif. Seperti biasa, ketika \( A = \{y\} \) untuk \( y \in S \), kita menyederhanakan notasinya menjadi \( G(x, y) \). Secara lebih umum, kita kemudian memiliki \( G(x, A) = \sum_{y \in A} G(x, y) \) untuk \( A \subseteq S \). Dengan demikian, sebagai matriks pada \( S \), \( G = \sum_{n=1}^\infty P^n \). Matriks \( G \) berkaitan erat dengan matriks potensial \( R \) dari \( \bs{X} \), yang diberikan oleh \( R = \sum_{n=0}^\infty P^n \). Jadi, \( R = I + G \), dan \( R(x, y) \) memberikan nilai harapan banyaknya kunjungan ke \( y \in S \) pada semua waktu (bukan hanya waktu positif), jika rantai dimulai pada \( x \in S \). Matriks \( G \) lebih berguna bagi tujuan kita dalam bagian ini.
Distribusi \( N_y \) dapat dinyatakan secara sederhana melalui probabilitas pencapaian. Berdasarkan sifat Markov dan homogenitas terhadap waktu, setiap kali rantai mencapai keadaan \( y \), perilaku selanjutnya tidak bergantung pada masa lalu dan mempunyai hukum yang sama dengan rantai yang dimulai dari \( y \) pada waktu 0. Pengamatan ini menjadi kunci pembuktian teorema berikut.
Jika \( x, \, y \in S \), maka
- \(\P(N_y = 0 \mid X_0 = x) = 1 - H(x, y)\)
- \( \P(N_y = n \mid X_0 = x) = H(x, y) [H(y, y)]^{n-1}[1 - H(y, y)] \) untuk \( n \in \N_+ \)
Rincian:
- Kejadian \( N_y = 0 \) berarti bahwa rantai tidak pernah mencapai \( y \) ketika dimulai pada \( x \). Probabilitas kejadian ini adalah \( 1 - H(x, y) \).
- Untuk \( n \in \N_+ \), kejadian \( N_y = n \) berarti bahwa rantai mencapai \( y \) ketika dimulai pada \( x \), lalu kembali sebanyak \( n - 1 \) kali ke \( y \), dan setelah itu tidak pernah mencapai \( y \) lagi. Probabilitas ketiga kejadian tersebut adalah \( H(x, y) \), \( [H(y, y)]^{n-1} \), dan \( 1 - H(y, y) \). Probabilitas-probabilitas tersebut dikalikan berdasarkan sifat Markov.
Diagram di atas merangkum gagasan pembuktiannya. Garis tebal bukanlah transisi satu langkah, melainkan mewakili seluruh lintasan di antara simpul-simpul yang ditunjukkan. Dalam kasus khusus \( x = y \), kita mempunyai \[ \P(N_x = n \mid X_0 = x) = [H(x, x)]^n [1 - H(x, x)], \quad n \in \N \] Dalam semua kasus, peubah pencacahan \( N_y \) pada dasarnya memiliki distribusi geometrik, tetapi distribusinya mungkin defektif, dengan sebagian massa probabilitas berada di \( \infty \). Perilakunya sangat berbeda bergantung pada apakah \( y \) transien atau rekuren.
Jika \( x, \, y \in S \) dan \( y \) transien, maka
- \( \P(N_y \lt \infty \mid X_0 = x) = 1 \)
- \( G(x, y) = H(x, y) \big/ [1 - H(y, y)] \)
- \( H(x, y) = G(x, y) \big/ [1 + G(y, y)] \)
Rincian:
- Jika \( y \) transien, maka \( H(y, y) \lt 1 \). Karena itu, dengan menggunakan distribusi banyaknya kunjungan dan deret geometri, \[ \begin{aligned} \P_x(N_y\in\N_+) &=\sum_{n=1}^{\infty}\P_x(N_y=n)\\ &=H(x,y)[1-H(y,y)] \sum_{n=1}^{\infty}[H(y,y)]^{n-1}\\ &=H(x,y). \end{aligned} \] Karena itu, \begin{align*} \P(N_y \lt \infty \mid X_0 = x) & = \P(N_y \in \N \mid X_0 = x) = \P(N_y = 0 \mid X_0 = x) + \P(N_y \in \N_+ \mid X_0 = x) \\ & = [1 - H(x, y)] + H(x, y) = 1 \end{align*}
- Dengan menggunakan turunan deret geometri, \begin{align*} G(x, y) & = \E(N_y \mid X_0 = x) = \sum_{n=1}^\infty n \P(N_y = n \mid X_0 = x) \\ & = H(x, y) [1 - H(y, y)]\sum_{n=1}^\infty n [H(y, y)]^{n-1} = \frac{H(x, y)}{1 - H(y, y)} \end{align*}
- Dari (b), \( G(y, y) = H(y, y) \big/[1 - H(y, y)] \), sehingga penyelesaian terhadap \( H(y, y) \) memberikan \( H(y, y) = G(y, y) \big/ [1 + G(y, y)] \). Substitusi hasil ini kembali ke (b) memberikan \( G(x, y) = H(x, y)[1 + G(y, y)] \).
Jika \( x, \, y \in S \) dan \( y \) rekuren, maka
- \( \P(N_y = 0 \mid X_0 = x) = 1 - H(x, y) \) dan \( \P(N_y = \infty \mid X_0 = x) = H(x, y) \)
- \( G(x, y) = 0 \) jika \( H(x, y) = 0 \) dan \( G(x, y) = \infty \) jika \( H(x, y) \gt 0 \)
- \( \P(N_y = \infty \mid X_0 = y) = 1 \) dan \( G(y, y) = \infty \)
Rincian:
- Jika \(y\) rekuren, \(H(y,y)=1\), sehingga dari distribusi banyaknya kunjungan, \(\P_x(N_y=n)=0\) untuk semua \(n\in\N_+\). Karena itu, \[ \P_x(N_y=\infty)=1-\P_x(N_y=0)=H(x,y). \]
- Jika \( H(x, y) = 0 \), maka \( \P(N_y = 0 \mid X_0 = x) = 1 \), sehingga \( \E(N_y \mid X_0 = x) = 0 \). Jika \( H(x, y) \gt 0 \), maka \( \P(N_y = \infty \mid X_0 = x) \gt 0 \), sehingga \( \E(N_y \mid X_0 = x) = \infty \).
- Dari distribusi banyaknya kunjungan, \(\P_y(N_y=n)=0\) untuk semua \(n\in\N\), sehingga \(\P_y(N_y=\infty)=1\).
Perhatikan bahwa terdapat hubungan yang dapat dibalik antara matriks \( H \) dan matriks \( G \); jika kita mengetahui salah satunya, kita dapat menghitung yang lain. Secara khusus, melalui \( G \) kita dapat mencirikan apakah suatu keadaan bersifat transien atau rekuren. Berikut rangkuman kita sejauh ini:
Misalkan \( x \in S \).
- Keadaan \( x \) transien jika dan hanya jika \( H(x, x) \lt 1 \) jika dan hanya jika \( G(x, x) \lt \infty \).
- Keadaan \( x \) rekuren jika dan hanya jika \( H(x, x) = 1 \) jika dan hanya jika \( G(x, x) = \infty \).
Tentu saja, klasifikasi tersebut juga berlaku bagi matriks potensial \( R = I + G \). Artinya, keadaan \( x \in S \) transien jika dan hanya jika \( R(x , x) \lt \infty \), dan keadaan \( x \) rekuren jika dan hanya jika \( R(x, x) = \infty \).
Relasi
Probabilitas pencapaian menyarankan suatu relasi penting pada ruang keadaan \( S \).
Untuk \( (x, y) \in S^2 \), keadaan \( x \) dapat mencapai keadaan \( y \), yang dinotasikan dengan \( x \to y \), jika \( x = y \) atau \( H(x, y) \gt 0 \).
Langsung dari kriteria pencapaian melalui pangkat transisi diperoleh bahwa \( x \to y \) jika dan hanya jika \( P^n(x, y) \gt 0 \) untuk suatu \( n \in \N \). Dalam graf keadaan rantai, \( x \to y \) jika dan hanya jika \( x = y \) atau terdapat lintasan berarah dari \( x \) ke \( y \). Perhatikan bahwa relasi ketercapaian bersifat refleksif berdasarkan definisi: \( x \to x \) untuk setiap \( x \in S \). Relasi ini juga memiliki sifat penting lainnya.
Relasi ketercapaian bersifat transitif: Untuk \( x, \, y, \, z \in S \), jika \( x \to y \) dan \( y \to z \), maka \( x \to z \).
Rincian:
Jika \( x \to y \) dan \( y \to z \), maka terdapat \(j,k\in\N\) sedemikian sehingga \( P^j(x, y) \gt 0 \) dan \( P^k(y, z) \gt 0 \). Namun, \( P^{j+k}(x, z) \ge P^j(x, y) P^k(y, z) \gt 0 \), sehingga \( x \to z \).
Relasi ketercapaian secara alami menyarankan beberapa definisi penting lainnya.
Misalkan \( A \subseteq S \) tak kosong.
- \( A \) tertutup jika \( x \in A \) dan \( x \to y \) menyiratkan \( y \in A \).
- \( A \) tak tereduksi jika \( A \) tertutup dan tidak memiliki himpunan bagian sejati yang tertutup.
Misalkan \( A \subseteq S \) tertutup. Maka
- \( P_A \), yaitu pembatasan \( P \) pada \( A \times A\), adalah matriks probabilitas transisi pada \( A \).
- \( \bs{X} \) yang dibatasi pada \( A \) adalah rantai Markov dengan matriks probabilitas transisi \( P_A \).
- \( (P^n)_A = (P_A)^n \) untuk \( n \in \N \).
Rincian:
- Jika \( x \in A \) dan \( y \notin A \), maka \( x \) tidak dapat mencapai \( y \), sehingga khususnya \( P(x, y) = 0 \). Karena itu, \( \sum_{y \in A} P(x, y) = 1 \) untuk \( x \in A \), sehingga \( P_A \) adalah matriks probabilitas transisi.
- Hal ini diperoleh dari (a). Jika rantai dimulai di \( A \), rantai tetap berada di \( A \) sepanjang waktu, dan tentu saja sifat Markov tetap berlaku.
- Sekali lagi, hal ini diperoleh dari (a).
Tentu saja, seluruh ruang keadaan \( S \) tertutup berdasarkan definisi. Jika ruang itu juga tak tereduksi, kita mengatakan bahwa rantai Markov \( \bs{X} \) itu sendiri tak tereduksi. Ingat bahwa untuk himpunan bagian tak kosong \( A \) dari \( S \) dan untuk \( n \in \N \), notasi \( P_A^n \) merujuk pada \( (P_A)^n \), bukan \( (P^n)_A \). Secara umum, keduanya tidak sama; bahkan, untuk \( x, \, y \in A \), \[ P_A^0(x,y)=\bs1(x=y), \] sedangkan, untuk \(n\in\N_+\), \[ P_A^n(x,y) =\P_x\!\left( \bigcap_{j=1}^{n-1}\{X_j\in A\}\cap\{X_n=y\} \right), \] dengan irisan kosong sama dengan \(\Omega\). Besaran kedua adalah probabilitas berpindah dari \(x\) ke \(y\) dalam \(n\) langkah sambil tetap berada di \(A\) sepanjang waktu. Namun, jika \( A \) tertutup, seperti dinyatakan pada bagian (c), besaran ini sama dengan \( P^n(x, y) \).
Misalkan \( A \) adalah himpunan bagian tak kosong dari \( S \). Maka \( \cl(A)=\{y\in S:x\to y\text{ untuk suatu }x\in A\} \) adalah himpunan tertutup terkecil yang memuat \( A \), dan disebut tutupan \( A \). Artinya,
- \( \cl(A) \) tertutup.
- \( A \subseteq \cl(A) \).
- Jika \( B \) tertutup dan \( A \subseteq B \), maka \( \cl(A) \subseteq B \)
Rincian:
- Misalkan \( x \in \cl(A) \) dan \( x \to y \). Maka terdapat \( a \in A \) sedemikian sehingga \( a \to x \). Berdasarkan sifat transitif, \( a \to y \), sehingga \( y \in \cl(A) \).
- Jika \( x \in A \), maka \( x \to x \), sehingga \( x \in \cl(A) \).
- Misalkan \( B \) tertutup dan \( A \subseteq B \). Jika \( x \in \cl(A) \), maka terdapat \( a \in A \) sedemikian sehingga \( a \to x \). Karena itu, \( a \in B \) dan \( a \to x \). Karena \( B \) tertutup, diperoleh \( x \in B \). Jadi, \( \cl(A) \subseteq B \).
Ingat bahwa untuk bilangan bulat positif tetap \( k \), \( P^k \) juga merupakan matriks probabilitas transisi dan mengatur rantai Markov \( k \)-langkah \( (X_0, X_k, X_{2 k}, \ldots) \). Karena itu, kita dapat mempertimbangkan relasi ketercapaian bagi rantai ini, dan semua hasil di atas tetap berlaku (tentu saja, relatif terhadap rantai \( k \)-langkah). Kadang-kadang kita perlu mempertimbangkan relasi ini, yang akan kita notasikan dengan \( \underset{k} \to \), khususnya dalam kajian periodisitas.
Misalkan \( j, \, k \in \N_+ \). Jika \( x \, \underset{k}\to \, y \) dan \( j \mid k \), maka \( x \, \underset{j}\to \, y \).
Rincian:
Jika \( x \, \underset{k}\to \, y \), maka terdapat \( n \in \N \) sedemikian sehingga \( P^{n k}(x, y) \gt 0 \). Jika \( j \mid k \), terdapat \( m \in \N_+ \) sedemikian sehingga \( k = m j \). Karena itu, \( P^{n m j}(x, y) \gt 0 \), sehingga \( x \, \underset{j}\to \, y \).
Dengan menggabungkan relasi ketercapaian \( \to \) dengan relasi invers \( \leftarrow \), kita memperoleh relasi lain yang sangat berguna.
Untuk \( (x, y) \in S^2 \), kita mengatakan bahwa \( x \) dan \( y \) saling berkomunikasi, dan menulis \( x \leftrightarrow y \), jika \( x \to y \) dan \( y \to x \).
Berdasarkan definisi, relasi ini bersifat simetris: jika \( x \leftrightarrow y \), maka \( y \leftrightarrow x \). Dari pembahasan di atas, relasi ini juga refleksif dan transitif. Jadi, relasi komunikasi ini adalah relasi ekuivalensi. Seperti semua relasi ekuivalensi, relasi ini mempartisi ruang menjadi kelas-kelas komunikasi yang saling lepas. Kita akan menotasikan kelas komunikasi dari suatu keadaan \( x \in S \) dengan \[ [x] = \{y \in S: x \leftrightarrow y\} \] Dengan demikian, untuk sembarang dua keadaan \( x, \, y \in S\), berlaku \( [x] = [y] \) atau \( [x] \cap [y] = \emptyset \), dan selain itu \( \bigcup_{x \in S} [x] = S \).
Dua pernyataan yang secara umum tidak berlaku:
- Himpunan tertutup tidak selalu merupakan kelas komunikasi.
- Kelas komunikasi tidak selalu tertutup.
Contoh:
Pertimbangkan rantai Markov trivial dengan ruang keadaan \( S = \{0, 1\} \) dan matriks transisi \( P = \left[\begin{matrix} 0 & 1 \\ 0 & 1\end{matrix}\right] \). Jadi, keadaan 0 dapat mencapai 1 secara deterministik dalam satu langkah, sedangkan keadaan 1 menyerap. Untuk relasi ketercapaian, satu-satunya hubungan adalah \( 0 \to 0 \), \( 0 \to 1 \), dan \( 1 \to 1 \). Dengan demikian, kelas-kelas komunikasinya adalah \( \{0\} \) dan \( \{1\} \).
- Seluruh ruang keadaan \( S \) tertutup, tetapi bukan kelas komunikasi.
- \( \{0\} \) adalah kelas komunikasi, tetapi tidak tertutup.
Di sisi lain, kita mempunyai hasil berikut:
Jika \( A \subseteq S \) tak tereduksi, maka \( A \) adalah kelas komunikasi.
Rincian:
Tetapkan \( x \in A \) (ingat bahwa himpunan tertutup tak kosong berdasarkan definisi). Karena \( A \) tertutup, diperoleh \( [x] \subseteq A \). Karena \( A \) tak tereduksi, \(\cl(\{y\})=A\) untuk setiap \(y\in A\), dan khususnya \(\cl(\{x\})=A\). Karena itu, \( x \leftrightarrow y \) untuk setiap \( y \in A \). Jadi, \( A \subseteq [x] \).
Relasi komunikasi sangat penting karena banyak sifat keadaan yang menarik ternyata merupakan sifat kelas, yang dimiliki bersama oleh semua keadaan dalam suatu kelas komunikasi. Secara khusus, status rekuren atau transien merupakan sifat kelas.
Kelas Komunikasi Transien dan Rekuren
Hasil berikut sangat penting: suatu keadaan rekuren hanya dapat mencapai keadaan rekuren lainnya.
Jika \( x \) adalah keadaan rekuren dan \( x \to y \), maka \( y \) rekuren dan \( H(x, y) = H(y, x) = 1 \).
Rincian:
Hasilnya jelas berlaku jika \( x = y \), sehingga kita mengasumsikan \( x \ne y \). Misalkan \( \alpha(x, y) \) menyatakan probabilitas bahwa rantai yang dimulai pada \( x \) mencapai \( y \) tanpa terlebih dahulu kembali ke \( x \). Harus berlaku \( \alpha(x, y) \gt 0 \) karena \( x \to y \). Dalam graf \( \bs{X} \), jika terdapat lintasan dari \( x \) ke \( y \), maka terdapat lintasan dari \( x \) ke \( y \) tanpa siklus. Rantai yang dimulai pada \( x \) dapat gagal kembali ke \( x \) dengan terlebih dahulu mencapai \( y \) tanpa kembali ke \( x \) di antaranya, lalu dari \( y \) tidak pernah mencapai \( x \). Dari sifat Markov dan sifat homogen terhadap waktu diperoleh \( 1 - H(x, x) \ge \alpha(x, y)[1 - H(y, x)] \ge 0 \). Namun, \( H(x, x) = 1 \), sehingga diperoleh \( H(y, x) = 1 \). Sekarang kita mengetahui bahwa terdapat bilangan bulat positif \( j, \, k \) sedemikian sehingga \( P^j(x, y) \gt 0 \) dan \( P^k(y, x) \gt 0 \). Karena itu, untuk setiap \( n \in \N \), \[ P^{j + k + n}(y, y) \ge P^k(y, x) P^n(x, x) P^j(x, y) \] Ingat bahwa \( G(x, x) = \infty \) karena \( x \) rekuren. Dengan menjumlahkan ketaksamaan yang ditampilkan terhadap \( n \), diperoleh \( G(y, y) = \infty \). Karena itu, \( y \) rekuren. Terakhir, pertukaran peran \( x \) dan \( y \) memberikan \( H(x, y) = 1 \).
Dari teorema ketercapaian dari keadaan rekuren, perhatikan bahwa jika \( x \) rekuren, semua keadaan dalam \( [x] \) juga rekuren. Jadi, dalam setiap kelas komunikasi, semua keadaan bersifat transien atau semua keadaan bersifat rekuren. Oleh karena itu, kita dapat menyebut kelas komunikasi transien atau rekuren, sebagaimana kita menyebut keadaan transien atau rekuren.
Jika \( A \) adalah kelas komunikasi rekuren, maka \( A \) tak tereduksi.
Rincian:
Misalkan \( x \in A \) dan \( x \to y \). Karena \( x \) rekuren, \( y \) juga rekuren dan \( y \to x \). Karena itu, \( x \leftrightarrow y \), sehingga \( y \in A \) karena \( A \) adalah kelas komunikasi. Misalkan \( B \subseteq A \) tertutup. Karena \( B \) tak kosong berdasarkan definisi, terdapat \( x \in B \), sehingga \( x \in A \) pula. Untuk setiap \( y \in A \), \( x \leftrightarrow y \), sehingga \( y \in B \) karena \( B \) tertutup. Jadi, \( A = B \), sehingga \( A \) tak tereduksi.
Jika \( A \) berhingga dan tertutup, maka \( A \) memiliki keadaan rekuren.
Rincian:
Tetapkan \( x \in A \). Karena \( A \) tertutup, diperoleh \( \P(N_A = \infty \mid X_0 = x) = 1 \). Karena \( A \) berhingga, diperoleh \( \P(N_y = \infty \mid X_0 = x) \gt 0 \) untuk suatu \( y \in A \). Namun, hal ini berarti bahwa \( y \) rekuren.
Jika \( A \) berhingga dan tak tereduksi, maka \( A \) adalah kelas komunikasi rekuren.
Rincian:
Perhatikan bahwa \(A\) adalah kelas komunikasi berdasarkan teorema himpunan tak tereduksi, dan \(A\) memiliki keadaan rekuren berdasarkan teorema himpunan berhingga tertutup. Karena itu, semua keadaan dalam \( A \) rekuren.
Dengan demikian, rantai Markov \( \bs{X} \) akan memiliki suatu koleksi (yang mungkin kosong) kelas komunikasi rekuren \( \{A_j: j \in J\} \), dengan \( J \) sebagai himpunan indeks terhitung. Setiap \( A_j \) tak tereduksi. Misalkan \( B \) menyatakan himpunan semua keadaan transien. Himpunan \( B \) mungkin kosong atau terdiri atas sejumlah kelas komunikasi, tetapi struktur kelas dalam \( B \) biasanya tidak penting bagi kita. Jika rantai dimulai dalam \( A_j \) untuk suatu \( j \in J \), rantai tetap berada dalam \( A_j \) selamanya dan mengunjungi setiap keadaan tak hingga kali dengan probabilitas 1. Jika rantai dimulai dalam \( B \), rantai dapat tetap berada dalam \( B \) selamanya (tetapi hanya jika \( B \) tak hingga), atau dapat memasuki salah satu kelas komunikasi rekuren \( A_j \) dan tidak pernah keluar lagi. Namun, dalam kedua kasus itu, rantai hanya mengunjungi setiap keadaan transien tertentu berhingga kali dengan probabilitas 1. Struktur dasar ini dikenal sebagai dekomposisi kanonik rantai dan ditampilkan dalam bentuk grafis di bawah ini. Sisi-sisi dari \( B \) berwarna abu-abu untuk menunjukkan bahwa transisi-transisi tersebut mungkin tidak ada.
Probabilitas Bertahan dan Uji Klasifikasi
Misalkan \(A\) adalah himpunan bagian sejati dari \(S\). Maka
- \(P_A^n(x,A)=\P_x(X_1\in A,\ldots,X_n\in A)\) untuk \(x\in A\) dan \(n\in\N_+\).
- \(\displaystyle\lim_{n\to\infty}P_A^n(x,A)=\P_x(X_1\in A,X_2\in A,\ldots)\) untuk \(x\in A\).
Rincian:
Ingat bahwa \( P_A^n \) berarti \( (P_A)^n \), dengan \( P_A \) sebagai pembatasan \( P \) pada \( A \times A \).
- Hal ini merupakan akibat sifat Markov dan merupakan probabilitas bahwa rantai tetap berada dalam \( A \) setidaknya hingga waktu \( n \), jika dimulai pada \( x \in A \).
- Hal ini diperoleh dari (a) dan teorema kekontinuan untuk kejadian menurun. Besaran ini adalah probabilitas bahwa rantai tetap berada dalam \( A \) selamanya jika dimulai pada \( x \in A \).
Misalkan \( g_A \) menyatakan fungsi yang didefinisikan oleh bagian (b), sehingga \[ g_A(x) = \P(X_1 \in A, X_2 \in A, \ldots \mid X_0 = x), \quad x \in A \] Fungsi probabilitas bertahan \( g_A \) merupakan pelengkap yang menarik bagi matriks pencapaian yang dipelajari di atas. Hasil berikut mencirikan fungsi ini dan memberikan metode yang dapat digunakan untuk menghitungnya, setidaknya dalam beberapa kasus.
Untuk \( A \subset S \), \( g_A \) adalah fungsi terbesar pada \( A \) yang mengambil nilai dalam \( [0, 1] \) dan memenuhi \( g = P_A g \). Selain itu, \( g_A = \bs{0}_A \) atau \( \sup\{g_A(x): x \in A\} = 1 \).
Rincian:
Perhatikan bahwa \( P_A^{n+1} \bs{1}_A = P_A P_A^n \bs{1}_A\) untuk \( n \in \N \). Dengan mengambil limit ketika \( n \to \infty \) dan menggunakan teorema konvergensi terbatas, diperoleh \( g_A = P_A g_A \). Misalkan sekarang \( g \) adalah fungsi pada \( A \) yang mengambil nilai dalam \( [0, 1] \) dan memenuhi \( g = P_A g \). Maka \( g \le \bs{1}_A \), sehingga \( g \le P_A^n \bs{1}_A \) untuk semua \( n \in \N \). Dengan membiarkan \( n \to \infty \), diperoleh \( g \le g_A \). Selanjutnya, misalkan \( c = \sup\{g_A(x): x \in A\} \). Maka \( g_A \le c \, \bs{1}_A \), sehingga \( g_A \le c \, P_A^n \bs{1}_A \) untuk setiap \( n \in \N \). Dengan membiarkan \( n \to \infty \), diperoleh \( g_A \le c \, g_A \). Karena itu, \( g_A = \bs{0}_A \) atau \( c = 1 \).
Pencirian dalam teorema fungsi bertahan terbesar menyiratkan sejenis hukum nol–satu: probabilitas bertahan selamanya dalam \( A \) bernilai 0 dari setiap keadaan awal \( x \in A \), atau nilainya dapat dibuat sedekat mungkin dengan 1 dengan memilih keadaan awal yang sesuai dalam \( A \). Dua hasil berikut menghubungkan fungsi bertahan dengan rekurensi.
Misalkan \( \bs{X} \) adalah rantai tak tereduksi dan rekuren dengan ruang keadaan \( S \). Maka \( g_A = \bs{0}_A \) untuk setiap himpunan bagian sejati \( A \) dari \( S \).
Rincian:
Tetapkan \( y \notin A \) dan perhatikan bahwa \( 0 \le g_A(x) \le 1 - H(x, y) \) untuk setiap \( x \in A \). Namun, \( H(x, y) = 1 \) karena rantai tak tereduksi dan rekuren. Karena itu, \( g_A(x) = 0 \) untuk \( x \in A \).
Misalkan \( \bs{X} \) adalah rantai Markov tak tereduksi dengan ruang keadaan \( S \) dan matriks probabilitas transisi \( P \). Jika terdapat keadaan \( x \) sedemikian sehingga \( g_A = \bs{0}_A \), dengan \( A = S \setminus \{x\} \), maka \( \bs{X} \) rekuren.
Rincian:
Dengan \( A \) seperti yang didefinisikan di atas, perhatikan bahwa \(1 - H(x, x) = \sum_{y \in A} P(x, y) g_A(y) \). Karena itu, \( H(x, x) = 1 \), sehingga \( x \) rekuren. Karena \( \bs{X} \) tak tereduksi, diperoleh bahwa \( \bs{X} \) rekuren.
Secara lebih umum, misalkan \( \bs{X} \) adalah rantai Markov dengan ruang keadaan \( S \) dan matriks probabilitas transisi \( P \). Dua teorema terakhir dapat digunakan untuk menguji apakah suatu kelas komunikasi tak tereduksi \( C \) rekuren atau transien. Kita menetapkan suatu keadaan \( x \in C \) dan menetapkan \( A = C \setminus \{x\} \). Kemudian kita mencoba menyelesaikan persamaan \( g = P_A g \) pada \( A \). Jika satu-satunya solusi yang mengambil nilai dalam \( [0, 1] \) adalah \( \bs{0}_A \), kelas \( C \) rekuren berdasarkan uji klasifikasi melalui fungsi bertahan. Jika terdapat solusi tak trivial, \( C \) transien. Kita sering mencoba memilih \( x \) agar perhitungannya mudah.
Menghitung Probabilitas Pencapaian dan Potensial
Sekarang kita telah mengetahui cukup banyak tentang rantai Markov dan sering kali dapat mengklasifikasikan keadaan serta menghitung besaran yang menjadi perhatian. Namun, kita belum mengetahui cara menghitung:
- \( G(x, y) \) ketika \( x \) dan \( y \) transien
- \( H(x, y) \) ketika \( x \) transien dan \( y \) transien atau rekuren.
Kedua masalah ini berkaitan melalui hubungan yang dapat dibalik antara matriks \( H \) dan \( G \) yang dibahas di atas. Seperti biasa, misalkan \( \bs{X} \) adalah rantai Markov dengan ruang keadaan \( S \), dan misalkan \( B \) menyatakan himpunan keadaan transien. Hasil berikut menunjukkan cara menghitung \( G_B \), yaitu pembatasan matriks \( G \) pada keadaan-keadaan transien. Semua entri matriks ini berhingga.
\( G_B \) memenuhi persamaan \( G_B = P_B + P_B G_B \) dan merupakan solusi nonnegatif terkecil. Jika \( B \) berhingga, maka \( G_B = (I_B - P_B)^{-1} P_B \).
Rincian:
Pertama, perhatikan bahwa \( (P^n)_B = (P_B)^n \) karena lintasan di antara dua keadaan transien hanya dapat melalui keadaan transien lainnya. Jadi, \( G_B = \sum_{n=1}^\infty P_B^n \). Dari teorema konvergensi monoton diperoleh \( P_B G_B = G_B - P_B \). Misalkan sekarang \( U \) adalah matriks nonnegatif pada \( B \) yang memenuhi \( U = P_B + P_B U \). Maka \( U = \sum_{k=1}^n P_B^k + P_B^{n+1} U \) untuk setiap \( n \in \N_+\). Karena itu, \( U \ge \sum_{k=1}^n P_B^k \) untuk setiap \( n \in \N_+ \), sehingga \( U \ge G_B \). Diperoleh \( (I_B - P_B)(I_B + G_B) = I_B \). Jika \( B \) berhingga, matriks \( I_B - P_B \) dapat dibalik.
Setelah dapat menghitung \( G_B \), kita juga dapat menghitung \(H_B\) menggunakan hubungan Green–pencapaian bagi keadaan transien. Yang tersisa hanyalah menghitung probabilitas pencapaian \( H(x, y) \) ketika \( x \) transien dan \( y \) rekuren. Hal pertama yang perlu diperhatikan ialah bahwa probabilitas pencapaian merupakan sifat kelas.
Misalkan \( x \) transien dan \( A \) merupakan kelas komunikasi rekuren. Maka \( H(x, y) = H(x, A) \) untuk \( y \in A \).
Artinya, jika dimulai dari keadaan transien \( x \in S \), probabilitas pencapaian ke \( y \) bernilai konstan untuk \( y \in A \), dan nilainya sama dengan probabilitas pencapaian ke kelas \( A \). Seperti sebelumnya, misalkan \( B \) menyatakan himpunan keadaan transien dan \( A \) merupakan kelas komunikasi rekuren. Misalkan \( h_A \) menyatakan fungsi pada \( B \) yang memberikan probabilitas pencapaian ke kelas \( A \), dan \( p_A \) menyatakan fungsi pada \( B \) yang memberikan probabilitas memasuki \( A \) pada langkah pertama: \[ h_A(x) = H(x, A), \; p_A(x) = P(x, A), \quad x \in B \]
\( h_A = p_A + G_B p_A \).
Rincian:
Pertama, perhatikan bahwa \( \P(\tau_A = n \mid X_0 = x) = (P_B^{n-1} p_A)(x) \) untuk \( n \in \N_+ \). Hasilnya kemudian diperoleh dengan menjumlahkan terhadap \( n \).
Rumus pencapaian kelas rekuren memadai jika kita telah menghitung \(G_B\) (misalnya dengan menggunakan persamaan matriks Green transien). Namun, kita mungkin ingin menghitung \( h_A \) secara langsung.
\( h_A \) memenuhi persamaan \( h_A = p_A + P_B h_A \) dan merupakan solusi nonnegatif terkecil. Jika \( B \) berhingga, maka \( h_A = (I_B - P_B)^{-1} p_A \).
Rincian:
Pertama, pengondisian pada \( X_1 \) memberikan \( h_A = p_A + P_B h_A \). Selanjutnya, misalkan \( h \) nonnegatif dan memenuhi \( h = p_A + P_B h \). Maka \( h = p_A + \sum_{k=1}^{n-1} P_B^k p_A + P_B^n h \) untuk setiap \( n \in \N_+ \). Karena itu, \( h \ge p_A + \sum_{k=1}^{n-1} P_B^k p_A \). Dengan membiarkan \( n \to \infty \), diperoleh \( h \ge h_A \). Representasi untuk \( B \) berhingga diperoleh dari persamaan matriks Green transien.
Contoh dan Penerapan
Rantai Markov Berhingga
Pertimbangkan rantai Markov dengan ruang keadaan \( S = \{a, b, c, d\} \) dan matriks transisi \( P \) berikut:
\[ P = \left[ \begin{matrix} \frac{1}{3} & \frac{2}{3} & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \end{matrix} \right] \]- Gambarkan graf keadaannya.
- Tentukan kelas-kelas komunikasi dan klasifikasikan setiap kelas sebagai transien atau rekuren.
- Hitung matriks \( G \).
- Hitung matriks \( H \).
Rincian:
-
Graf keadaan 
- \( \{a, b\} \) rekuren; \( \{c\} \) rekuren; \( \{d\} \) transien.
- \[ G=\begin{bmatrix} \infty&\infty&0&0\\ \infty&\infty&0&0\\ 0&0&\infty&0\\ \infty&\infty&\infty&\frac13 \end{bmatrix}. \]
- \[ H=\begin{bmatrix} 1&1&0&0\\ 1&1&0&0\\ 0&0&1&0\\ \frac23&\frac23&\frac13&\frac14 \end{bmatrix}. \]
Pertimbangkan rantai Markov dengan ruang keadaan \( S = \{1, 2, 3, 4, 5, 6\} \) dan matriks transisi \( P \) berikut:
\[ P = \left[ \begin{matrix} 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{1}{4} & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{3} & 0 & \frac{2}{3} & 0 \\ 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} \end{matrix} \right] \]- Buatlah sketsa graf keadaannya.
- Tentukan kelas-kelas komunikasi dan klasifikasikan setiap kelas sebagai rekuren atau transien.
- Hitung matriks \( G \).
- Hitung matriks \( H \).
Rincian:
-
Graf keadaan 
- \( \{1, 3, 5\} \) rekuren; \( \{2, 6\} \) transien; \( \{4\} \) rekuren.
- \[ G=\begin{bmatrix} \infty&0&\infty&0&\infty&0\\ \infty&\frac12&\infty&\infty&\infty&2\\ \infty&0&\infty&0&\infty&0\\ 0&0&0&\infty&0&0\\ \infty&0&\infty&0&\infty&0\\ \infty&\frac12&\infty&\infty&\infty&1 \end{bmatrix}. \]
- \[ H=\begin{bmatrix} 1&0&1&0&1&0\\ \frac12&\frac13&\frac12&\frac12&\frac12&1\\ 1&0&1&0&1&0\\ 0&0&0&1&0&0\\ 1&0&1&0&1&0\\ \frac12&\frac13&\frac12&\frac12&\frac12&\frac12 \end{bmatrix}. \]
Pertimbangkan rantai Markov dengan ruang keadaan \( S = \{1, 2, 3, 4, 5, 6\} \) dan matriks transisi \( P \) berikut:
\[ P = \left[ \begin{matrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0 & 0 \\ \frac{1}{4} & 0 & \frac{1}{2} & \frac{1}{4} & 0 & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{matrix} \right] \]- Buatlah sketsa graf keadaannya.
- Tentukan kelas-kelas komunikasi dan klasifikasikan setiap kelas sebagai rekuren atau transien.
- Hitung matriks \( G \).
- Hitung matriks \( H \).
Rincian:
-
Graf keadaan 
- \( \{1, 2\} \) rekuren; \( \{3, 4\} \) transien; \( \{5, 6\} \) rekuren.
- \[ G=\begin{bmatrix} \infty&\infty&0&0&0&0\\ \infty&\infty&0&0&0&0\\ \infty&\infty&\frac75&\frac45&\infty&\infty\\ \infty&\infty&\frac45&\frac35&\infty&\infty\\ 0&0&0&0&\infty&\infty\\ 0&0&0&0&\infty&\infty \end{bmatrix}. \]
- \[ H=\begin{bmatrix} 1&1&0&0&0&0\\ 1&1&0&0&0&0\\ \frac45&\frac45&\frac7{12}&\frac12&\frac15&\frac15\\ \frac35&\frac35&\frac13&\frac38&\frac25&\frac25\\ 0&0&0&0&1&1\\ 0&0&0&0&1&1 \end{bmatrix}. \]
Model Khusus
Sifat transien dan rekuren, serta probabilitas pencapaian, penting bagi setiap model khusus yang dipelajari pada bagian-bagian selanjutnya: