Absorpční Markovův řetěz - Absorbing Markov chain

V matematické teorii pravděpodobnost, an absorbující Markovův řetězec je Markovův řetězec ve kterém každý stát může dosáhnout absorbujícího stavu. Absorpční stav je stav, který po zadání nelze opustit.
Stejně jako obecné Markovovy řetězce mohou existovat Markovovy řetězce absorbující nepřetržitý čas s nekonečným stavovým prostorem. Tento článek se však soustředí na případ diskrétního stavu diskrétního stavu a prostoru.
Formální definice
Markovův řetěz je absorbující řetěz, pokud[1][2]
- existuje alespoň jeden absorbující stav a
- je možné přejít z jakéhokoli stavu do alespoň jednoho absorbujícího stavu v konečném počtu kroků.
V absorpčním Markovově řetězci se stav, který neabsorbuje, nazývá přechodný.
Kanonická forma
Nechte absorbovat Markovův řetězec s přechodovou maticí P mít t přechodné stavy a r absorbující stavy. Pak
kde Q je t-podle-t matice, R je nenulová t-podle-r matice, 0 je r-podle-t nulová matice a Jár je r-podle-r matice identity. Tím pádem, Q popisuje pravděpodobnost přechodu z nějakého přechodného stavu do jiného while R popisuje pravděpodobnost přechodu z nějakého přechodného stavu do nějakého absorbujícího stavu.
Základní matice
Základní vlastností absorpčního Markovova řetězce je očekávaný počet návštěv přechodného stavu j počínaje přechodným stavem i (než se vstřebá). Pravděpodobnost přechodu z i na j přesně k kroky je (i,j) - vstup z Qk. Shrnutí pro všechny k (od 0 do ∞) získá základní matici označenou N. To lze dokázat
kde Ját je t-podle-t matice identity. (i, j) zadání matice N je očekávaný počet stavů řetězce jznamená, že řetěz začal ve stavu i. S maticí N v ruce lze snadno získat další vlastnosti Markovova řetězce.[2]
Rozdíly v počtu návštěv
Rozptyl v počtu návštěv přechodného stavu j se spuštěním v přechodném stavu i (než je absorbován) je (i,j) - vstup matice
kde Ndg je diagonální matice se stejnou úhlopříčkou jako N a Nčtvereční je Produkt Hadamard z N se sebou (tj. každý záznam z N je na druhou).
Očekávaný počet kroků
Očekávaný počet kroků před absorpcí při spuštění v přechodném stavu i je ith vstup vektoru
kde 1 je délka-t vektor sloupce, jehož položky jsou všechny 1.
Odchylka od počtu kroků
Rozptyl počtu kroků před absorpcí při spuštění v přechodném stavu i je ith vstup vektoru
kde tčtvereční je Produkt Hadamard z t se sebou (tj. každý záznam z t je na druhou).
Přechodné pravděpodobnosti
Pravděpodobnost návštěvy přechodného stavu j při spuštění v přechodném stavu i je (i,j) - vstup matice
kde Ndg je diagonální matice se stejnou úhlopříčkou jako N.
Absorpční pravděpodobnosti
Další vlastností je pravděpodobnost absorpce v absorpčním stavu j při zahájení z přechodného stavu i, který je (i,j) - vstup matice
Příklady
Generování řetězců
Zvažte postup opakovaného převrácení a spravedlivá mince dokud se neobjeví sekvence (hlavy, ocasy, hlavy). Tento proces je modelován absorpčním Markovovým řetězcem s přechodovou maticí
První stav představuje prázdný řetězec, druhý stav řetězec „H“, třetí stav řetězec „HT“ a čtvrtý stav řetězec „HTH“. Ačkoliv ve skutečnosti mince vyletí po generování řetězce „HTH“, perspektiva absorpčního Markovova řetězce je v tom, že proces přešel do absorpčního stavu představujícího řetězec „HTH“, a proto nemůže odejít.
Pro tento absorbující Markovův řetězec je základní matice
Očekávaný počet kroků od každého přechodného stavu je
Očekávaný počet mincí mincí před pozorováním sekvence (hlavy, ocasy, hlavy) je tedy 10, což je položka pro stát představující prázdný řetězec.

Hazardní hry
Hry založené zcela na náhodě mohou být modelovány absorbujícím markovským řetězcem. Klasickým příkladem je starodávná indická desková hra Hadi a žebříky. Graf vpravo[3] zakreslí pravděpodobnostní hmotu v osamělém absorbujícím stavu, který představuje poslední čtverec, když je přechodová matice zvýšena na větší a větší síly. Chcete-li určit očekávaný počet tahů k dokončení hry, spočítejte vektor t jak je popsáno výše a prozkoumejte tStart, což je přibližně 39,2.
Klinika infekčních nemocí
Příklad testování infekčních nemocí, ať už v krevních produktech nebo na lékařských klinikách, se často vyučuje jako příklad absorpčního Markovova řetězce.[4] Veřejný model Centra pro kontrolu a prevenci nemocí (CDC) pro HIV a pro hepatitidu B, například,[5] ilustruje vlastnost, že absorpce Markovových řetězců může vést k detekci nemoci, ve srovnání se ztrátou detekce jinými prostředky.
Ve standardním modelu CDC má Markovův řetězec pět stavů, stav, ve kterém je jedinec neinfikovaný, pak stav s infikovaným, ale nedetekovatelným virem, stav s detekovatelným virem a absorpční stavy, kdy byl z kliniky ukončen / ztracen, nebo že byl detekován (cíl). Typická míra přechodu mezi markovskými státy je pravděpodobnost str za jednotku času infekce virem, w pro rychlost odstraňování období okna (čas do detekce viru), q - pro míru ukončení / ztráty ze systému a - d pro detekci, za předpokladu typické rychlosti ve kterém zdravotnický systém provádí testy dotyčného krevního produktu nebo pacientů.

Z toho vyplývá, že můžeme „projít“ Markovovým modelem, abychom identifikovali celkovou pravděpodobnost detekce osoby začínající jako nezjištěnou, vynásobením pravděpodobností přechodu do každého dalšího stavu modelu jako:
.
Následný celkový absolutní počet falešně negativních testů - primární obava CDC - by pak byla míra testů vynásobená pravděpodobností dosažení infikovaného, ale nezjistitelného stavu, krát doba pobytu v infikovaném nezjistitelném stavu:
.
Viz také
Reference
- ^ A b Grinstead, Charles M .; Snell, J. Laurie (Červenec 1997). „Ch. 11: Markov Chains“ (PDF). Úvod do pravděpodobnosti. Americká matematická společnost. ISBN 978-0-8218-0749-1.
- ^ A b Kemeny, John G.; Snell, J. Laurie (Červenec 1976) [1960]. „Ch. 3: Absorpční Markovovy řetězy“. In Gehring, F. W .; Halmos, P. R. (eds.). Konečné Markovovy řetězy (Druhé vydání.). New York Berlin Heidelberg Tokio: Springer-Verlag. str.224. ISBN 978-0-387-90192-3.
- ^ Na základě definice uvedené v S. C. Althoen; L. King; K. Schilling (březen 1993). „Jak dlouhá je hra hadů a žebříků?“. Matematický věstník. Matematický věstník, sv. 77, č. 478. 78 (478): 71–76. doi:10.2307/3619261. JSTOR 3619261.
- ^ výsledky, hledání (1998-07-28). Markovovy řetězy. Cambridge: Cambridge University Press. ISBN 9780521633963.
- ^ Sanders, Gillian D .; Anaya, Henry D .; Asch, Steven; Hoang, Tuyen; Golden, Joya F .; Bayoumi, Ahmed M .; Owens, Douglas K. (červen 2010). „Nákladová efektivnost strategií pro zlepšení testování HIV a příjem výsledků: Ekonomická analýza randomizované kontrolované studie“. Journal of General Internal Medicine. 25 (6): 556–563. doi:10.1007 / s11606-010-1265-5. ISSN 0884-8734. PMC 2869414. PMID 20204538.