Matriks Stokastik, Matriks Yang Digunakan Untuk Transisi – Dalam matematika, matriks stokastik adalah matriks persegi yang digunakan untuk menggambarkan transisi dari rantai Markov. Setiap entrinya adalah bilangan real nonnegatif yang mewakili probabilitas. Ini juga disebut matriks probabilitas, matriks transisi, matriks substitusi, atau matriks Markov. Matriks stokastik pertama kali dikembangkan oleh Andrey Markov pada awal abad ke-20, dan telah digunakan di berbagai bidang ilmiah, termasuk teori probabilitas, statistik, keuangan matematika dan aljabar linier, serta ilmu komputer dan genetika populasi.

Matriks Stokastik, Matriks Yang Digunakan Untuk Transisi

transitionmathproject – Ada beberapa definisi dan jenis matriks stokastik yang berbeda. Dalam nada yang sama, seseorang dapat mendefinisikan vektor stokastik (juga disebut vektor probabilitas) sebagai vektor yang elemen-elemennya adalah bilangan real nonnegatif yang berjumlah 1. Jadi, setiap baris matriks stokastik kanan (atau kolom matriks stokastik kiri) adalah vektor stokastik. Konvensi umum dalam literatur matematika bahasa Inggris adalah menggunakan vektor baris peluang dan matriks stokastik kanan daripada vektor kolom peluang dan matriks stokastik kiri. artikel ini mengikuti konvensi itu.

Baca Juga : Mengulas Dekomposisi Cholesky dan Dekomposisi LU Dibidang Matematika

Sejarah Matriks stokastik

Matriks stokastik dikembangkan bersama rantai Markov oleh Andrey Markov, seorang matematikawan dan profesor Rusia di Universitas St. Petersburg yang pertama kali menerbitkan topik tersebut pada tahun 1906. Penggunaan awalnya yang dimaksudkan adalah untuk analisis linguistik dan mata pelajaran matematika lainnya seperti pengocokan kartu, tetapi rantai dan matriks Markov dengan cepat digunakan di bidang lain.

Matriks stokastik dikembangkan lebih lanjut oleh para sarjana seperti Andrey Kolmogorov, yang memperluas kemungkinannya dengan memungkinkan proses Markov waktu kontinu. Pada 1950-an, artikel yang menggunakan matriks stokastik telah muncul di bidang ekonometrik dan teori rangkaian. Pada tahun 1960-an, matriks stokastik muncul dalam berbagai karya ilmiah yang lebih luas, dari ilmu perilaku hingga geologi hingga perencanaan perumahan.

Selain itu, banyak pekerjaan matematika juga dilakukan selama dekade ini untuk meningkatkan jangkauan penggunaan dan fungsionalitas matriks stokastik dan proses Markovian secara lebih umum. Dari tahun 1970-an hingga sekarang, matriks stokastik telah digunakan di hampir setiap bidang yang memerlukan analisis formal, dari ilmu struktural hingga diagnosis medis hingga manajemen personalia. Selain itu, matriks stokastik telah digunakan secara luas dalam pemodelan perubahan lahan, biasanya dengan istilah matriks Markov.

Definisi dan properti

Jika peluang berpindah dari i ke j dalam satu langkah waktu adalah Pr(j|i) = Pi,j, matriks stokastik P diberikan dengan menggunakan Pi,j sebagai elemen baris ke-i dan kolom ke-j, mis. , Jumlah elemen di atas di setiap baris i dari P dapat lebih ringkas ditulis sebagai P1 = 1, di mana 1 adalah vektor dimensi-S dari semua vektor. Dengan menggunakan ini, dapat dilihat bahwa hasil kali dua matriks stokastik benar P′ dan P′′ juga stokastik benar: P′ P′′ 1 = P′ (P′′ 1) = P′ 1 = 1. Secara umum , pangkat ke-k Pk dari matriks stokastik kanan P juga stokastik kanan.

Secara umum, transisi probabilitas dari suatu keadaan ke keadaan lain dalam rantai Markov berhingga yang diberikan oleh matriks P dalam k langkah diberikan oleh Pk. Distribusi probabilitas awal dari keadaan, menentukan di mana sistem mungkin awalnya dan dengan probabilitas apa, diberikan sebagai vektor baris. Dapat ditunjukkan bahwa jari-jari spektral matriks stokastik adalah satu. Dengan teorema lingkaran Gershgorin, semua nilai eigen dari matriks stokastik memiliki nilai absolut kurang dari atau sama dengan satu. Selain itu, setiap matriks stokastik kanan memiliki vektor eigen kolom “jelas” yang terkait dengan nilai eigen 1: vektor 1, yang koordinatnya sama dengan 1 (perhatikan saja bahwa mengalikan baris A kali 1 sama dengan jumlah entri baris dan, karenanya, sama dengan 1).

Karena nilai eigen kiri dan kanan dari matriks persegi adalah sama, setiap matriks stokastik memiliki, setidaknya, vektor eigen baris yang terkait dengan nilai eigen 1 dan nilai absolut terbesar dari semua nilai eigennya juga 1. Akhirnya, Teorema Titik Tetap Brouwer ( diterapkan pada himpunan cembung kompak dari semua distribusi probabilitas dari himpunan hingga {1, …, n}) menyiratkan bahwa ada beberapa vektor eigen kiri yang juga merupakan vektor probabilitas stasioner. Di sisi lain, teorema Perron-Frobenius juga memastikan bahwa setiap matriks stokastik yang tidak dapat direduksi memiliki vektor stasioner seperti itu, dan bahwa nilai absolut terbesar dari nilai eigen selalu 1.

Namun, teorema ini tidak dapat diterapkan secara langsung ke matriks tersebut karena membutuhkan tidak dapat direduksi. Secara umum, mungkin ada beberapa vektor seperti itu. Namun, untuk matriks dengan entri yang benar-benar positif (atau, lebih umum, untuk matriks stokastik aperiodik tak tereduksi), vektor ini unik dan dapat dihitung dengan mengamati bahwa untuk setiap i kita memiliki limit berikut, di mana j adalah ke-j elemen vektor baris . Antara lain, ini mengatakan bahwa probabilitas jangka panjang untuk berada dalam keadaan j tidak tergantung pada keadaan awal i.

Bahwa kedua perhitungan ini memberikan vektor stasioner yang sama adalah bentuk teorema ergodik, yang umumnya benar dalam berbagai sistem dinamis disipatif: sistem berkembang, dari waktu ke waktu, ke keadaan stasioner. Secara intuitif, matriks stokastik mewakili rantai Markov. penerapan matriks stokastik untuk distribusi probabilitas mendistribusikan kembali massa probabilitas dari distribusi asli sambil mempertahankan massa totalnya. Jika proses ini diterapkan berulang kali, distribusi konvergen ke distribusi stasioner untuk rantai Markov.

Contoh Matriks stokastik

Misalkan ada pengatur waktu dan deretan lima kotak yang berdekatan, dengan kucing di kotak pertama dan tikus di kotak kelima pada waktu nol. Kucing dan tikus keduanya melompat ke kotak yang berdekatan secara acak ketika pengatur waktu maju. Misalnya. jika kucing berada di kotak kedua dan tikus di kotak keempat, probabilitasnya adalah seperempat bahwa kucing akan berada di kotak pertama dan tikus di kotak kelima setelah penghitung waktu maju. Jika kucing berada di kotak pertama dan tikus di kotak kelima, peluangnya adalah bahwa kucing akan berada di kotak dua dan tikus akan berada di kotak empat setelah pengatur waktu maju. Kucing memakan tikus jika keduanya berakhir di kotak yang sama, pada saat itu permainan berakhir.

Variabel acak K memberikan jumlah langkah waktu mouse tetap dalam permainan. Rantai Markov yang mewakili permainan ini berisi lima status berikut yang ditentukan oleh kombinasi posisi (kucing, tikus). Perhatikan bahwa sementara enumerasi naif negara bagian akan mencantumkan 25 negara bagian, banyak yang tidak mungkin karena mouse tidak akan pernah memiliki indeks yang lebih rendah daripada kucing (karena itu berarti mouse menempati kotak kucing dan bertahan untuk melewatinya), atau karena jumlah kedua indeks akan selalu memiliki paritas genap.