Kita memulai bagian ini dengan sebuah contoh yang memberikan motivasi. Tinjau graf terhubung dengan enam simpul yang ditampilkan pada [provisional cross-reference: fig-markovchain]. Langkah pertama adalah memilih satu simpul secara acak dan berpindah ke sana. Setelah itu, kita mengikuti prosedur rekursif berikut. Jika setelah \(i\) langkah Anda berada di simpul \(x\) dan \(x\) mempunyai \(d\) tetangga, pilih salah satu tetangga secara acak, masing-masing dengan probabilitas \(1/d\text{,}\) lalu berpindahlah ke sana. Selanjutnya, kita mencoba menjawab pertanyaan-pertanyaan seperti berikut:
Untuk setiap simpul \(x\text{,}\) misalkan \(p_{x,m}\) menyatakan probabilitas bahwa Anda berada di simpul \(x\) setelah \(m\) langkah. Apakah \(\lim_{m\rightarrow\infty}p_{x,m}\) ada, dan jika ada, seberapa cepat barisan tersebut konvergen ke limit ini?
Jika Anda berada dalam keadaan \(S_j\) pada waktu \(i\text{,}\) maka untuk setiap \(k=1,2,\dots,n\text{,}\) terdapat probabilitas tetap \(p(j,k)\) yang tidak bergantung pada \(i\) bahwa Anda akan berada dalam keadaan \(S_k\) pada waktu \(i+1\text{.}\)
Matriks \(n\times n\)\(P\) yang entri \(j,k\)-nya merupakan probabilitas \(p(j,k)\) untuk berpindah dari keadaan \(S_j\) ke keadaan \(S_k\) disebut matriks transisi rantai Markov tersebut. Perhatikan bahwa \(P\) merupakan matriks stokastik, i.e., semua entrinya tak negatif dan jumlah setiap baris adalah \(1\text{.}\) Sebaliknya, setiap matriks stokastik persegi dapat dipandang sebagai matriks transisi suatu rantai Markov.
Suatu matriks transisi \(P\) disebut reguler jika terdapat bilangan bulat \(m\) sehingga matriks \(P^m\) hanya mempunyai entri positif. Berikut sebuah hasil mendasar dalam bidang ini yang mudah dipahami, tetapi sedikit terlalu rumit untuk dibuktikan dalam ruang yang tersedia.
Misalkan \(P\) matriks transisi reguler berukuran \(n\times n\text{.}\) Terdapat vektor baris \(W=(w_1, w_2,\dots,w_n)\) yang terdiri atas bilangan real positif dengan jumlah \(1\) sedemikian sehingga, ketika \(m\) menuju tak hingga, setiap baris \(P^m\) menuju \(W\text{.}\) Selain itu, \(WP=W\text{,}\) dan untuk setiap \(i=1,2,\dots,n\text{,}\) nilai \(w_i\) merupakan probabilitas limit untuk berada dalam keadaan \(S_i\text{.}\)
Berdasarkan pernyataan Teorema 16.9, vektor baris \(W\) dapat dihitung dengan teknik nilai eigen yang termasuk dalam mata kuliah aljabar linear standar tingkat sarjana. Sebagai contoh, matriks transisi \(P\) yang ditampilkan dalam (16.3.1) bersifat reguler karena semua entri \(P^3\) positif. Untuk matriks ini, vektor barisnya adalah \(W=(5/13, 3/13, 2/13, 2/13, 1/13, 1/13)\text{.}\) Namun, pertanyaan tentang seberapa cepat \(P^m\) konvergen ke vektor limit tersebut lebih rumit, demikian pula pertanyaan tentang berapa lama waktu yang diperlukan agar kita cukup yakin telah melakukan setiap transisi yang mungkin.
Suatu keadaan \(S_i\) dalam rantai Markov bermatriks transisi \(P\) disebut menyerap jika \(p_{i,i}=1\) dan \(p_{i,j}=0\) untuk semua \(j\neq i\text{,}\) i.e., seperti Hotel California yang terkenal buruk itu, begitu Anda berada dalam keadaan \(S_i\text{,}\) “Anda tidak akan pernah dapat pergi.”
Sekarang kita dapat meninjau permainan berikut. Mulailah pada salah satu dari empat simpul dalam \(\{1,2,3,4\}\text{,}\) lalu lanjutkan seperti sebelumnya dengan berpindah melalui pemilihan tetangga secara acak. Simpul \(4\) dapat dipandang sebagai titik “pelarian”, suatu tempat berlindung yang tidak pernah ditinggalkan setelah dicapai. Di sisi lain, simpul \(5\) mungkin merupakan tempat seseorang bertemu harimau lapar dan terserap dengan cara yang tidak perlu dirinci di sini.
Rantai Markov disebut menyerap jika terdapat paling sedikit satu keadaan menyerap dan, bagi setiap keadaan \(S_j\) yang tidak menyerap, suatu keadaan menyerap dapat dicapai—meskipun mungkin diperlukan banyak langkah. Jenis pertanyaan yang ingin kita jawab kini adalah:
Jika kita mulai dalam keadaan tak menyerap \(S_i\text{,}\) berapakah probabilitas mencapai keadaan menyerap \(S_j\) dan kemudian terserap dalam keadaan tersebut, suatu pertanyaan yang menjadi sungguh tidak menyenangkan jika dikaitkan dengan harimau?
