Masalah 1. Diberi matriks kebarangkalian peralihan untuk rantai Markov diskret daripada i-negeri ke-dalam j-ke dalam satu langkah ( i, j=1, 2). Taburan kebarangkalian ke atas negeri di detik permulaan t=0 ditentukan oleh vektor =(0.1; 0.9). Cari:

1. matriks P2 peralihan litar dari negeri i dalam sesebuah negeri j dalam dua
langkah;

2. taburan kebarangkalian ke atas negeri pada masa ini t=2;

3. kebarangkalian bahawa pada masa ini t=1 keadaan litar akan menjadi A2;

4. pengagihan pegun.

Penyelesaian. Untuk rantai Markov diskret, jika ia adalah homogen, hubungan berikut berlaku:

di mana P1 ialah matriks kebarangkalian peralihan dalam satu langkah;
Рn - matriks kebarangkalian peralihan untuk n langkah;

1. Cari matriks peralihan P2 dalam dua langkah

Biarkan taburan kebarangkalian ke atas keadaan dihidupkan S langkah ke- ditentukan oleh vektor
.
Mengetahui matriks Pn peralihan dalam n langkah, kita boleh menentukan taburan kebarangkalian ke atas keadaan pada (S+n)-langkah ke . (5)

2. Mari kita cari taburan kebarangkalian ke atas keadaan sistem pada masa ini t=2. Mari kita masukkan (5) S=0 dan n=2. Kemudian .

Kami akan dapatkannya.

3. Mari kita cari taburan kebarangkalian ke atas keadaan sistem pada masa ini t=1.

Mari kita masukkan (5) s=0 dan n=1, maka .
Bagaimana kita boleh melihat bahawa kebarangkalian bahawa pada masa ini t=1 keadaan litar akan menjadi A2, sama p2(1)=0,69.
Taburan kebarangkalian ke atas keadaan dipanggil pegun jika ia tidak berubah dari langkah ke langkah, iaitu
Kemudian daripada hubungan (5) di n=1 kita dapat

4. Mari cari taburan pegun. Oleh kerana =2 kita ada =(p1; p2). Mari kita tulis sistem persamaan linear(6) dalam bentuk koordinat

Keadaan terakhir dipanggil normalisasi. Dalam sistem (6) satu persamaan sentiasa merupakan gabungan linear yang lain. Oleh itu, ia boleh dicoret. Mari kita selesaikan persamaan pertama sistem dan persamaan normalisasi bersama-sama. Kami mempunyai 0.6 p1=0,3p2, iaitu p2=2p1. Kemudian p1+2p1=1 atau , iaitu . Oleh itu, .
Jawapan:
1) matriks peralihan dalam dua langkah untuk rantai Markov tertentu mempunyai bentuk ;
2) taburan kebarangkalian ke atas negeri pada masa ini t=2 sama ;
3) kebarangkalian bahawa pada masa ini t=1 keadaan litar akan menjadi A2, adalah sama p2(t)=0,69;
4) taburan pegun mempunyai bentuk

Matriks diberi intensiti peralihan rantai Markov berterusan. Buat graf keadaan berlabel sepadan dengan matriks Λ; buat satu sistem persamaan pembezaan Kolmogorov untuk kebarangkalian negeri; cari taburan kebarangkalian mengehadkan. Penyelesaian. Rantai Markov homogen dengan nombor terhingga negeri A1, A2,…A dicirikan oleh matriks keamatan peralihan ,

di mana - intensiti peralihan rantai Markov dari negeri ini Аi dalam sesebuah negeri Аj; рij(Δt)-kebarangkalian peralihan Ai→Aj setiap selang masa Δ t.

Peralihan sistem dari keadaan ke keadaan ditentukan dengan mudah menggunakan graf keadaan berlabel, di mana lengkok yang sepadan dengan keamatan ditandakan λ ij>0. Mari buat graf keadaan berlabel untuk matriks yang diberikan intensiti peralihan

Biarkan menjadi vektor kebarangkalian rj(t),
j=1, 2,…,, sistem berada dalam keadaan Aj pada masa ini t.

Jelas sekali 0≤ rj(t)≤1 dan . Kemudian, dengan peraturan pembezaan fungsi vektor hujah skalar kita dapat . Kebarangkalian rj(t) memenuhi sistem persamaan pembezaan Kolmogorov (SDEK), yang dalam bentuk matriks mempunyai bentuk . (7)

Jika pada masa awal sistem berada dalam keadaan Аj, maka SDUK harus diselesaikan di bawah syarat awal
ri(0)=1, рj(0)=0, j≠i,j=1, 2,…,. (8)
Set SDEK (7) dan keadaan awal (8) secara unik menerangkan rantai Markov homogen dengan masa yang berterusan dan bilangan negeri yang terhad.
Mari kita karang SDEK untuk rantai Markov tertentu. Sejak =3, maka j=1, 2, 3.

Daripada hubungan (7) kita perolehi

.
Dari sini kita akan ada

Keadaan terakhir dipanggil normalisasi.
Taburan kebarangkalian ke atas keadaan dipanggil pegun, jika ia tidak berubah dari semasa ke semasa, iaitu di mana rj=const, j=1,2,…,. Dari sini .

Kemudian daripada SDUK (7) kami memperoleh sistem untuk mencari taburan pegun
(9)
Untuk masalah ini, dari SDUK kita akan ada

Daripada keadaan normalisasi yang kami perolehi 3р2+р2+р2=1 atau . Oleh itu, taburan had mempunyai bentuk .
Ambil perhatian bahawa keputusan ini boleh diperolehi terus daripada graf keadaan berlabel jika kita menggunakan peraturan: untuk pengedaran pegun, jumlah produk λ jipi, j≠i, untuk anak panah yang datang dari i-keadaan ke- adalah sama dengan hasil tambah λ jipi, j≠i, untuk anak panah yang disertakan dalam i-negeri ke-. sungguh,

Adalah jelas bahawa sistem yang terhasil adalah bersamaan dengan yang disusun menggunakan SDUK. Oleh itu ia mempunyai penyelesaian yang sama.
Jawapan: taburan pegun mempunyai bentuk .

Rantaian Markov ialah satu siri peristiwa di mana setiap peristiwa berikutnya bergantung pada yang sebelumnya. Dalam artikel ini kita akan mengkaji konsep ini dengan lebih terperinci.

Rantaian Markov ialah cara yang biasa dan agak mudah untuk dimodelkan peristiwa rawak. Ia digunakan dalam pelbagai bidang, daripada penjanaan teks kepada pemodelan kewangan. yang paling banyak contoh terkenal ialah SubredditSimulator. DALAM dalam kes ini Rantaian Markov digunakan untuk mengautomasikan penciptaan kandungan sepanjang subreddit.

Rantaian Markov jelas dan mudah digunakan kerana ia boleh dilaksanakan tanpa menggunakan sebarang konsep statistik atau matematik. Rantaian Markov sesuai untuk mempelajari pemodelan kebarangkalian dan sains data.

Senario

Bayangkan hanya ada dua keadaan cuaca: Ia boleh sama ada cerah atau mendung. Anda sentiasa boleh menentukan cuaca dengan tepat detik semasa. Dijamin cerah atau mendung.

Sekarang anda ingin belajar cara meramal cuaca untuk esok. Secara intuitif, anda memahami bahawa cuaca tidak boleh berubah secara mendadak dalam satu hari. Ini dipengaruhi oleh banyak faktor. Cuaca esok secara langsung bergantung pada cuaca semasa, dsb. Oleh itu, untuk meramalkan cuaca, anda mengumpul data selama beberapa tahun dan membuat kesimpulan bahawa selepas hari mendung, kebarangkalian hari yang cerah ialah 0.25. Adalah logik untuk mengandaikan bahawa kebarangkalian dua hari mendung berturut-turut ialah 0.75, kerana kita hanya mempunyai dua kemungkinan keadaan cuaca.

Kini anda boleh meramalkan cuaca beberapa hari lebih awal berdasarkan cuaca semasa.

Contoh ini menunjukkan konsep utama rantai Markov. Rantaian Markov terdiri daripada satu set peralihan yang ditentukan oleh taburan kebarangkalian, yang seterusnya memenuhi sifat Markov.

Ambil perhatian bahawa dalam contoh taburan kebarangkalian bergantung hanya pada peralihan dari hari semasa ke hari berikutnya. ini harta yang unik Proses Markov - ia melakukan ini tanpa menggunakan memori. Biasanya, pendekatan ini tidak dapat mencipta urutan di mana mana-mana arah aliran diperhatikan. Sebagai contoh, sementara rantai Markov boleh mensimulasikan gaya penulisan berdasarkan kekerapan perkataan, ia tidak boleh membuat teks dengannya makna yang mendalam, kerana ia hanya boleh berfungsi dengan teks yang besar. Inilah sebabnya mengapa rantai Markov tidak boleh menghasilkan kandungan yang bergantung kepada konteks.

Model

Secara rasmi, rantai Markov ialah automaton kemungkinan. Taburan kebarangkalian peralihan biasanya diwakili sebagai matriks. Jika rantai Markov mempunyai N keadaan yang mungkin, maka matriks akan mempunyai bentuk N x N, di mana kemasukan (I, J) akan menjadi kebarangkalian peralihan dari keadaan I ke keadaan J. Di samping itu, matriks sedemikian mestilah stokastik, iaitu baris atau lajur jumlahnya harus ditambah sehingga satu. Dalam matriks sedemikian, setiap baris akan mempunyai taburan kebarangkalian sendiri.

Pandangan umum rantai Markov dengan keadaan dalam bentuk bulatan dan tepi dalam bentuk peralihan.

Contoh matriks peralihan dengan tiga keadaan yang mungkin.

Rantaian Markov mempunyai vektor keadaan awal, diwakili sebagai matriks N x 1 Ia menerangkan taburan kebarangkalian permulaan dalam setiap keadaan N yang mungkin. Entri I menerangkan kebarangkalian rantaian bermula dalam keadaan I.

Kedua-dua struktur ini cukup memadai untuk mewakili rantai Markov.

Kami telah membincangkan cara mendapatkan kebarangkalian peralihan dari satu keadaan ke keadaan lain, tetapi bagaimana pula dengan mendapatkan kebarangkalian itu dalam beberapa langkah? Untuk melakukan ini, kita perlu menentukan kebarangkalian peralihan dari keadaan I ke keadaan J dalam langkah M. Ia sebenarnya sangat mudah. Matriks peralihan P boleh ditentukan dengan mengira (I, J) dengan menaikkan P kepada kuasa M. Untuk nilai kecil M, ini boleh dilakukan secara manual menggunakan pendaraban berulang. Tetapi untuk nilai yang besar M, jika anda biasa dengan algebra linear, lebih banyak lagi dengan cara yang cekap menaikkan matriks kepada kuasa akan mula-mula menyerong matriks itu.

Rantaian Markov: kesimpulan

Sekarang, mengetahui apa itu rantaian Markov, anda boleh melaksanakannya dengan mudah dalam salah satu bahasa pengaturcaraan. Rantaian Markov mudah adalah asas untuk belajar lebih lanjut kaedah yang kompleks pemodelan.

Semua kemungkinan keadaan sistem dalam rantai Markov homogen, dan merupakan matriks stokastik yang mentakrifkan rantai ini, terdiri daripada kebarangkalian peralihan (lihat muka surat 381).

Mari kita nyatakan dengan kebarangkalian sistem berada dalam keadaan pada suatu masa jika diketahui bahawa pada suatu masa sistem itu berada dalam keadaan (,). Jelas sekali, . Menggunakan teorem pada penambahan dan pendaraban kebarangkalian, kita boleh mencari dengan mudah:

atau dalam tatatanda matriks

Dari sini, memberikan nilai secara berurutan, kami memperoleh formula penting

Jika ada had

atau dalam tatatanda matriks

kemudian nilai dipanggil kebarangkalian peralihan marginal atau akhir.

Untuk mengetahui dalam kes apakah terdapat kebarangkalian peralihan yang mengehadkan dan untuk mendapatkan formula yang sepadan, kami memperkenalkan istilah berikut.

Kami akan memanggil matriks stokastik dan rantai Markov homogen yang sepadan dengan sekata jika matriks tidak mempunyai nombor ciri yang berbeza daripada kesatuan dan sama dalam modulus kepada satu, dan tetap jika sebagai tambahan kesatuan adalah akar sederhana persamaan ciri matriks

Matriks biasa dicirikan oleh fakta bahawa dalam bentuk normalnya (69) (ms 373) matriks adalah primitif. Untuk matriks biasa tambahan.

Di samping itu, rantai Markov homogen dipanggil tidak boleh terurai, boleh terurai, akiklik, kitaran jika untuk rantai ini matriks stokastik adalah, masing-masing, tidak boleh terurai, boleh reput, primitif, imprimitif.

Memandangkan matriks stokastik primitif ialah jenis khas matriks biasa, rantai Markov asiklik ialah jenis khas rantai biasa.

Kami akan menunjukkan bahawa menghadkan kebarangkalian peralihan wujud hanya untuk rantai Markov homogen biasa.

Sesungguhnya, jadikan polinomial minimum bagi matriks biasa . Kemudian

Menurut Teorem 10, kita boleh mengandaikan bahawa

Berdasarkan formula (24) Ch. V (halaman 113)

(96)

di mana ialah matriks bersebelahan terkurang dan

Jika ialah matriks biasa, maka

dan oleh itu, di sebelah kanan formula (96), semua sebutan kecuali yang pertama cenderung kepada sifar. Oleh itu, untuk matriks biasa terdapat matriks yang terdiri daripada kebarangkalian peralihan yang mengehadkan, dan

Keadaan sebaliknya adalah jelas. Jika ada masalah

maka matriks tidak boleh mempunyai nombor ciri, yang mana , a , sejak itu had tidak akan wujud [Had yang sama mesti wujud kerana kewujudan had (97").]

Kami telah membuktikan bahawa untuk rantai Markov homogen biasa (dan hanya biasa) terdapat matriks. Matriks ini ditentukan oleh formula (97).

Mari kita tunjukkan bagaimana matriks boleh dinyatakan melalui polinomial ciri

dan matriks bersebelahan .

Dari identiti

Berdasarkan (95), (95") dan (98) ia berikut:

Oleh itu, formula (97) boleh digantikan dengan formula

(97)

Untuk rantai Markov biasa, kerana ia adalah jenis rantai biasa tertentu, matriks wujud dan ditentukan oleh mana-mana formula (97), (97"). Dalam kes ini, formula (97") juga mempunyai bentuk

2. Pertimbangkan rantai biasa jenis umum (tidak teratur). Kami menulis matriks yang sepadan dalam bentuk biasa

(100)

di mana matriks stokastik primitif, dan matriks tidak boleh terurai mempunyai nombor ciri maksimum. Percaya

,

jom tulis dalam borang

(101)

Tetapi , kerana semua nombor ciri matriks adalah kurang daripada satu dalam nilai mutlak. sebab tu

(102)

Oleh kerana matriks stokastik primitif, matriks mengikut formula (99) dan (35) (ms 362) adalah positif

dan dalam setiap lajur mana-mana matriks ini semua elemen adalah sama antara satu sama lain:

.

Perhatikan bahawa bentuk normal (100) matriks stokastik sepadan dengan pembahagian keadaan sistem kepada kumpulan:

Setiap kumpulan dalam (104) sepadan dengan kumpulan sirinya sendiri dalam (101). Menurut terminologi L.N. Kolmogorov, keadaan sistem yang termasuk dalam dipanggil penting, dan keadaan yang termasuk dalam kumpulan yang selebihnya dipanggil tidak penting.

Daripada bentuk (101) matriks ia mengikuti bahawa untuk sebarang bilangan langkah terhingga (dari saat ke saat ) satu-satunya peralihan sistem yang mungkin ialah a) daripada keadaan penting kepada keadaan penting kumpulan yang sama, b) daripada keadaan tidak penting kepada keadaan penting, dan c) daripada keadaan tidak penting kepada keadaan tidak penting kumpulan yang sama atau sebelumnya.

Daripada bentuk (102) matriks itu menunjukkan bahawa dalam kes peralihan hanya mungkin dari mana-mana keadaan kepada keadaan penting, iaitu, kebarangkalian peralihan kepada mana-mana keadaan tidak penting cenderung kepada sifar dengan bilangan langkah. Oleh itu, keadaan penting kadangkala dipanggil keadaan had.

3. Daripada formula (97) ia berikut:

.

Ini menunjukkan bahawa setiap lajur matriks adalah vektor eigen bagi matriks stokastik untuk nombor ciri.

Untuk matriks biasa, nombor 1 ialah punca ringkas persamaan ciri dan nombor ini sepadan dengan hanya satu (sehingga faktor skalar) vektor eigen bagi matriks. Oleh itu, dalam mana-mana lajur matriks, semua elemen adalah sama dengan nombor bukan negatif yang sama:

Oleh itu, dalam rantai biasa, kebarangkalian peralihan yang mengehadkan tidak bergantung pada keadaan awal.

Sebaliknya, jika dalam beberapa rantai Markov homogen biasa, kebarangkalian peralihan prodel tidak bergantung pada keadaan awal, iaitu, formula (104) tahan, maka dalam skema (102) untuk matriks ia adalah perlu. Tetapi kemudian rantai itu tetap.

Untuk rantai asiklik, yang merupakan kes khas rantai biasa, ia adalah matriks primitif. Oleh itu, bagi sesetengah orang (lihat Teorem 8 pada halaman 377). Tetapi kemudian .

Sebaliknya, ia mengikuti bahawa untuk sesetengah , dan ini, menurut Teorem 8, bermakna bahawa matriks adalah primitif dan, oleh itu, rantai Markov homogen yang diberikan adalah asiklik.

Kami merumuskan keputusan yang diperoleh dalam bentuk teorem berikut:

Teorem 11. 1. Agar semua kebarangkalian peralihan menghadkan wujud dalam rantai Markov homogen, adalah perlu dan mencukupi bahawa rantai itu tetap. Dalam kes ini, matriks yang terdiri daripada menghadkan kebarangkalian peralihan ditentukan oleh formula (95) atau (98).

2. Agar kebarangkalian peralihan yang mengehadkan dalam rantai Markov homogen biasa menjadi bebas daripada keadaan awal, adalah perlu dan mencukupi bahawa rantai itu tetap. Dalam kes ini, matriks ditentukan oleh formula (99).

3. Agar semua kebarangkalian peralihan yang mengehadkan dalam rantaian Markov homogen biasa berbeza daripada sifar, adalah perlu dan mencukupi bahawa rantai itu adalah akiklik.

4. Mari kita perkenalkan lajur kebarangkalian mutlak

(105)

di manakah kebarangkalian sistem berada dalam keadaan (,) pada masa ini. Dengan menggunakan teorem penambahan dan pendaraban kebarangkalian, kita dapati:

(,),

atau dalam tatatanda matriks

di manakah matriks terpindah bagi matriks itu .

Semua kebarangkalian mutlak (105) ditentukan daripada formula (106), jika kebarangkalian awal dan matriks kebarangkalian peralihan diketahui

Mari kita perkenalkan kebarangkalian mutlak yang mengehadkan

Melewati kedua-dua belah kesamaan (106) kepada had pada , kita memperoleh:

Perhatikan bahawa kewujudan matriks mengehadkan kebarangkalian peralihan membayangkan kewujudan mengehadkan kebarangkalian mutlak untuk sebarang kebarangkalian awal dan sebaliknya.

Daripada formula (107) dan daripada bentuk (102) matriks ia mengikuti bahawa kebarangkalian mutlak mengehadkan sepadan dengan keadaan tidak penting adalah sama dengan sifar.

Mendarab kedua-dua belah kesamaan matriks

di sebelah kanan pada , kami, berdasarkan (107), memperoleh:

iaitu, lajur kebarangkalian mutlak marginal ialah vektor eigen bagi matriks untuk nombor ciri.

Jika litar ini Markov adalah sekata, maka ia adalah punca mudah persamaan ciri matriks . Dalam kes ini, lajur mengehadkan kebarangkalian mutlak ditentukan secara unik daripada (108) (sejak dan ).

Biarkan rantai Markov biasa diberikan. Kemudian daripada (104) dan daripada (107) ia berikut:

(109)

Dalam kes ini, kebarangkalian mutlak yang mengehadkan tidak bergantung pada kebarangkalian awal.

Sebaliknya, ia mungkin tidak bergantung pada kehadiran formula (107) jika dan hanya jika semua baris matriks adalah sama, i.e.

,

dan oleh itu (mengikut Teorem 11) ia adalah matriks biasa.

Jika ialah matriks primitif, maka , dan dengan itu berdasarkan (109)

Sebaliknya, jika semuanya tidak bergantung pada kebarangkalian awal, maka dalam setiap lajur matriks semua elemen adalah sama dan mengikut (109), dan ini, menurut Teorem 11, bermakna itu adalah matriks primitif, iaitu rantai ini. adalah asiklik.

Daripada perkara di atas, maka Teorem 11 boleh dirumuskan seperti berikut:

Teorem 11". 1. Agar semua kebarangkalian mutlak yang menghadkan wujud dalam rantai Markov homogen untuk sebarang kebarangkalian awal, adalah perlu dan mencukupi bahawa rantai itu tetap.

2. Untuk mengehadkan kebarangkalian mutlak wujud dalam rantai Markov homogen untuk sebarang kebarangkalian awal dan tidak bergantung pada kebarangkalian awal ini, adalah perlu dan mencukupi bahawa rantai itu tetap.

3. Agar rantai Markov homogen mempunyai kebarangkalian mutlak pengehad positif untuk sebarang kebarangkalian awal dan kebarangkalian pengehad ini bebas daripada yang awal, adalah perlu dan mencukupi bahawa rantai itu menjadi akiklik.

5. Sekarang pertimbangkan rantai Markov homogen jenis umum dengan matriks kebarangkalian peralihan.

Marilah kita mengambil bentuk normal (69) matriks dan menandakannya dengan indeks imprimitiviti matriks dalam (69). Biarkan menjadi gandaan sepunya terkecil bagi integer. Kemudian matriks tidak mempunyai nombor ciri yang sama dalam modulus kepada satu, tetapi berbeza daripada satu, iaitu, ia adalah matriks biasa; dalam kes ini - penunjuk terkecil di mana - matriks yang betul. Kami memanggil nombor itu tempoh rantaian Markov homogen yang diberikan dan... Sebaliknya, jika dan , ditakrifkan oleh formula (110) dan (110").

Purata kebarangkalian mutlak marginal sepadan dengan keadaan tidak penting sentiasa sifar.

Jika bentuk normal matriks ialah nombor (dan hanya dalam kes ini), purata mengehadkan kebarangkalian mutlak tidak bergantung pada kebarangkalian awal dan ditentukan secara unik daripada persamaan (111).

Artikel ini memberi idea umum tentang cara menjana teks menggunakan pemodelan proses Markov. Khususnya, kami akan memperkenalkan rantai Markov dan, sebagai amalan, kami akan melaksanakan penjana teks kecil dalam Python.

Sebagai permulaan, mari kita tulis definisi yang diperlukan, tetapi belum begitu jelas, dari halaman Wikipedia untuk sekurang-kurangnya memahami secara kasar apa yang kita hadapi:

proses Markov t t

rantai Markov

Apakah maksud semua ini? Mari kita fikirkan.

Asas

Contoh pertama adalah sangat mudah. Menggunakan ayat daripada buku kanak-kanak, kami akan menguasai konsep asas rantai Markov dan juga mentakrifkan apa itu dalam konteks kami badan, pautan, taburan kebarangkalian dan histogram. Walaupun cadangan diberikan pada Inggeris, intipati teori akan mudah difahami.

Cadangan ini ialah bingkai, iaitu, asas di mana teks akan dijana pada masa hadapan. Ia terdiri daripada lapan perkataan, tetapi pada masa yang sama perkataan yang unik hanya lima sahaja pautan(kita bercakap tentang Markovian rantai). Untuk kejelasan, mari warnakan setiap pautan dalam warnanya sendiri:

Dan kami menulis bilangan kejadian setiap pautan dalam teks:

Dalam gambar di atas anda boleh melihat bahawa perkataan "ikan" muncul dalam teks 4 kali lebih kerap daripada setiap perkataan lain ( "Satu", "dua", "merah", "biru"). Iaitu, kebarangkalian menemui perkataan dalam korpus kita "ikan" 4 kali lebih tinggi daripada kebarangkalian menemui setiap perkataan lain yang ditunjukkan dalam rajah. Bercakap dalam bahasa matematik, kita boleh menentukan hukum taburan pembolehubah rawak dan mengira dengan kebarangkalian apa salah satu perkataan akan muncul dalam teks selepas perkataan semasa. Kebarangkalian dikira seperti berikut: kita perlu membahagikan bilangan kemunculan perkataan yang kita perlukan dalam korpus dengan jumlah bilangan semua perkataan di dalamnya. Untuk perkataan "ikan" kebarangkalian ini ialah 50% kerana ia muncul 4 kali dalam ayat 8 perkataan. Untuk setiap pautan yang tinggal, kebarangkalian ini ialah 12.5% ​​​​(1/8).

Secara grafik mewakili pengedaran pembolehubah rawak mungkin menggunakan histogram. Dalam kes ini, kekerapan berlakunya setiap pautan dalam ayat dapat dilihat dengan jelas:

Jadi, teks kami terdiri daripada perkataan dan pautan unik, dan kami memaparkan taburan kebarangkalian penampilan setiap pautan dalam ayat pada histogram. Jika anda fikir ia tidak patut diganggu dengan statistik, baca terus. Dan mungkin ia akan menyelamatkan nyawa anda.

Intipati definisi

Sekarang mari kita tambahkan elemen teks kita yang sentiasa tersirat, tetapi tidak disuarakan dalam ucapan seharian - permulaan dan akhir ayat:

Mana-mana ayat mengandungi "permulaan" dan "akhir" yang tidak kelihatan ini, mari tambahkannya sebagai pautan kepada pengedaran kami:

Mari kita kembali kepada definisi yang diberikan pada permulaan artikel:

proses Markov- proses rawak, evolusi yang selepas mana-mana tetapkan nilai parameter masa t tidak bergantung kepada evolusi yang terdahulu t, dengan syarat bahawa nilai proses pada masa ini ditetapkan.

rantai Markov - kes khas Proses Markov, apabila ruang keadaannya adalah diskret (iaitu, tidak lebih daripada boleh dikira).

Jadi apa maksudnya? Secara kasarnya, kami memodelkan proses di mana keadaan sistem pada masa berikutnya hanya bergantung pada keadaannya pada saat semasa, dan tidak bergantung dalam apa-apa cara pada semua keadaan sebelumnya.

Bayangkan apa yang ada di hadapan anda tingkap, yang hanya memaparkan keadaan semasa sistem (dalam kes kami, ia adalah satu perkataan), dan anda perlu menentukan perkataan seterusnya hanya berdasarkan data yang dibentangkan dalam tetingkap ini. Dalam korpus kami, perkataan mengikut satu sama lain mengikut pola berikut:

Oleh itu, pasangan perkataan terbentuk (walaupun akhir ayat mempunyai pasangan sendiri - makna kosong):

Mari kumpulkan pasangan ini mengikut perkataan pertama. Kita akan melihat bahawa setiap perkataan mempunyai set pautan sendiri, yang dalam konteks ayat kita boleh ikut dia:

Mari kita membentangkan maklumat ini dengan cara lain - untuk setiap pautan kami menetapkan tatasusunan semua perkataan yang mungkin muncul dalam teks selepas pautan ini:

Mari kita lihat lebih dekat. Kami melihat bahawa setiap pautan mempunyai perkataan itu boleh datang selepasnya dalam ayat. Jika kita menunjukkan rajah di atas kepada orang lain, orang itu mungkin boleh membina semula kita tawaran awal, iaitu badan.

Contoh. Mari kita mulakan dengan perkataan "Mula". Seterusnya, pilih perkataan "Satu", kerana mengikut skim kami ini adalah satu-satunya perkataan, yang boleh mengikut permulaan ayat. Di sebalik Firman "Satu" juga hanya satu perkataan boleh mengikuti - "ikan". Sekarang cadangan baharu dalam versi pertengahan kelihatan seperti "Satu ikan". Selanjutnya keadaan menjadi lebih rumit - untuk "ikan" boleh ada perkataan dengan kebarangkalian yang sama sebanyak 25% "dua", "merah", "biru" dan akhir ayat "Tamat". Jika kita mengandaikan bahawa perkataan seterusnya ialah "dua", pembinaan semula akan diteruskan. Tetapi kita boleh memilih pautan "Tamat". Dalam kes ini, berdasarkan skema kami, ayat akan dijana secara rawak yang sangat berbeza daripada korpus - "Satu ikan".

Kami baru sahaja mensimulasikan proses Markov - kami menentukan setiap perkataan seterusnya hanya berdasarkan pengetahuan tentang perkataan semasa. Untuk memahami bahan sepenuhnya, mari bina gambar rajah yang menunjukkan kebergantungan antara unsur-unsur di dalam korpus kita. Bujur mewakili pautan. Anak panah membawa kepada pautan berpotensi yang boleh mengikut perkataan dalam bujur. Di sebelah setiap anak panah ialah kebarangkalian pautan seterusnya akan muncul selepas yang semasa:

Hebat! Kami telah belajar maklumat yang diperlukan untuk meneruskan dan menganalisis model yang lebih kompleks.

Memperluaskan asas perbendaharaan kata

Dalam bahagian artikel ini kami akan membina model mengikut prinsip yang sama seperti sebelumnya, tetapi dalam penerangan kami akan meninggalkan beberapa langkah. Jika anda menghadapi sebarang kesulitan, kembali kepada teori di blok pertama.

Mari kita ambil empat lagi petikan daripada pengarang yang sama (juga dalam bahasa Inggeris, ia tidak akan merugikan kita):

“Hari ini awak adalah awak. Itu lebih benar daripada benar. Tidak ada seorang pun yang hidup yang lebih daripada kamu.”

“Awak ada otak dalam kepala awak. Anda mempunyai kaki dalam kasut anda. Anda boleh memandu sendiri ke mana-mana arah yang anda pilih. Awak sendiri."

“Semakin banyak bahawa anda membaca semakin banyak perkara yang anda akan tahu. Lebih banyak yang anda pelajari, lebih banyak tempat yang anda akan pergi."

“Fikir kiri dan fikir kanan dan fikir rendah dan fikir tinggi. Oh, anda fikir anda boleh berfikir jika anda mencuba.”

Kerumitan korpus telah meningkat, tetapi dalam kes kami ini hanya tambahan - kini penjana teks akan dapat menghasilkan ayat yang lebih bermakna. Hakikatnya ialah dalam mana-mana bahasa terdapat perkataan yang muncul dalam pertuturan lebih kerap daripada yang lain (contohnya, kami menggunakan preposisi "dalam" lebih kerap daripada perkataan "kriogenik"). Bagaimana lebih banyak perkataan dalam korpus kami (dan oleh itu kebergantungan di antara mereka), lebih banyak maklumat penjana mempunyai tentang perkataan yang paling mungkin muncul dalam teks selepas perkataan semasa.

Cara paling mudah untuk menerangkan perkara ini adalah dari sudut pandangan program. Kami tahu bahawa untuk setiap pautan terdapat satu set perkataan yang boleh mengikutinya. Dan juga, setiap perkataan dicirikan oleh bilangan penampilannya dalam teks. Kami memerlukan beberapa cara untuk menangkap semua maklumat ini di satu tempat; Untuk tujuan ini, kamus yang menyimpan pasangan "(kunci, nilai)" adalah paling sesuai. Kunci kamus akan merekodkan keadaan semasa sistem, iaitu, salah satu pautan badan (contohnya, "yang" dalam gambar di bawah); dan kamus lain akan disimpan dalam nilai kamus. Dalam kamus bersarang, kunci ialah perkataan yang boleh muncul dalam teks selepas pautan semasa korpus ( "berfikir" Dan "lebih" boleh pergi selepas dalam teks "yang"), dan nilai ialah bilangan kemunculan perkataan ini dalam teks selepas pautan kami (perkataan "berfikir" muncul dalam teks selepas perkataan "yang" 1 kali, perkataan "lebih" selepas perkataan itu "yang"- 4 kali):

Baca semula perenggan di atas beberapa kali untuk memastikan anda memahaminya dengan tepat. Sila ambil perhatian bahawa kamus bersarang dalam kes ini adalah histogram yang sama, ia membantu kami menjejaki pautan dan kekerapan kejadiannya dalam teks berbanding perkataan lain. Perlu diingatkan bahawa asas perbendaharaan kata sedemikian adalah sangat kecil untuk penjanaan teks yang betul bahasa semula jadi- ia sepatutnya mengandungi lebih daripada 20,000 perkataan, atau lebih baik lagi, lebih daripada 100,000 Dan lebih baik lagi, lebih daripada 500,000 tetapi mari kita lihat asas perbendaharaan kata yang kita ada.

Rantaian Markov dalam kes ini dibina sama dengan contoh pertama - setiap perkataan seterusnya dipilih hanya berdasarkan pengetahuan tentang perkataan semasa, semua perkataan lain tidak diambil kira. Tetapi terima kasih kepada penyimpanan dalam kamus data tentang perkataan yang muncul lebih kerap daripada yang lain, kami boleh menerima apabila memilih keputusan termaklum. Mari lihat contoh khusus:

Lagi:

Iaitu, jika perkataan semasa adalah perkataan "lebih", selepas itu boleh terdapat perkataan dengan kebarangkalian yang sama sebanyak 25% "benda" Dan "tempat", dan dengan kebarangkalian 50% - perkataan "itu". Tetapi kebarangkalian semuanya boleh sama:

Fikirkan:

Bekerja dengan Windows

Sehingga kini, kami hanya menganggap tingkap sebesar satu perkataan. Anda boleh meningkatkan saiz tetingkap supaya penjana teks menghasilkan lebih banyak ayat "disahkan". Ini bermakna semakin besar tingkap, semakin kecil sisihan dari badan semasa penjanaan. Meningkatkan saiz tetingkap sepadan dengan peralihan rantai Markov kepada lebih banyak perintah tinggi. Sebelum ini, kami membina litar tertib pertama untuk tetingkap, dua perkataan akan menghasilkan litar tertib kedua, tiga akan menghasilkan litar tertib ketiga, dan seterusnya.

Tingkap- ini adalah data dalam keadaan semasa sistem yang digunakan untuk membuat keputusan. Jika kita menggabungkan tetingkap besar dan set data yang kecil, kemungkinan besar kita akan mendapat ayat yang sama setiap kali. Mari kita ambil asas perbendaharaan kata dari contoh pertama kami dan kembangkan tetingkap kepada saiz 2:

Sambungan ini bermakna setiap tetingkap kini hanya mempunyai satu pilihan untuk keadaan sistem yang seterusnya - tidak kira apa yang kami lakukan, kami akan sentiasa menerima hukuman yang sama, sama dengan kes kami. Oleh itu, untuk bereksperimen dengan tingkap, dan untuk penjana teks untuk mengembalikan kandungan unik, sediakan asas perbendaharaan kata sekurang-kurangnya 500,000 patah perkataan.

Pelaksanaan dalam Python

Struktur data diktogram

Diktogram (dikt ialah jenis data kamus terbina dalam Python) akan memaparkan hubungan antara pautan dan kekerapan kejadiannya dalam teks, iaitu pengedarannya. Tetapi pada masa yang sama, ia akan mempunyai harta kamus yang kami perlukan - masa pelaksanaan program tidak akan bergantung pada jumlah data input, yang bermaksud kami mencipta algoritma yang berkesan.

Import Diktogram kelas rawak(dict): def __init__(self, iterable=None): # Mulakan pengedaran kami sebagai objek kelas baharu, # tambah elemen sedia ada super(Dictogram, self).__init__() self.types = 0 # bilangan kunci unik dalam pengedaran self.tokens = 0 # jumlah kuantiti semua perkataan dalam pengedaran jika boleh iterable: self.update(iterable) def update(self, iterable): # Kemas kini pengedaran dengan elemen daripada set data # iterable sedia ada untuk item dalam iterable: if item dalam self: self += 1 self .token += 1 else: self = 1 self.types += 1 self.token += 1 def count(self, item): # Kembalikan nilai pembilang item atau 0 jika item dalam self: return self return 0 def return_random_word (diri): random_key = random.sample(self, 1) # Cara lain: # random.choice(histogram.keys()) return random_key def return_weighted_random_word(self): # Jana nombor rawak pseudo antara 0 dan (n- 1), # dengan n ialah bilangan umum perkataan random_int = random.randint(0, self.tokens-1) index = 0 list_of_keys = self.keys() # print "random index:", random_int untuk i dalam julat(0 , self.types): indeks += self] # print the index if(index > random_int): # print list_of_keys[i] return list_of_keys[i]

Pembina struktur Dictogram boleh menghantar sebarang objek yang boleh diulang. Unsur-unsur objek ini akan menjadi perkataan untuk memulakan Diktogram, contohnya, semua perkataan daripada buku. Dalam kes ini, kami mengira elemen supaya untuk mengakses mana-mana daripadanya, kami tidak perlu melalui keseluruhan set data setiap kali.

Kami juga membuat dua fungsi untuk kembali perkataan rawak. Satu fungsi memilih kunci rawak dalam kamus, dan satu lagi, dengan mengambil kira bilangan kemunculan setiap perkataan dalam teks, mengembalikan perkataan yang kita perlukan.

Struktur rantai Markov

daripada histogram import Dictogram def make_markov_model(data): markov_model = dict() untuk i dalam julat(0, len(data)-1): jika data[i] dalam markov_model: # Hanya tambahkan pada pengedaran yang sedia ada markov_model].update( ]) else: markov_model] = Dictogram() return markov_model

Dalam pelaksanaan di atas, kami mempunyai kamus yang menyimpan tetingkap sebagai kunci dalam pasangan "(kunci, nilai)" dan pengedaran sebagai nilai dalam pasangan itu.

Struktur rantai Markov pesanan ke-n

daripada histogram import Dictogram def make_higher_order_markov_model(order, data): markov_model = dict() untuk i dalam julat(0, len(data)-order): # Buat tetingkap tetingkap = tuple(data) # Tambah pada kamus jika tetingkap masuk markov_model: # Lampirkan pada edaran sedia ada markov_model.update() else: markov_model = Dictogram() return markov_model

Sangat serupa dengan pesanan pertama rantai Markov, tetapi dalam kes ini kami menyimpan permotoran sebagai kunci dalam pasangan "(kunci, nilai)" dalam kamus. Kami menggunakannya dan bukannya senarai, kerana tuple dilindungi daripada sebarang perubahan, dan ini penting bagi kami - lagipun, kunci dalam kamus tidak sepatutnya berubah.

Penghuraian model

Bagus, kami telah melaksanakan kamus. Tetapi bagaimana kita boleh menjana kandungan berdasarkan keadaan semasa dan langkah ke keadaan seterusnya? Mari kita lihat model kami:

Dari histogram import Dictogram import rawak daripada koleksi import deque import re def generate_random_start(model): # Untuk menjana sebarang perkataan permulaan, nyahkomen baris: # return random.choice(model.keys()) # Untuk menjana perkataan permulaan "betul" , gunakan kod di bawah: # Betul perkataan awal- inilah yang merupakan permulaan ayat dalam korpus jika "END" dalam model: seed_word = "END" manakala seed_word == "END": seed_word = model["END"].return_weighted_random_word() return seed_word return rawak. pilihan(model .keys()) def generate_random_sentence(length, markov_model): current_word = generate_random_start(markov_model) ayat = untuk i dalam julat(0, length): current_dictogram = markov_model random_weighted_word = current_dictogram.return_weighted_random_word() current_word = ayat_rawak_berat. (perkataan_semasa) ayat = sentence.capitalize() return " ".join(ayat) + "."

ayat balik

Apa seterusnya?

Cuba fikirkan di mana anda boleh menggunakan penjana teks berdasarkan rantai Markov sendiri. Cuma jangan lupa bahawa perkara yang paling penting ialah cara anda menghuraikan model dan apakah sekatan khas yang anda tetapkan pada penjanaan. Pengarang artikel ini, sebagai contoh, semasa mencipta penjana tweet, menggunakan tetingkap besar, mengehadkan kandungan yang dihasilkan kepada 140 aksara, dan hanya menggunakan perkataan "betul" untuk memulakan ayat, iaitu, yang merupakan permulaan ayat dalam korpus. Kaedah huraian matematik
Proses rawak Markov dalam sistem dengan keadaan diskret (DS) bergantung pada titik masa (sebelum ini diketahui atau rawak) peralihan sistem dari keadaan ke keadaan boleh berlaku. Jika peralihan sistem dari keadaan ke keadaan mungkin pada saat-saat masa yang telah ditetapkan, kita sedang berurusan dengan rawak proses Markov dengan masa diskret. Jika peralihan boleh dilakukan pada bila-bila masa rawak, maka kita sedang menanganinya
proses Markov rawak dengan masa yang berterusan. Biarlah ada S sistem fizikal n, yang mungkin dalam S 1 , S 2 , …, negeri. Peralihan dari negeri ke negeri hanya boleh dilakukan pada saat-saat tertentu t 1 , t 2 , …, tk, mari kita sebut detik ini dalam langkah masa. Kami akan mempertimbangkan usaha sama dalam sistem S sebagai fungsi hujah integer 1, 2, ..., k, dengan hujah ialah nombor langkah.
Contoh: S 1 → S 2 → S 3 → S 2 .
Marilah kita bersetuju untuk menetapkan S i (k) – peristiwa yang terdiri daripada fakta bahawa selepas k langkah sistem berada dalam keadaan S i.
Untuk mana-mana k acara S 1 ( k), S 2 ( k) ,…, S n (k) bentuk kumpulan penuh acara dan adalah tidak serasi.

Sesuatu proses dalam sistem boleh diwakili sebagai rantaian peristiwa.
Contoh: S 1 (0) , S 2 (1) , S 3 (2) , S 5 (3) ,….
Urutan ini dipanggil rantai Markov , jika bagi setiap langkah kebarangkalian peralihan dari mana-mana keadaan S i dalam apa jua keadaan S j tidak bergantung pada bila dan bagaimana sistem itu sampai ke negeri ini S i.
Biarkan pada bila-bila masa selepas apa-apa k-sistem langkah ke- S mungkin berada di salah satu negeri S 1 , S 2 , …, negeri, iaitu satu peristiwa daripada kumpulan lengkap peristiwa boleh berlaku: S 1 (k), S 2 ( k) , …, negeri (k). Mari kita nyatakan kebarangkalian kejadian ini:
P 1 (1) = P(S 1 (1)); P 2 (1) = P(S 2 (1)); …; Pn(1) = P(negeri (k));
P 1 (2) = P(S 1 (2)); P 2 (2) = P(S 2 (2)); ...; Pn(2) = P(negeri (2));
P 1 (k) = P(S 1 (k)); P 2 (k) = P(S 2 (k)); …; Pn(k) = P(negeri (k)).
Adalah mudah untuk melihat bahawa untuk setiap nombor langkah syaratnya dipenuhi
P 1 (k) + P 2 (k) +…+ Pn(k) = 1.
Mari kita panggil kebarangkalian ini kebarangkalian nyatakan Oleh itu, tugas akan berbunyi seperti ini: cari kebarangkalian keadaan sistem untuk sebarang k.
Contoh. Biar ada beberapa jenis sistem yang boleh berada di mana-mana enam negeri. maka proses yang berlaku di dalamnya boleh digambarkan sama ada sebagai graf perubahan dalam keadaan sistem (Rajah 7.9, A), atau dalam bentuk graf keadaan sistem (Rajah 7.9, b).

A)

nasi. 7.9
Juga, proses dalam sistem boleh digambarkan sebagai urutan keadaan: S 1 , S 3 , S 2 , S 2 , S 3 , S 5 , S 6 , S 2 .
Kebarangkalian keadaan pada ( k+ 1) langkah ke hanya bergantung pada keadaan di k- m langkah.
Untuk sebarang langkah k terdapat beberapa kebarangkalian sistem beralih dari mana-mana keadaan ke mana-mana keadaan lain, mari kita panggil kebarangkalian ini kebarangkalian peralihan bagi rantai Markov.
Sebahagian daripada kebarangkalian ini akan menjadi 0 jika peralihan dari satu keadaan ke keadaan lain tidak dapat dilakukan dalam satu langkah.
Rantaian Markov dipanggil homogen, jika keadaan peralihan tidak bergantung pada nombor langkah, jika tidak, ia dipanggil heterogen.
Biarkan ada rantai Markov homogen dan biarkan sistem S mempunyai n keadaan yang mungkin: S 1 , …, negeri. Biarkan kebarangkalian peralihan ke keadaan lain dalam satu langkah diketahui bagi setiap keadaan, i.e. P ij(daripada S i V S j dalam satu langkah), maka kita boleh menulis kebarangkalian peralihan sebagai matriks.

. (7.1)
Di sepanjang pepenjuru matriks ini adalah kebarangkalian bahawa sistem beralih daripada keadaan S i dalam keadaan yang sama S i.
Menggunakan acara yang dimasukkan sebelum ini , kita boleh menulis kebarangkalian peralihan sebagai kebarangkalian bersyarat:
.
Jelas sekali, jumlah istilah dalam setiap baris matriks (1) adalah sama dengan satu, kerana peristiwa membentuk kumpulan lengkap peristiwa yang tidak serasi.

Apabila mempertimbangkan rantai Markov, serta semasa menganalisis Markov proses rawak, pelbagai graf keadaan digunakan (Rajah 7.10).

nasi. 7.10

Sistem ini boleh berada di mana-mana daripada enam negeri, manakala P ij ialah kebarangkalian sistem beralih daripada keadaan S i dalam sesebuah negeri S j. Untuk sistem ini, kami menulis persamaan bahawa sistem berada dalam keadaan tertentu dan keluar daripadanya pada masa itu t tidak keluar:

DALAM kes am rantai Markov adalah tidak homogen, iaitu kebarangkalian P ij perubahan dari langkah ke langkah. Katakan bahawa matriks kebarangkalian peralihan pada setiap langkah diberikan, maka kebarangkalian bahawa sistem itu S pada k-langkah ke dalam negeri S i, boleh didapati menggunakan formula

Mengetahui matriks kebarangkalian peralihan dan keadaan awal sistem, seseorang boleh mencari kebarangkalian keadaan selepas apa-apa k-langkah ke. Biarkan pada saat awal sistem berada dalam keadaan S m. Kemudian untuk t = 0
.
Mari cari kebarangkalian selepas langkah pertama. Dari negeri S m sistem akan pergi ke negeri S 1 , S 2 dll dengan kebarangkalian P m 1 , P m 2 , …, P mm, …, P mn. Kemudian selepas langkah pertama kebarangkalian akan sama

. (7.2)
Mari cari kebarangkalian keadaan selepas langkah kedua: . Kami akan mengira kebarangkalian ini menggunakan formula kebarangkalian penuh dengan hipotesis:
.
Hipotesis akan menjadi kenyataan berikut:

• selepas langkah pertama sistem berada dalam keadaan S 1 -H 1;
• selepas langkah kedua sistem berada dalam keadaan S 2 -H 2;
• selepas n daripada langkah ke-, sistem berada dalam keadaan S n -H n.

Kebarangkalian hipotesis diketahui daripada ungkapan (7.2). Kebarangkalian bersyarat peralihan kepada keadaan A bagi setiap hipotesis juga diketahui dan ditulis ke dalam matriks keadaan peralihan. Kemudian, menggunakan jumlah formula kebarangkalian, kita dapat:

Kebarangkalian mana-mana keadaan selepas langkah kedua:

(7.3)
Formula (7.3) merumuskan semua kebarangkalian peralihan P ij, tetapi hanya yang bukan sifar diambil kira. Kebarangkalian sebarang keadaan selepas k-langkah ke:

(7.4)
Oleh itu, kebarangkalian keadaan selepas k-langkah ditentukan oleh formula berulang(7.4) melalui kebarangkalian ( k – 1) langkah ke-

Tugasan 6. Satu matriks kebarangkalian peralihan untuk rantai Markov dalam satu langkah diberikan. Cari matriks peralihan litar yang diberi dalam tiga langkah .
Penyelesaian. Matriks peralihan sistem ialah matriks yang mengandungi semua kebarangkalian peralihan sistem ini:

Setiap baris matriks mengandungi kebarangkalian kejadian (peralihan daripada keadaan i dalam sesebuah negeri j), yang membentuk kumpulan lengkap, jadi jumlah kebarangkalian peristiwa ini adalah sama dengan satu:

Mari kita nyatakan dengan p ij (n) kebarangkalian bahawa hasil daripada n langkah (ujian) sistem akan bergerak dari keadaan i ke keadaan j. Sebagai contoh, p 25 (10) ialah kebarangkalian peralihan daripada keadaan kedua kepada keadaan kelima dalam sepuluh langkah. Ambil perhatian bahawa untuk n=1 kita memperoleh kebarangkalian peralihan p ij (1)=p ij .
Kami diberi tugas: mengetahui kebarangkalian peralihan p ij, cari kebarangkalian p ij (n) peralihan sistem dari keadaan i dalam sesebuah negeri j untuk n langkah. Untuk melakukan ini, kami memperkenalkan perantaraan (antara i Dan j) negeri r. Dengan kata lain, kita akan menganggap bahawa dari keadaan awal i untuk m langkah sistem akan pergi ke keadaan pertengahan r dengan kebarangkalian p ij (n-m), selepas itu, untuk selebihnya n-m langkah daripada keadaan pertengahan r ia akan pergi ke keadaan akhir j dengan kebarangkalian p ij (n-m) . Menggunakan jumlah formula kebarangkalian kita dapat:
.
Formula ini dipanggil kesamaan Markov. Dengan menggunakan formula ini, anda boleh mencari semua kebarangkalian p ij (n), dan, akibatnya, matriks P n itu sendiri. Oleh kerana kalkulus matriks membawa kepada matlamat dengan lebih cepat, kami menulis hubungan matriks yang terhasil daripada formula yang terhasil dalam bentuk umum.
Mari kita mengira matriks peralihan rantai Markov dalam tiga langkah menggunakan formula yang terhasil:

Jawapan:.

Tugasan No 1. Matriks kebarangkalian peralihan rantai Markov mempunyai bentuk:
.
Taburan ke atas keadaan pada masa t=0 ditentukan oleh vektor:
π 0 =(0.5; 0.2; 0.3)
Cari: a) taburan mengikut keadaan pada momen t=1,2,3,4.
c) pengagihan pegun.