Apa itu rantai Markov?

9

Saat ini saya membaca beberapa makalah tentang penggumpalan rantai Markov dan saya gagal melihat perbedaan antara rantai Markov dan grafik tertimbang sederhana yang diarahkan.

Sebagai contoh dalam artikel Optimal penggumpalan ruang-negara di rantai Markov, mereka memberikan definisi CTMC (rantai Markov waktu kontinu) sebagai berikut:

Kami menganggap CTMC terbatas dengan ruang state oleh matriks laju transisi .S = { x 1 , x 2 , , x n } Q : S × SR +(S,Q)S={x1,x2,,xn}Q:S×SR+

Mereka tidak menyebutkan properti Markov sama sekali, dan, pada kenyataannya, jika bobot di tepi mewakili probabilitas saya percaya properti Markov sepele memegangnya karena probabilitas hanya bergantung pada keadaan rantai saat ini dan bukan jalur yang mengarah untuk itu.

Dalam artikel lain Pada Relational Properties of Lumpability, rantai Markov didefinisikan dengan cara yang sama:

Rantai Markov akan direpresentasikan sebagai triplet mana adalah himpunan terbatas dari keadaan , matriks probabilitas transisi yang menunjukkan probabilitas untuk berpindah dari satu keadaan ke keadaan lain, dan adalah distribusi probabilitas awal yang mewakili kemungkinan sistem mulai dalam keadaan tertentu.( S , P , π ) S M P πM(S,P,π)SMPπ

Sekali lagi, tidak disebutkan masa lalu atau masa depan atau kemerdekaan.

Ada makalah ketiga Simple O (m logn) Time Markov Chain Lumping di mana mereka tidak hanya tidak pernah menyatakan bahwa bobot pada tepian adalah probabilitas, tetapi mereka bahkan mengatakan:

Dalam banyak aplikasi, nilai tidak negatif. Namun, kami tidak membuat asumsi ini, karena ada juga aplikasi di mana sengaja dipilih sebagai , sehingga biasanya negatif.W ( s , s ) - W ( s , S { s } )W(s,s)W(s,s)W(s,S{s})

Selain itu, dinyatakan bahwa lumping harus menjadi cara untuk mengurangi jumlah negara sambil mempertahankan properti Markov (dengan menggabungkan negara "setara" menjadi negara yang lebih besar). Namun, bagi saya, sepertinya itu hanya menjumlahkan probabilitas dan bahkan seharusnya tidak menjamin bahwa kemampuan transisi yang dihasilkan ke / dari keadaan agregat berada dalam kisaran . Apa sebenarnya yang dipertahankan benjolan itu?[0,1]

Jadi, ada dua kemungkinan yang saya lihat:

  • Saya tidak mengerti apa itu rantai Markov, atau
  • Penggunaan istilah rantai Markov di koran-koran itu palsu

Bisakah seseorang mengklarifikasi situasinya?

Sepertinya ada banyak komunitas yang menggunakan istilah itu dan mereka sangat berbeda. Dari 3 artikel yang saya pertimbangkan ini sepertinya properti Markov adalah sepele atau tidak berguna, sambil melihat berbagai jenis kertas yang terlihat mendasar.

Bakuriu
sumber
Ada banyak buku teks dan sumber daya di Internet yang menjelaskan (a) apa rantai Markov itu dan (b) apa definisi matematika yang tepat. Kami berharap Anda melakukan sejumlah besar penelitian dan studi mandiri sebelum bertanya. Jadi, sudahkah Anda berkonsultasi dengan salah satu sumber daya itu? Apa yang kamu temukan di sana? PS Saya kira makalah dalam literatur akan mengasumsikan Anda tahu definisi rantai Markov, dan kalimat-kalimat itu tidak harus dimaksudkan sebagai definisi formal yang tepat dari rantai Markov, melainkan hanya untuk menetapkan notasi yang mereka gunakan ketika berbicara sekitar satu.
DW
Masa lalu atau masa depan atau kemerdekaan adalah properti yang mengikuti, iirc. Namun, harus ada pembatasan berat; mungkin beberapa hal bisa tetap tersirat, misalnya menetapkan bobot keluar yang hilang ke tepi yang mengarah ke keadaan tenggelam (lih. definisi DFA berbeda).
Raphael
4
@ DW Ya saya lakukan. Apa yang saya temukan adalah bahwa gagasan rantai Markov di buku teks tampaknya tidak ada hubungannya dengan konsep itu seperti yang digunakan dalam makalah tersebut. Inilah mengapa saya menanyakan hal ini.
Bakuriu
4
Sekali lagi, ada kemungkinan ketiga. Saya pikir kesalahan yang Anda buat adalah menafsirkan pernyataan di koran-koran itu sebagai definisi rantai Markov. Saya kira itu mungkin bukan maksud dari pernyataan itu. Saya kira para penulis menganggap Anda sudah terbiasa dengan definisi rantai Markov, dan hanya mencoba untuk membangun beberapa notasi (ada beberapa jenis notasi yang dapat Anda gunakan untuk konsep yang sama). Jadi, coba lihat lagi dari sudut pandang itu dan lihat apakah Anda menemukan sesuatu yang bertentangan di koran (jika Anda menemukan, tambahkan ke pertanyaan).
DW
4
@ DW Sepertinya OP melakukan penelitian yang layak dan menyusun pertanyaannya dengan baik. Ya kita bisa menggunakan google untuk belajar. Tetapi apakah Anda memperhatikan seberapa tinggi peringkat situs SE di google? Itu karena kami memadatkan informasi menjadi (biasanya) pertanyaan tunggal yang didefinisikan dengan baik. Upaya kolaboratif dari komunitas kami membuat konten yang sangat kaya dan berharga, yang berkali-kali, lebih bermanfaat daripada halaman dan halaman info di luar sana menghasilkan pembelajaran yang lebih efisien.
BAR

Jawaban:

10

Sebuah Continuous-waktu Markov Chain dapat direpresentasikan sebagai grafik diarahkan dengan konstan bobot tepi non-negatif. Representasi yang setara dari bobot tepi konstan grafik berarah dengan node adalah sebagai matriksThe Markov properti (bahwa masa depan negara tergantung hanya pada keadaan saat ini) adalah implisit dalam bobot tepi konstan (atau entri konstan dalam matriks). Implisit berarti tersirat oleh . Matematikawan menggunakannya sebagai makna eufemisme, "Anda harus membuktikannya sendiri."N × NNN×N

Tetapi kertas pertama mendefinisikan notasi yang konsisten dengan Rantai Markov waktu-berkelanjutan , kadang-kadang disebut Proses Markov , sedangkan kertas kedua mendefinisikan notasi yang konsisten dengan Rantai Markov waktu diskrit . Mereka bilang

πP adalah matriks probabilitas transisi yang menunjukkan probabilitas untuk berpindah dari satu keadaan ke keadaan lain, dan adalah distribusi probabilitas awal yang mewakili kemungkinan sistem memulai dalam keadaan tertentu. [penekanan ditambahkan]π

Mereka mengasumsikan bahwa matriks konstan dari waktu ke waktu (sehingga menyiratkan properti Markov). Tersirat dalam probabilitas istilah adalah kenyataan bahwa setiap konstanta dalam kisaran , bahwa entri dalam setiap kolom jumlah ke , dan bahwa jumlah entri dalam jumlah ke .P 1 π 1[0,1]P1π1

Saya tidak bisa membaca makalah ketiga, itu paywalled. Jika entri dalam setiap kolom dari matriks diharuskan untuk menjumlahkan ke 1 maka mereka adalah probabilitas dan mereka berbicara tentang Rantai Markov waktu diskrit. Jika entri di setiap kolom dapat jumlah ke angka sewenang-wenang maka entri mewakili tingkat bukan probabilitas dan mereka berbicara tentang Rantai Markov waktu-berkelanjutan.

1

Dengan Chains Markov Continous-time dan Discrete-time, properti Markov tersirat oleh bobot tepi konstan (atau setara dengan entri konstan dalam matriks transisi).

Logika Pengembaraan
sumber
8

Rantai Markov datang dalam dua rasa: waktu kontinu dan waktu diskrit.

Baik rantai markov waktu kontinu (CTMC) dan rantai markov waktu diskrit (DTMC) direpresentasikan sebagai grafik tertimbang yang diarahkan.

Untuk DTMC, transisinya selalu membutuhkan satu unit "waktu". Akibatnya, tidak ada pilihan untuk berapa berat Anda pada busur seharusnya - Anda menempatkan kemungkinan pergi ke "j" mengingat bahwa Anda berada di "i."

Untuk CTMC, waktu transisi antara dua keadaan harus diberikan oleh variabel acak eksponensial. Ini adalah perbedaan utama antara CTMC dan DTMC: DTMC selalu memiliki waktu transisi unit. CTMC memiliki waktu transisi acak.

Untuk CTMC, konvensi umumnya untuk meletakkan bobot pada busur sesuai dengan tingkat variabel acak eksponensial pergi dari sumber ke tujuan. Itu adalah - konvensi adalah untuk memberi nilai pada busur, bukan probabilitas.

Tarif Negatif

Meskipun semua CTMC yang saya ingat diwakili dengan tingkat positif di tepinya, tingkat negatif muncul dalam analisis CTMC.

Katakanlah kita berdiri di negara A, yang terhubung ke B, C, dan D seperti di bawah ini.

A -> B (laju ke A dari B negatif) A -> C (laju ke A dari C negatif) D -> A (laju ke A dari D adalah positif)

Ini kemungkinan tidak sesuai dengan makalah Anda; Saya membawanya untuk menunjukkan bahwa bobot negatif tidak selalu konyol jika seseorang bekerja dengan konvensi yang sesuai.

Markov Property

Untuk DTMC - Anda benar. Properti markov puas sepele. Untuk CTMC, properti markov puas karena transisi diberikan oleh variabel acak eksponensial (yang "tanpa memori"). Jika transisi tidak diberikan oleh variabel acak eksponensial (katakan saja mereka seragam), maka kita akan berbicara tentang "Rantai Semi-Markov" atau "Proses Semi-Markov."

Riley
sumber
W(s,s)W(s,S{s})s
W(s,s)=W(s,S{s})