Rantai Markov Waktu Diskrit

Rantai Markov waktu diskrit adalah urutan keadaan acak yang berkembang dalam waktu bilangan bulat sehingga distribusi keadaan berikutnya hanya bergantung pada keadaan saat ini, bukan pada keseluruhan masa lalu.

Definition

Rantai Markov waktu diskrit adalah proses stokastik pada ruang keadaan terhitung yang diindeks oleh bilangan bulat non-negatif yang distribusi bersyarat keadaan berikutnya, mengingat seluruh riwayat, hanya bergantung pada keadaan saat ini, yang dikodekan oleh matriks probabilitas transisi satu langkah.

Scope

Area ini mencakup sifat Markov dan matriks transisi, klasifikasi keadaan berdasarkan komunikasi, rekurensi, transiensi, dan periodisitas, keberadaan dan keunikan distribusi stasioner dan pembatas, tingkat konvergensi dan pencampuran, serta aplikasi utama termasuk Monte Carlo rantai Markov dan model Markov tersembunyi.

Sub-topics

• Model Markov Tersembunyi
• Klasifikasi dan Rekurensi Rantai Markov
• Markov Chain Monte Carlo
• Distribusi Stasioner dan Konvergensi

Core questions

• Apa arti sifat Markov dan bagaimana sifat ini ditangkap oleh matriks transisi?
• Bagaimana keadaan diklasifikasikan menjadi kelas rekuren, transien, dan periodik?
• Kapan suatu rantai memiliki distribusi stasioner yang unik dan konvergen kepadanya?
• Seberapa cepat suatu rantai mendekati ekuilibrium, dan bagaimana hal ini dimanfaatkan dalam simulasi?

Key theories

Sifat Markov dan persamaan Chapman-Kolmogorov

Masa depan secara kondisional independen dari masa lalu mengingat masa kini, sehingga probabilitas transisi multi-langkah diperoleh dengan mengalikan matriks transisi, yang membuat perilaku n-langkah dapat dihitung dari matriks satu langkah.

Teorema Ergodik untuk rantai Markov

Rantai yang ireduksi, aperiodik, dan rekuren positif memiliki distribusi stasioner unik yang kepadanya distribusi marjinal konvergen dan terhadapnya rata-rata waktu fungsi konvergen hampir pasti, menghubungkan frekuensi jangka panjang dengan hukum stasioner.

Clinical relevance

Rantai Markov waktu diskrit memodelkan langkah acak, cuplikan antrean, genetika populasi, algoritma peringkat seperti PageRank, dan transisi keadaan ekonomi; teori konvergensinya mendasari Monte Carlo rantai Markov, metode komputasi dominan untuk pengambilan sampel dari distribusi probabilitas kompleks di seluruh statistik, fisika, dan pembelajaran mesin.

History

Andrey Markov memperkenalkan rantai dengan transisi yang bergantung tetapi tanpa memori pada tahun 1906 untuk memperluas hukum bilangan besar di luar independensi, mengilustrasikannya dengan urutan huruf dalam puisi Pushkin. Kolmogorov dan Doeblin menempatkan teori konvergensi pada fondasi teori ukuran yang ketat pada tahun 1930-an.

Key figures

• Andrey Markov
• Andrey Kolmogorov
• Wolfgang Doeblin

Seminal works

• norris1997

Frequently asked questions

Apa yang membuat suatu proses menjadi rantai Markov?

Sifat Markov: mengingat keadaan saat ini, evolusi masa depan independen dari bagaimana rantai mencapai keadaan tersebut, sehingga seluruh dinamika dijelaskan oleh probabilitas transisi satu langkah.

Kapan rantai Markov konvergen ke distribusi jangka panjang yang unik?

Ketika rantai tersebut ireduksi, aperiodik, dan rekuren positif; maka ada satu distribusi stasioner tunggal yang kepadanya rantai konvergen terlepas dari keadaan awalnya.