P1- Základní pojmy z oblasti Markovových řetězců 1.1 Základní pojmy – matice pravděpodobností přechodu Markovovy řetězce jsou nejjednodušším typem procesů Markovova typu; předpokládá se u nich diskrétnost času i stavů. Uplatňují se při popisu systémů, které se mohou nacházet v jednom z konečného, popřípadě v jednom z nekonečného, ale spočetného[1] počtu stavů. Předpokládáme, že máme celkem M stavů (počet může být konečný nebo spočetný) a že diskrétní čas uvažujeme od okamžiku „0“. Chování takového systému (v nějakém časovém okamžiku ) je určeno 1. vektorem absolutních tj. nepodmíněných pravděpodobností v určitém okamžiku pro 2. maticí pravděpodobností přechodu (z jednoho stavu do jiného, popř. pravděpodobnosti setrvání v témže stavu) pro , Poznámka 1 Vzhledem k tomu, že se jedná o pravděpodobnosti, musí splňovat podmínky , což znamená, že matice pravděpodobností přechodu má nezáporné prvky a jedničkové řádkové součty[2]. Přechod systému ve dvou po sobě následujících okamžicích lze popsat tímto základním schématem: , resp. mezi dvěma (počátečním a aktuálním) časovými okamžiky: (1.1) , Pro přechod od prvního („0“) ke druhému („1“) časovému okamžiku to znamená vyjádření (1.2) , Pro jednotlivé stavy pro přechod mezi prvními dvěma obdobími zřejmě platí podle (1.2) : [3] , což rozepsáno po jednotlivých stavech dává tuto soustavu vztahů ....................................................................................... Pro přechod od t-tého k t+1-mu časovému okamžiku znamená obdobně vyjádření (1.1) soustavu n vztahů : ....................................................................................... Vhodnou souhrnnou reprezentací všech pravděpodobností přechodu po 1 kroku je maticová forma, při níž matici zapíšeme jako stav 0 1 ....... M (1.3) pro Protože jsou pravděpodobnosti, musí být splněny vlastnosti: (1.4A) pro všechna (1.4B) pro všechna S ohledem na platnost (1.4A), (1.4B), má tedy matice nezáporné prvky, přičemž součty prvků v každém jejím řádku jsou rovny 1.[4] 1.2 Definice Markovova řetězce a souvisejících pojmů Předpoklady týkající se sdruženého rozdělení M-rozměrných náhodných vektorů ...... jsou nutné k tomu, abychom mohli získat užitečné výsledky. Jeden ze základních předpokladů, který umožňuje rozvinout analytické nástroje, je ten, že stochastický proces je markovský, tzn., že má následující klíčovou vlastnost: Definice 1 Stochastický proces se nazývá markovský [Markovian process], jestliže platí tzv. markovská vlastnost (1.3) pro a pro každou posloupnost stavů Markovská vlastnost je charakteristická tím, že podmíněná pravděpodobnost jakékoliv budoucí události za podmínky, že byly dány všechny minulé události a současný stav, je nezávislá na všech těchto minulých událostech a závisí pouze na stavu procesu v současnosti. Definice 2 Podmíněnou pravděpodobnost nazveme pravděpodobností přechodu [transition probability] Definice 3 Jestliže platí pro všechna , pak říkáme, že tyto jednokrokové pravděpodobnosti jsou stacionární [stationary] pro všechna . Takže pokud máme stacionární pravděpodobnosti přechodu, znamená to, že se tyto pravděpodobnosti v průběhu času nemění. Podmíněné pravděpodobnosti sdělující, že „v čase t+n je systém ve stavu j, jestliže byl předtím v čase t ve stavu i“ jsou obvykle značeny [5] a jsou nazývány pravděpodobnosti přechodu po n krocích. Takže je právě podmíněná prst, že náhodná proměnná X, vycházeje ze stavu i, bude po n krocích právě ve stavu j (po n časových jednotkách). Protože jsou podmíněné pravděpodobnosti, musí rovněž splňovat podmínky: (1.4A) pro všechna a pro (1.4B) pro všechna a pro Vhodnou souhrnnou reprezentací všech pravděpodobností přechodu po n krocích je opět maticová forma – matice pravděpodobností přechodu po n krocích stav 0 1 ...... . M (1.5) pro Každý řádek této matice vyjadřuje rozdělení pravděpodobností stavů, kam se dá ze stavu vyjádřeného tímto řádkem po n krocích dostat. Každý sloupec této matice vyjadřuje rozdělení pravděpodobností stavů, odkud se dá do stavu vyjádřeného tímto sloupcem po n krocích dostat. S ohledem na platnost (1.4A), (1.4B), má matice nezáporné prvky, přičemž dále součty prvků v každém jejím řádku jsou rovny 1.[6] Definice 4 Stochastický proces , se nazývá konečný Markovův řetězec (= řetězec s konečným počtem stavů), jestliže má následující vlastnosti: 1. Počet stavů (M) je konečný. 2. Náhodný proces má markovskou vlastnost (1.3) 3. Jsou definovány stacionární pravděpodobnosti ve smyslu definice 3 4. Je dán vektor počátečních pravděpodobností pro všechna . Tvrzení tato definice 4 Markovova řetězce (ne nutně stacionárního) a stav systému v čase 0 (resp. rozdělení pravděpodobnosti v tomto stavu) úplným způsobem popisují trajektorii Markovova procesu: ověření: Označme . K důkazu bude postačující ukázat, jak spočíst pomocí matice a vektoru všechny veličiny (1.6) tzn. ukázat, jak mohou být za předpokladů Definice 4 získány libovolné pravděpodobnosti obsahující posloupnosti stavů , na základě axiomu pro rozklad celkové pravděpodobnosti. Podle definice podmíněné pravděpodobnosti máme pro (1.6) vyjádření (1.7) Nyní podle definice Markovské vlastnosti (1.3) procesu (1.8) Substituujeme-li (1.8) do (1.7), dostaneme Druhý člen pravé strany vyjadřuje pravděpodobnost sdruženého jevu . Postupujeme-li dále indukcí stejně jako pro pravděpodobnost jevu , dostaneme (1.9) . □ . 1.3 Příklady - prostorově homogenní Markovovy řetězce Nechť označuje diskrétní náhodnou veličinu, jejíž možné hodnoty jsou celá nezáporná čísla. Označme , přičemž a . Nechť náhodné vektory reprezentují nezávislá pozorování veličiny . Popíšeme nyní dva různé Markovovy řetězce, které mají souvislost s posloupností veličin . Příklad 1A Uvažujme proces , definovaný jako , s počáteční předepsanou hodnotou . Jeho markovská matice pravděpodobností přechodu po 1 kroku má tvar Každý řádek (které jsou navzájem stejné) zde prostě vyjadřuje skutečnost, že náhodná veličina je nezávislá na náhodná veličině , Příklad 1B Jiná důležitá třída Markovových řetězců pochází z úvah o postupných dílčích součtech sestavených z veličin , neboli o veličinách (1.10) t = 1,2,...., s dodefinováním počátku . Na proces můžeme nahlížet jako na Markovův řetězec. Můžeme snadno spočíst jeho matici pravděpodobností přechodu pro pro , Zde jsme využili předpokládanou nezávislost jednotlivých . Schématicky vyjádřeno pomocí matice pravděpodobností přechodu součtů : Příklad 1C Kdybychom připustili, že hodnoty náhodné proměnné mohou být jak kladná, tak záporná celá čísla, pak možné hodnoty pro každé t budou obsaženy v rámci množiny všech celých čísel. Místo konvenčního očíslování stavů pomocí přirozených čísl, je zde výhodnější ztotožnit stavový prostor s množinou všech celých čísel, protože matice pravděpodobností přechodu se vyjádří v symetričtějším tvaru: ________________________________ [1] Spočetným počtem rozumíme nekonečný počet, jehož velikost (mohutnost) je rovnocenná (ekvivalentní) nekonečnému počtu přirozených čísel. Pozn.: Množina racionálních čísel je rovněž spočetná, množina iracionálních nebo množina reálných čísel jsou „o mnoho větší“, tedy nespočetné. [2] Nepřipouští se tedy neurčitost ve smyslu toho, že by nebylo určeno, kam (resp.s jakou pravděpodobností) se systém může v následujícím časovém okamžiku dostat. [3] Tím je vyčerpávajícím způsobem popsáno, odkud lze v nejširším možném případě (tedy ze všech možných M stavů ) do stavu „j“ přejít. [4] Pro součty po sloupcích to neplatí, protože ne do každého stavu se musíme do 1 kroku dostat. [5] Tyto podmíněné pravděpodobnosti jsou v případě stacionarity procesu shodné s podmíněnými pravděpodobnostmi, že „v čase n je systém ve stavu j, jestliže byl předtím v čase 0 ve stavu i“ [6] Pro součty po sloupcích to neplatí, protože ne do každého stavu se musíme do n krocích dostat – viz dále podrobněji při zavedení klasifikaci stavů.