Lineární rovnice a procesy Markovovy řetězce Matematika I – 10a Lineární procesy Jan Slovák Masarykova univerzita Fakulta informatiky 19. 11. 2012 Lineární rovnice a procesy Markovovy řetězce Obsah přednášky 1 Lineární rovnice a procesy 2 Markovovy řetězce Lineární rovnice a procesy Markovovy řetězce Iterované procesy Procesy bývají popsány prostřednictvím lineární operace pro jednotlivá časová období (linearizovaný model). Budeme chtít studovat jeho chování během delší doby. Example Představme si, že zkoumáme nějaký systém jednotlivců (pěstovaná zvířata, hmyz, buněčné kultury apod) rozdělený do m skupin (třeba podle stáří, fází vývoje hmyzu apod.). Stav xn je tedy dán vektorem (a1, . . . , am) závisejícím na okamžiku tn, ve kterém systém pozorujeme. Lineární model vývoje takového systému je dán maticí A dimenze n, která zadává změnu vektoru xn na xn+1 = A · xn při přírůstku času z tk na tk+1. Lineární rovnice a procesy Markovovy řetězce Příkladem lineárních procesů je Leslieho model růstu s maticí (pro m = 5) A =       f1 f2 f3 f4 f5 τ1 0 0 0 0 0 τ2 0 0 0 0 0 τ3 0 0 0 0 0 τ4 0       , ve které: fi označuje relativní plodnost příslušné věkové skupiny (ve sledovaném časovém skoku vznikne z N jedinců v i–té skupině fi N jedinců nových, tj. ve skupině první); τi je relativní úmrtnost i-té skupiny během jednoho období. Lineární rovnice a procesy Markovovy řetězce Předpokládejme chvíli, že pro konkrétní koeficienty může být dominantní vlastní číslo λ0 vetší než jedna, zatímco absolutní hodnoty ostatních vlastních čísel λi budou ostře menší než jedna. Iterace dávají pro každý vektor v = v0 + v1+ rozložený na vlastní vektory matice (pomíjíme teď složitější možnost různých algebraických a geometrických násobností jednotlivých vlastních čísel) ϕk (v) = λk 0v0 + λk 1v1 + . . . . V takovém případě při iteraci kroků našeho procesu dojde při libovolné počáteční hodnotě x0 k postupnému vymizení všech komponent v jednotlivých vlastních podprostorech kromě v0. Poměrné proporce rozložení populace do věkových skupin se budou blížit poměrům komponent vlastního vektoru k dominantnímu vlastnímu číslu. Lineární rovnice a procesy Markovovy řetězce Například pro matici (uvědomme si význam jednotlivých koeficientů) A =       0 0.2 0.8 0.6 0 0.95 0 0 0 0 0 0.8 0 0 0 0 0 0.7 0 0 0 0 0 0.6 0       vyjdou vlastní hodnoty přibližně 1.03, 0, −0.5, −0, 27 + 0.74i, −0.27 − 0.74i s velikostmi 1.03, 0, 0.5, 0.78, 0.78 a vlastní vektor příslušný dominantnímu vlastnímu číslu je přibližně x = (30 27 21 14 8). Zvolili jsme rovnou jediný vlastní vektor se součtem souřadnic rovným 100, zadává nám proto přímo výsledné procentní rozložení populace. Lineární rovnice a procesy Markovovy řetězce Častý případ lineárních procesů je popis systému, který se může nacházet v m různých stavech s různou pravděpodobností. V jistém okamžiku je ve stavu s pravděpodobností ai pro stav i a k přechodu z možného stavu i do stavu j dojde s pravděpodobností tij . Popis procesu: V čase n je systém popsán pravděpodobnostním vektorem xn = (a1, . . . , am). Tj. komponenty vektoru x jsou reálná nezáporná čísla a jejich součet je roven jedné. Komponenty udávají rozdělení pravděpodobnosti jednotlivých možností stavů systému. Rozdělení pravděpodobností pro čas n + 1 je dáno vynásobením pravděpodobnostní maticí přechodu T = (tij ), tj. xn+1 = T · xn. Protože vektor x zachycuje všechny možné stavy, budou všechny sloupce matice T tvořeny také pravděpodobnostními vektory. Lineární rovnice a procesy Markovovy řetězce Takovému procesu říkáme Markovův proces. Každý pravděpodobnostní vektor x je opět zobrazen na vektor se součtem souřadnic jedna: i,j tij xj = j ( i tij )xj = j xj = 1. Protože je součet řádků matice T vždy roven vektoru (1, . . . , 1), bude jednička zaručeně vlastním číslem matice T a k ní musí existovat vlastní vektor x0. Lineární rovnice a procesy Markovovy řetězce Theorem (Perronova–Frobeniova teorie) Nechť A je reálná čtvercová matice dimenze m s nezápornými prvky, jejíž nějaká mocnina Ak má samé kladné prvky. Pak platí 1 existuje reálné vlastní číslo λm matice A takové, že pro všchna ostatní vlastní čísla λ platí |λ| < λm, 2 vlastní číslo λm má algebraickou násobnost jedna, 3 vlastní podprostor odpovídající λm obsahuje vektor se všemi souřadnicemi kladnými 4 platí odhad mini j aij ≤ λm ≤ maxi j aij . Lineární rovnice a procesy Markovovy řetězce Důsledkem této věty pro Markovovy procesy s maticí, která nemá žádné nulové prvky (nebo jejíž některá mocnina má tuto vlastnost), je existence vlastního vektoru x∞ pro vlastní číslo 1, který je pravděpodobnostní přibližování hodnoty iterací Tkx0 k vektoru x∞ pro jakýkoliv pravděpodobnostní vektor x0. První tvrzení vyplývá přímo z kladnosti souřadnic vlastního vektoru zmíněné v Perronově–Frobeniově větě, druhé pak z toho, že absolutní hodnoty všech ostatních vlastních čísel musí být ostře menší než jedna. Lineární rovnice a procesy Markovovy řetězce Sledovanost televizí Vysílají jisté dvě televizní stanice. Z veřejného výzkumu vyplynulo, že po jednom roce přejde 1/6 diváků první stanice ke druhé stanici, 1/5 diváků druhé stanice přejde k první stanici. Popište časový vývoj počtu diváků sledujících dané stanice jako Markovův proces. Maticí Markovova procesu je zjevně T = 5 6 1 5 1 6 4 5 . Matice má dominantní vlastní hodnotu 1, příslušný vlastní vektor je (6 5 , 1). Protože je vlastní hodnota dominantní, tak se poměr diváků se ustálí na poměru 6 : 5. Lineární rovnice a procesy Markovovy řetězce Ruleta Hráč rulety má následující strategii: přišel hrát se 100 Kč. Vždy všechno, co aktuálně má. Sází vždy na černou (v ruletě je 37 čísel, z toho je 18 černých, 18 červených a nula). Hráč skončí, pokud nic nemá, nebo pokud získá 800 Uvažte tuto úlohu jako Markovův proces a napište jeho matici. Jednotlivé stavy systému jsou dány aktuální hodnotou, kterou hráč má. Jsou to tedy částky 0, 100, 200, 400 a 800 Kč. Sloupce příslušné matice jsou obrazem situace, kdy hráč je s pravděpodobností jedna v odpovídajícím stavu (tj. standardních vektorů báze R5). Lineární rovnice a procesy Markovovy řetězce Výsledná matice je: T =       1 a a a 0 0 0 0 0 0 0 b 0 0 0 0 0 b 0 0 0 0 0 b 1       , kde a = 19 37 a b = 18 37 . Všimněte si podobnosti s Leslieho růstovým modelem.