Deyarli butunlay ajraladigan Markov zanjiri - Nearly completely decomposable Markov chain

Yilda ehtimollik nazariyasi, a deyarli ajraladigan (NCD) Markov zanjiri a Markov zanjiri bu erda holat-bo'shliq shunday bo'linishi mumkinki, bo'lim ichida harakat bo'linishlar orasidagi harakatga qaraganda ancha tez-tez sodir bo'ladi.^[1] Hisoblash uchun ayniqsa samarali algoritmlar mavjud statsionar taqsimot ushbu xususiyatga ega bo'lgan Markov zanjirlari.^[2]

Ta'rif

Ando va Fisher to'liq parchalanadigan matritsani aniqlang, bu erda "satrlar va ustunlarning bir xil qayta tuzilishi kvadrat to'plamini qoldiradi submatrikalar ustida asosiy diagonali "Deyarli butunlay parchalanadigan matritsa - bu satrlar va ustunlarning bir xil qayta tuzilishi asosiy diagonalda kvadrat submatrikalar to'plamini qoldiradigan matritsa. kichik nollar hamma joyda.^[3][4]

Misol

A Markov zanjiri bilan o'tish matritsasi

${ displaystyle P = { begin {pmatrix} { frac {1} {2}} & { frac {1} {2}} & 0 & 0 { frac {1} {2}} va { frac { 1} {2}} & 0 & 0 0 & 0 & { frac {1} {2}} & { frac {1} {2}} 0 & 0 & { frac {1} {2}} va { frac {1 } {2}} end {pmatrix}} + epsilon { begin {pmatrix} - { frac {1} {2}} & 0 & { frac {1} {2}} & 0 0 & - { frac {1} {2}} & 0 & { frac {1} {2}} { frac {1} {2}} & 0 & - { frac {1} {2}} & 0 0 & { frac {1} {2}} & 0 & - { frac {1} {2}} end {pmatrix}}}$

agar deyarli ajralsa ε kichik (masalan, 0,1).^[5]

Statsionar tarqatish algoritmlari

Markov zanjiri uchun maxsus maqsadli takroriy algoritmlar ishlab chiqilgan^[2] ko'p darajali algoritm bo'lsa ham, umumiy maqsadli algoritm,^[6] eksperimental ravishda raqobatbardosh va ba'zi hollarda sezilarli darajada tezroq ekanligi ko'rsatilgan.^[7]

Shuningdek qarang

• Yopish qobiliyati

Adabiyotlar