Hrudkovatelnost - Lumpability

v teorie pravděpodobnosti, hrudkovatelnost je metoda pro zmenšení velikosti stavového prostoru některých Markovovy řetězce nepřetržitého času, poprvé publikováno Kemeny a Snell.^[1]

Definice

Předpokládejme, že úplný stavový prostor a Markovův řetězec je rozdělena na disjunktní podmnožiny států, kde jsou tyto podmnožiny označeny t_i. Toto tvoří a rozdělit ${displaystyle scriptstyle {T = {t_ {1}, t_ {2}, ldots}}}$ států. Stavový prostor i sbírka podmnožin mohou být buď konečné, nebo spočetně nekonečné. ${displaystyle {X_ {i}}}$ je hrudkovitý s ohledem na oddíl T právě a jen pro jakékoli podmnožiny t_i a t_j v oddílu a pro všechny státy n, n ‘ v podmnožině t_i,

${displaystyle sum _ {min t_ {j}} q (n, m) = součet _ {min t_ {j}} q (n ', m),}$

kde q(já, j) je míra přechodu ze stavu i do stavu j.^[2]

Podobně pro a stochastická matice P, P je hrudkovitá matice na oddílu T právě a jen pro jakékoli podmnožiny t_i a t_j v oddílu a pro všechny státy n, n ‘ v podmnožině t_i,

${displaystyle sum _ {min t_ {j}} p (n, m) = součet _ {min t_ {j}} p (n ', m),}$

kde p(já, j) je pravděpodobnost přechodu ze stavu i do stavu j.^[3]

Příklad

Zvažte matici

${displaystyle P = {egin {pmatrix} {frac {1} {2}} & {frac {3} {8}} & {frac {1} {16}} & {frac {1} {16}} { frac {7} {16}} & {frac {7} {16}} & 0 & {frac {1} {8}} {frac {1} {16}} & 0 & {frac {1} {2}} & { frac {7} {16}} 0 a {frac {1} {16}} a {frac {3} {8}} a {frac {9} {16}} konec {pmatrix}}}$

a všimněte si, že je v oddílu hrudkovitý t = {(1,2), (3,4)} takže píšeme

${displaystyle P_ {t} = {egin {pmatrix} {frac {7} {8}} & {frac {1} {8}} {frac {1} {16}} & {frac {15} {16} } konec {pmatrix}}}$

a zavolat P_t soustředěná matice P na t.

Postupně zpracovatelné procesy

V roce 2012, Katehakis a Smit objevili Postupně lumpovatelné procesy, pro které lze získat stacionární pravděpodobnosti postupným výpočtem stacionárních pravděpodobností úmyslně konstruované sekvence Markovových řetězců. Každý z těchto řetězců má (obvykle mnohem) menší stavový prostor, což přináší významné výpočetní vylepšení. Tyto výsledky mají mnoho spolehlivých aplikací a modely a problémy se zařazováním do fronty.^[4]

Kvazi-hrudkovatelnost

Franceschinis a Muntz představili kvazi-hrudkovatelnost, vlastnost, díky které díky malé změně v matici rychlosti je řetěz hrudkovitý.^[5]

Viz také

• Téměř úplně rozložitelný Markovův řetězec

Reference