Kuis Latihan Rantai Markov & Proses Stokastik dengan Pelajaran Interaktif Langkah demi Langkah
Gunakan kuis di bagian bawah halaman untuk berlatih rantai Markov dan proses stokastik: sifat Markov, matriks transisi stokastik baris, pembaruan distribusi \(pP\), pangkat \(P^n\), hukum Chapman-Kolmogorov, distribusi stasioner \(\pi P=\pi\), keadaan penyerap dan kelas tertutup, ketaktereduksian, rekurensi dan sifat transien, periode dan aperiodisitas, konvergensi rantai hingga, martingale, submartingale, supermartingale, filtrasi, dan waktu henti. Jika Anda perlu penyegaran, buka pelajaran untuk contoh yang jelas dan cek cepat.
Jawab rangkaian soal dan tinjau kesalahanmu di akhir.
Cara kerja latihan rantai Markov dan proses stokastik ini
1. Kerjakan set latihan: jawab soal tentang probabilitas transisi, distribusi stasioner, rekurensi, periodisitas, martingale, dan waktu henti.
2. Buka pelajaran: tinjau matriks stokastik baris, struktur kelas, perilaku jangka panjang, rantai penyerap, dan alat ekspektasi bersyarat.
3. Coba lagi: kembali ke set soal dan putuskan apakah perlu menghitung entri matriks, menyelesaikan \(\pi P=\pi\), mengklasifikasikan keadaan, atau memeriksa ekspektasi bersyarat.
Yang akan Anda pelajari dalam pelajaran rantai Markov & proses stokastik
Hukum transisi dan pangkat matriks
Baca \(P_{ij}\) sebagai probabilitas berpindah dari keadaan \(i\) ke keadaan \(j\) dalam satu langkah.
Perbarui distribusi vektor baris dengan \(p_{n+1}=p_nP\) dan \(p_n=p_0P^n\).
Gunakan Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
Perilaku stasioner dan jangka panjang
Selesaikan \(\pi P=\pi\) bersama dengan \(\sum_i\pi_i=1\).
Kenali \(\pi\) sebagai vektor eigen kiri dengan nilai eigen \(1\).
Ketahui kapan rantai hingga tak tereduksi dan aperiodik konvergen ke baris stasioner.
Struktur kelas pada rantai hingga
Klasifikasikan kelas berkomunikasi, kelas tertutup, dan keadaan penyerap.
Bedakan keadaan rekuren dari keadaan transien dalam rantai hingga.
Hitung periode dari FPB waktu kembali yang mungkin.
Proses, martingale, dan waktu henti
Gunakan filtrasi \(\mathcal F_n\) untuk merepresentasikan informasi yang diketahui pada waktu \(n\).
Periksa martingale menggunakan \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Kenali bahwa waktu henti harus dapat diputuskan dari informasi masa lalu dan saat ini, bukan data masa depan yang belum terlihat.
Modelkan gerak acak satu langkah demi satu langkah
Tujuan: Bangun perangkat yang andal untuk rantai Markov hingga dan gagasan proses stokastik yang berdekatan. Anda akan membaca matriks transisi, menghitung probabilitas banyak langkah, menyelesaikan distribusi stasioner, mengklasifikasikan keadaan, mengenali perilaku periodik, dan menghubungkan ekspektasi bersyarat dengan martingale serta waktu henti.
Kriteria keberhasilan
Nyatakan sifat Markov: dengan syarat keadaan saat ini diketahui, masa depan tidak memerlukan masa lalu yang lebih awal.
Periksa bahwa matriks transisi hingga bersifat stokastik baris: entrinya tidak negatif dan setiap baris berjumlah \(1\).
Perbarui distribusi vektor baris dengan \(p_{n+1}=p_nP\) dan baca \(P^n_{ij}\) sebagai probabilitas \(n\)-langkah.
Gunakan Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
Selesaikan \(\pi P=\pi\) dengan \(\sum_i\pi_i=1\) untuk distribusi stasioner.
Klasifikasikan keadaan penyerap, kelas berkomunikasi, ketaktereduksian, rekurensi, dan sifat transien.
Temukan periode dari waktu kembali dan ketahui mengapa transisi ke diri sendiri memaksa periode \(1\).
Nyatakan gambaran konvergensi rantai hingga tak tereduksi dan aperiodik.
Kenali martingale, submartingale, supermartingale, dan waktu henti memakai ekspektasi bersyarat serta informasi yang tersedia sejauh ini.
Kosakata kunci
Proses stokastik: barisan variabel acak seperti \(X_0,X_1,X_2,\dots\).
Rantai Markov: proses stokastik yang hukum keadaan berikutnya bergantung pada keadaan saat ini, bukan seluruh masa lalu.
Matriks transisi: \(P_{ij}=\Pr(X_{n+1}=j\mid X_n=i)\), dengan setiap baris berupa distribusi probabilitas.
Distribusi stasioner: distribusi \(\pi\) dengan \(\pi P=\pi\).
Kelas berkomunikasi: keadaan-keadaan yang dapat saling mencapai.
Periode: FPB dari waktu kembali yang mungkin ke suatu keadaan.
Martingale: proses dengan \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Waktu henti: waktu acak yang diputuskan memakai informasi yang tersedia sampai waktu itu.
Cek awal cepat
Cek awal: Dalam rantai Markov, setelah mensyaratkan keadaan saat ini, masa depan satu langkah bergantung pada apa?
Petunjuk: Masa lalu dapat memengaruhi masa depan melalui keadaan saat ini, tetapi setelah keadaan saat ini diketahui, keadaan sebelumnya tidak menambahkan informasi ekstra untuk hukum langkah berikutnya.
Baris mengodekan probabilitas satu langkah
Tujuan pembelajaran: Baca matriks transisi hingga dan hitung distribusi satu langkah atau banyak langkah tanpa kehilangan konvensi probabilitas.
Ide utama
Dengan konvensi vektor baris, distribusi saat ini \(p_n\) diperbarui oleh \(p_{n+1}=p_nP\). Entri \(P_{ij}\) adalah peluang berpindah dari keadaan \(i\) ke keadaan \(j\) dalam satu langkah.
Aturan matriks
Setiap entri memenuhi \(P_{ij}\ge0\).
Setiap baris berjumlah \(1\), karena keadaan berikutnya pasti berada di suatu tempat.
Perpindahan deterministik memiliki satu entri baris sama dengan \(1\) dan yang lain \(0\).
Keadaan penyerap \(i\) memiliki \(P_{ii}=1\).
Jika \(p_0\) adalah distribusi, maka \(p_0P^n\) adalah distribusi setelah \(n\) langkah.
Chapman-Kolmogorov
Transisi banyak langkah tersusun: \[P^{m+n}=P^mP^n.\] Secara entri, ini menjumlahkan semua keadaan perantara yang mungkin.
Contoh dikerjakan
Contoh: Misalkan \(P=\begin{pmatrix}1/2&1/2\\1/4&3/4\end{pmatrix}\) dan \(p_0=(1,0)\). Berapakah \(p_1\)?
Kalikan dari kanan: \[p_1=p_0P=(1,0)\begin{pmatrix}1/2&1/2\\1/4&3/4\end{pmatrix}=(1/2,1/2).\] Mulai dari keadaan \(1\), distribusi berikutnya hanyalah baris \(1\) dari \(P\).
Coba
Coba: Dalam matriks transisi, bagaimana baris \((1/4,3/4)\) seharusnya diklasifikasikan?
Petunjuk: Periksa ketaknegatifan dan jumlah barisnya.
Distribusi stasioner tidak berubah oleh satu langkah
Tujuan pembelajaran: Kenali dan selesaikan persamaan stasioner untuk rantai hingga.
Ide utama
Distribusi baris \(\pi\) bersifat stasioner ketika \(\pi P=\pi\). Dalam bahasa aljabar linear, \(\pi\) adalah vektor eigen kiri dari \(P\) dengan nilai eigen \(1\), dinormalisasi sehingga entrinya tidak negatif dan berjumlah \(1\).
Daftar cek penyelesaian
Tulis \(\pi=(\pi_1,\dots,\pi_k)\).
Selesaikan \(\pi P=\pi\).
Tambahkan normalisasi \(\pi_1+\cdots+\pi_k=1\).
Periksa bahwa entrinya tidak negatif.
Pada rantai tereduksi, distribusi stasioner mungkin tidak unik.
Pintasan dua keadaan
Untuk \(P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}\) dengan \(a+b\) positif, distribusi stasionernya sebanding dengan \((b,a)\), sehingga \(\pi=\left(\frac{b}{a+b},\frac{a}{a+b}\right)\).
Contoh dikerjakan
Contoh: Cari distribusi stasioner untuk \(P=\begin{pmatrix}1/2&1/2\\1/2&1/2\end{pmatrix}\).
Kedua barisnya seragam. Mengalikan distribusi apa pun dengan \(P\) menghasilkan \((1/2,1/2)\), jadi \(\pi=(1/2,1/2)\) bersifat stasioner.
Coba
Coba: Apa arti \(\pi P=\pi\)?
Petunjuk: Satu transisi membuat distribusi tetap persis seperti semula.
Keterjangkauan mengendalikan struktur rantai
Tujuan pembelajaran: Gunakan keterjangkauan graf untuk mengklasifikasikan keadaan dan kelas berkomunikasi.
Ide utama
Katakan \(i\) mencapai \(j\) jika \((P^n)_{ij}>0\) untuk suatu \(n\ge0\). Keadaan saling berkomunikasi ketika masing-masing dapat mencapai yang lain. Rantai hingga tak tereduksi memiliki satu kelas berkomunikasi.
Bahasa klasifikasi
Kelas tertutup: setelah masuk, rantai tidak dapat keluar dari kelas itu.
Keadaan penyerap: kelas tertutup satu keadaan, ekuivalen dengan \(P_{ii}=1\).
Keadaan rekuren: dikunjungi kembali dengan probabilitas \(1\).
Keadaan transien: dikunjungi hanya berhingga kali dengan probabilitas \(1\).
Rantai tak tereduksi: setiap keadaan berkomunikasi dengan setiap keadaan lain.
Fakta rantai hingga
Dalam rantai hingga tak tereduksi, setiap keadaan bersifat rekuren. Dalam rantai hingga tereduksi, keadaan di luar kelas tertutup sering kali transien karena probabilitas akhirnya berpindah ke kelas tertutup dan tetap di sana.
Contoh dikerjakan
Contoh: Untuk \(P=\begin{pmatrix}1&0\\1/2&1/2\end{pmatrix}\), keadaan mana yang penyerap?
Keadaan \(1\) penyerap karena baris \(1\) adalah \((1,0)\), sehingga \(P_{11}=1\). Keadaan \(2\) dapat berpindah ke keadaan \(1\), tetapi keadaan \(1\) tidak dapat kembali ke keadaan \(2\), jadi rantainya tidak tak tereduksi.
Coba
Coba: Apa arti tak tereduksi untuk rantai Markov hingga?
Petunjuk: Pikirkan graf berarah dengan panah \(i\to j\) ketika suatu transisi memiliki probabilitas positif.
Aritmetika waktu kembali menentukan aperiodisitas
Tujuan pembelajaran: Hitung periode sederhana dan ketahui mengapa aperiodisitas penting untuk konvergensi.
Ide utama
Periode suatu keadaan \(i\) adalah FPB dari semua \(n\) positif sehingga \((P^n)_{ii}>0\). Keadaan dengan periode \(1\) disebut aperiodik. Dalam rantai tak tereduksi, semua keadaan memiliki periode yang sama.
Gambaran konvergensi
Jika rantai hingga tak tereduksi dan aperiodik, ia memiliki distribusi stasioner unik \(\pi\).
Untuk rantai seperti itu, \(P^n\) konvergen ke matriks yang semua barisnya adalah \(\pi\).
Jika rantainya periodik, distribusi stasioner bisa ada sementara \(P^n\) tetap berosilasi.
Jika rantainya tereduksi, perilaku limit bergantung pada kelas tertutup yang dapat dicapai.
Transisi ke Diri Kirimiri
Transisi ke diri sendiri \(P_{ii}>0\) memberi kemungkinan kembali dalam satu langkah, sehingga FPB waktu kembali mencakup \(1\). Ini memaksa periode \(1\).
Contoh dikerjakan
Contoh: Untuk \(P=\begin{pmatrix}0&1\\1&0\end{pmatrix}\), apa yang terjadi setelah dua langkah?
Rantai berganti keadaan pada setiap langkah. Jadi \(P^2=I\), kembali terjadi pada waktu genap, dan setiap keadaan memiliki periode \(2\).
Coba
Coba: Berapa periode rantai dengan \(P=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)?
Petunjuk: Mulai dari suatu keadaan, hitung waktu ketika kembali mungkin terjadi.
Keadaan tertutup mengubah soal probabilitas menjadi persamaan
Tujuan pembelajaran: Susun persamaan sederhana untuk probabilitas pencapaian dan waktu pencapaian dalam perilaku penyerap.
Ide utama
Keadaan penyerap menjebak rantai setelah keadaan itu dimasuki. Secara lebih umum, kelas berkomunikasi tertutup tidak dapat ditinggalkan. Pertanyaan pencapaian menanyakan apakah dan kapan proses memasuki himpunan tertentu.
Persamaan Pencapaian
Untuk probabilitas pencapaian \(h_i\), gunakan nilai batas \(h_i=1\) pada target dan \(h_i=0\) pada kelas tertutup yang mustahil.
Untuk keadaan lain, gunakan \(h_i=\sum_j P_{ij}h_j\).
Untuk waktu pencapaian harapan \(t_i\), gunakan \(t_i=0\) pada target dan \(t_i=1+\sum_jP_{ij}t_j\) di tempat lain.
Jaga agar persamaan tetap kecil dengan memakai simetri atau keadaan penyerap yang jelas.
Kelas tertutup
Kelas penyerap adalah kelas berkomunikasi yang tidak dapat ditinggalkan. Satu keadaan penyerap adalah contoh terkecil dari gagasan ini.
Contoh dikerjakan
Contoh: Untuk \(P=\begin{pmatrix}1&0\\1/2&1/2\end{pmatrix}\), jika mulai dari keadaan \(2\), berapa waktu harapan untuk mencapai keadaan \(1\)?
Misalkan \(t_1=0\). Dari keadaan \(2\), \[t_2=1+\frac12t_1+\frac12t_2=1+\frac12t_2.\] Maka \(t_2=2\).
Coba
Coba: Jika rantai Markov mulai di keadaan penyerap, di mana ia berada setelah satu langkah?
Petunjuk: Keadaan penyerap memiliki \(P_{ii}=1\).
Ekspektasi bersyarat melacak kecenderungan yang adil
Tujuan pembelajaran: Hubungkan intuisi rantai Markov dengan bahasa yang lebih luas tentang proses stokastik, filtrasi, martingale, dan waktu henti.
Ide utama
Proses stokastik adalah keluarga variabel acak berindeks. Filtrasi \((\mathcal F_n)\) mencatat informasi yang tersedia pada waktu \(n\). Pernyataan martingale adalah ekspektasi bersyarat relatif terhadap informasi ini.
Kamus ekspektasi bersyarat
Martingale: \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Submartingale: \(E[X_{n+1}\mid\mathcal F_n]\ge X_n\), sehingga kecenderungan bersyaratnya tidak negatif.
Supermartingale: \(E[X_{n+1}\mid\mathcal F_n]\le X_n\), sehingga kecenderungan bersyaratnya tidak positif.
Ini adalah pernyataan tentang rata-rata bersyarat, bukan tentang setiap lintasan sampel yang naik atau turun.
Waktu henti
Waktu henti \(\tau\) harus dapat diputuskan dari informasi yang tersedia sampai waktu \(n\) ketika memeriksa apakah \(\tau\le n\). Misalnya, waktu pertama suatu proses mencapai \(5\) adalah waktu henti; waktu terakhir sebelum besok ketika proses mencapai \(5\) bergantung pada informasi masa depan.
Contoh dikerjakan
Contoh: Misalkan \(S_n\) adalah random walk adil dengan langkah independen \(+1\) atau \(-1\), masing-masing dengan probabilitas \(1/2\). Mengapa \(S_n\) merupakan martingale?
Dengan informasi saat ini, langkah berikutnya memiliki rata-rata bersyarat \(0\). Karena itu \(E[S_{n+1}\mid\mathcal F_n]=S_n+0=S_n\).
Petunjuk: Martingale memiliki kecenderungan bersyarat nol dari nilai saat ini.
Kebanyakan kesalahan mencampur konvensi atau mengabaikan asumsi
Tujuan pembelajaran: Akhiri dengan memisahkan fakta matriks transisi, fakta jangka panjang, dan fakta ekspektasi bersyarat.
Kesalahan umum
Konvensi baris versus kolom: pelajaran ini memakai distribusi baris \(pP\). Dengan distribusi kolom, rumusnya ditransposkan.
Baris matriks tidak valid: probabilitas harus tidak negatif dan setiap baris harus berjumlah \(1\).
Stasioner bukan penyerap: \(\pi P=\pi\) menggambarkan distribusi, tidak harus keadaan tetap.
Rantai tereduksi dapat memiliki banyak distribusi stasioner: setiap kelas tertutup dapat menopang massa stasioner.
Periode dapat menghalangi konvergensi: rantai dua keadaan yang saling bertukar memiliki distribusi stasioner tetapi \(P^n\) berosilasi.
Pintasan transisi ke diri sendiri: \(P_{ii}>0\) memberi periode \(1\) untuk kelas rekuren itu.
Transien bersifat akhirnya: keadaan transien dapat dikunjungi beberapa kali, tetapi hanya berhingga kali dengan probabilitas \(1\).
Waktu henti memakai informasi yang tersedia: ia tidak boleh bergantung pada hasil masa depan yang belum terlihat.
Martingale berarti rata-rata bersyarat adil: bukan berarti lintasannya tetap konstan.
Contoh dikerjakan
Contoh: Apakah baris \((1/4,1/4)\) valid sebagai baris transisi lengkap?
Tidak. Baris itu tidak negatif, tetapi entrinya berjumlah \(1/2\), bukan \(1\). Baris transisi lengkap harus memberikan probabilitas total \(1\) pada semua keadaan berikutnya.
Coba
Coba: Waktu henti tidak boleh bergantung pada apa?
Petunjuk: Pada waktu \(n\), keputusan harus didasarkan pada informasi yang tersedia sampai waktu \(n\).
Rekap akhir
Sifat Markov: hukum keadaan berikutnya bergantung pada keadaan saat ini setelah keadaan saat ini diketahui.
Matriks transisi memiliki entri tidak negatif dan baris yang berjumlah \(1\).
Dengan vektor baris, \(p_n=p_0P^n\).
Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
Distribusi stasioner menyelesaikan \(\pi P=\pi\) dan \(\sum_i\pi_i=1\).
Keadaan penyerap memiliki \(P_{ii}=1\); kelas tertutup tidak dapat ditinggalkan.
Tak tereduksi berarti setiap keadaan dapat mencapai setiap keadaan lain.
Periode adalah FPB dari waktu kembali yang mungkin; transisi ke diri sendiri memberi periode \(1\).
Rantai hingga tak tereduksi dan aperiodik konvergen ke baris stasioner.
Waktu henti diputuskan dari informasi masa lalu dan saat ini, bukan data masa depan yang belum terlihat.
Langkah berikutnya: Tutup pelajaran ini dan coba kuis lagi. Untuk setiap soal, pertama-tama putuskan apakah yang ditanyakan adalah satu langkah, banyak langkah, distribusi stasioner, klasifikasi keadaan, periode, atau ekspektasi bersyarat.
Set latihan
Soal latihan Markov Chains & Stochastic Processes dengan skor langsung
Jawab semua 10 soal di bawah ini, lalu lihat skor akhir dan tinjauan kesalahan agar kamu tahu persis apa yang perlu diperbaiki.
0/10dijawab
Soal 1Belum dijawab
Sifat Markov menyatakan bahwa masa depan bergantung pada:
Jawaban benar: A. Keadaan saat ini
Penjelasan: Dengan keadaan saat ini diketahui, masa lalu tidak menambah informasi.
Soal 2Belum dijawab
Dalam matriks transisi untuk rantai Markov hingga, setiap baris biasanya berjumlah:
Jawaban benar: C. \(1\)
Penjelasan: Baris memuat peluang semua keadaan berikutnya, sehingga jumlahnya \(1\).
Soal 3Belum dijawab
Peluang transisi harus bersifat:
Jawaban benar: B. Taknegatif
Penjelasan: Peluang bersifat taknegatif dan paling besar \(1\).
Soal 4Belum dijawab
Distribusi stasioner \(\pi\) memenuhi:
Jawaban benar: D. \(\pi P=\pi\)
Penjelasan: Stasioner berarti satu transisi membuat distribusi tidak berubah.
Soal 5Belum dijawab
Keadaan penyerap \(i\) memiliki peluang transisi \(P_{ii}\) sama dengan:
Jawaban benar: B. \(1\)
Penjelasan: Setelah dimasuki, keadaan penyerap tidak pernah ditinggalkan.
Soal 6Belum dijawab
Jika \(P=\begin{pmatrix}1&0\\0&1\end{pmatrix}\), kedua keadaan bersifat:
Jawaban benar: D. Penyerap
Penjelasan: Setiap keadaan bertransisi ke dirinya sendiri dengan peluang \(1\).
Soal 7Belum dijawab
Suatu rantai bersifat ireduksibel ketika:
Jawaban benar: D. Setiap keadaan dapat mencapai setiap keadaan lain
Penjelasan: Ireduksibel berarti semua keadaan saling berkomunikasi.
Soal 8Belum dijawab
Jika distribusi saat ini adalah \(p\), distribusi berikutnya biasanya:
Jawaban benar: A. \(pP\)
Penjelasan: Dengan konvensi vektor baris, satu langkah diperbarui dengan mengalikan di kanan oleh \(P\).
Soal 9Belum dijawab
Untuk \(P=\begin{pmatrix}1/2&1/2\\1/2&1/2\end{pmatrix}\), distribusi mana yang stasioner?
Jawaban benar: B. \((1/2,1/2)\)
Penjelasan: Distribusi seragam tetap seragam setelah dikalikan dengan matriks ini.
Soal 10Belum dijawab
Dalam rantai Markov hingga, entri suatu distribusi probabilitas harus berjumlah:
Jawaban benar: D. \(1\)
Penjelasan: Distribusi memberikan total peluang \(1\) pada semua keadaan.
