Téměř úplně rozložitelný Markovův řetězec - Nearly completely decomposable Markov chain - Wikipedia

v teorie pravděpodobnosti, a téměř úplně rozložitelný (NCD) Markovův řetězec je Markovův řetězec kde lze stavový prostor rozdělit takovým způsobem, že k pohybu uvnitř oddílu dochází mnohem častěji než k pohybu mezi oddíly.^[1] Obzvláště účinné algoritmy existují pro výpočet stacionární distribuce markovských řetězců s touto vlastností.^[2]

Definice

Ando a Rybář definovat zcela rozložitelnou matici jako matici, kde „identické přeskupení řádků a sloupců ponechá sadu čtverců dílčí matice na hlavní úhlopříčka a nuly všude jinde. “Téměř úplně rozložitelná matice je ta, kde identické přeskupení řádků a sloupců ponechává sadu čtvercových submatic na hlavní úhlopříčce a malá nenulová všude jinde.^[3][4]

Příklad

A Markovův řetězec s přechodová matice

${ displaystyle P = { begin {pmatrix} { frac {1} {2}} & { frac {1} {2}} & 0 & 0 { frac {1} {2}} & { frac { 1} {2}} & 0 & 0 0 & 0 & { frac {1} {2}} & { frac {1} {2}} 0 & 0 & { frac {1} {2}} & { 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}} a 0 & - { frac {1} {2}} end {pmatrix}}}$

je téměř úplně rozložitelný, pokud ε je malý (řekněme 0,1).^[5]

Stacionární distribuční algoritmy

Pro řetězce NCD Markov byly navrženy speciální iterační algoritmy^[2] ačkoli víceúrovňový algoritmus, univerzální algoritmus,^[6] bylo experimentálně prokázáno, že je konkurenceschopné a v některých případech výrazně rychlejší.^[7]

Viz také

• Hrudkovatelnost

Reference