Aljabar Linear · Rantai Markov

Rantai Markov

Rantai Markov berpindah keadaan secara acak. Peluang keadaan berikutnya hanya bergantung pada keadaan sekarang. Dalam matriks transisi P, distribusi besok adalah distribusi hari ini dikalikan P. Pengulangan sering menghasilkan distribusi stasioner π dengan πP = π, vektor eigen kiri untuk nilai eigen 1.

Rantai Markov dalam visualisasi ini

Dalam rantai Markov, peluang keadaan berikutnya hanya bergantung pada keadaan sekarang. Di sini keadaannya cerah, mendung, dan hujan. Baris ii pada matriks transisi PP memuat peluang besok jika keadaan hari ini ii. Tiap baris adalah vektor peluang. Jika distribusi hari ini vektor baris pp, besok distribusinya pPpP dan setelah nn hari pn=p0Pnp_n = p_0 P^n. Untuk tiga keadaan, setiap distribusi adalah titik dalam segitiga. Satu sudut berarti satu keadaan pasti, dan peluangnya adalah bobot ketiga sudut. Titik gelap mewakili baris PP, titik biru distribusi awal, dan lintasan merah menghubungkan p0,p1,p2,…p_0, p_1, p_2, \dots.

Apa yang terjadi dalam satu langkah?

Satu langkah memetakan tiap sudut ke barisnya: setelah hari yang pasti cerah, distribusinya adalah baris pertama. Distribusi lain pp adalah rata-rata berbobot dari sudut, jadi pPpP adalah rata-rata baris dengan bobot yang sama. Seluruh segitiga masuk ke segitiga yang direntang baris-baris itu; setelah dua langkah masuk ke segitiga baris P2P^2. Bila suatu pangkat PP memiliki semua entri positif, segitiga bersarang ini menyusut ke satu titik, yaitu distribusi stasioner π\pi.

Mengapa π vektor eigen dan seberapa cepat pₙ mendekatinya?

Titik tetap memenuhi πP=π\pi P = \pi: π\pi adalah vektor eigen untuk nilai eigen 1, tepatnya vektor eigen kiri (dalam bentuk kolom, PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}). Jumlah entri selisih p0−πp_0 - \pi adalah 0. Pada subruang itu, PP memiliki dua nilai eigen lainnya, λ2,λ3\lambda_2, \lambda_3. Satu langkah mengalikan vektor di setiap arah eigen dengan nilai eigennya. Bila kedua modulus kurang dari 1, pnp_n mendekati π\pi dan modulus terbesar ∣λ2∣|\lambda_2| menentukan laju. Untuk rantai cuaca, ∣λ2∣≈0.462|\lambda_2| \approx 0.462. Saat nn besar, tersisa sedikit kurang dari separuh jarak per langkah jika ada komponen awal searah λ2\lambda_2. Dengan nilai eigen kompleks, lintasan juga berputar saat menyusut.

Kapan distribusi tidak konvergen?

Dalam siklus, cerah, mendung, dan hujan berulang. Kedua nilai eigen lainnya bermodulus 1 dan pnp_n terus berputar kecuali dimulai di π\pi. Dengan dua keadaan penyerap, cerah dan hujan masing-masing bertahan. Nilai eigen 1 muncul dua kali dan semua campuran cerah dan hujan tetap, sehingga pnp_n konvergen tetapi limitnya bergantung pada awal. Untuk rantai hingga, pnp_n mendekati π\pi yang sama dari setiap awal jika dan hanya jika ada tepat satu kelas tertutup yang saling berkomunikasi dan kelas itu aperiodik. Semua keadaan di kelas itu dapat saling mencapai tanpa bisa keluar. Salah satu syarat yang cukup ialah semua entri suatu pangkat PmP^m positif.

Hal yang perlu diperhatikan

  • Untuk rantai cuaca, distribusi stasioner memberi peluang cuaca pada hari yang jauh di masa depan dari awal apa pun. Cuacanya sendiri tetap berubah dari hari ke hari.
  • Dengan lebih dari tiga keadaan, distribusi mengisi simpleks berdimensi lebih tinggi, padanan segitiga. Penjelasan yang sama tetap berlaku.

Kontrol

  • Geser titik gelap untuk mengubah baris matriks transisi atau titik biru untuk mengubah awal. Tombol panah menggeser titik yang mendapat fokus sebesar 0.01.

Terkait