Finanční Matematika - 10. přednáška Diskrétní Markovovy řetězce
Martin Panák 2. května 2016
□ rS1
připomenutí z minulé hodiny
Má-li vektor (X,0) sdruženou hustotu f(x,6), pak podmíněná pravděpodobnost komponenty 0 za podmínky X = x je dána hustotou
f(x\e)g(e)
g{0\x) =
f(x)
kde f(x) a g{9) jsou marginální hustoty pravděpodobností.
Diskrétní Markovovy řetězce
Matematický model 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 systém ve stavu / s pravděpodobností x; a k přechodu z možného stavu / do stavu j (za časovou jednotku) dojde s pravděpodobností tn.
Diskrétní Markovovy řetězce
Matematický model 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 systém ve stavu / s pravděpodobností x; a k přechodu z možného stavu / do stavu j (za časovou jednotku) dojde s pravděpodobností tjj. Můžeme tedy proces zapsat takto: V čase n je systém popsán pravděpodobnostním vektorem
xn = ..., um(n))T.
To znamená, že všechny 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 bude dáno vynásobením pravděpodobnostní maticí přechodu T = (ŕ//), tj.
xn+i = T • xn.
Studenti na přednášce
Studenty můžeme rozdělit řekněme do tří skupin - na ty, co jsou přítomni na přednášce a vnímají, na ty, co jsou rovněž přítomni, ale nevnímají, a na ty, co sedí místo přednášky v hospodě. Nyní budeme hodinu po hodině sledovat, jak se mění počty studentů v těchto skupinách. Základem je vypozorovat, jaké jsou jednotlivé pravděpodobnosti změn stavu studenta. Dejme tomu, že by to mohlo být následovně:
Studenti na přednášce
Studenty můžeme rozdělit řekněme do tří skupin - na ty, co jsou přítomni na přednášce a vnímají, na ty, co jsou rovněž přítomni, ale nevnímají, a na ty, co sedí místo přednášky v hospodě. Nyní budeme hodinu po hodině sledovat, jak se mění počty studentů v těchto skupinách. Základem je vypozorovat, jaké jsou jednotlivé pravděpodobnosti změn stavu studenta. Dejme tomu, že by to mohlo být následovně:
Student, který vnímá: s pravděpodobností 50% zůstane vnímat, 40% přestane vnímat a 10% odejde do hospody. Student, který je na přednášce a nevnímá: začne vnímat s pravděpodobností 10%, zůstane ve stejném stavu 50%, odejde do hospody 40%. Student, který sedí v hospodě má nulovou pravděpodobnost, že se vrátí na přednášku.
Jak se bude tento model vyvíjet v čase? Jak se situace změní, pokud budeme předpokládat aspoň desetiprocentní pravděpodobnost toho, že se student vrátí z hospody na přednášku (tu ovšem samozřejmě nevnímá)?
Jak se bude tento model vyvíjet v čase? Jak se situace změní, pokud budeme předpokládat aspoň desetiprocentní pravděpodobnost toho, že se student vrátí z hospody na přednášku (tu ovšem samozřejmě nevnímá)? Ze zadání se jedná o Markovův proces s maticí
0,5   0,1 0\ 0,4   0,5   0 1. 0,1   0,4 1/
Jak se bude tento model vyvíjet v čase? Jak se situace změní, pokud budeme předpokládat aspoň desetiprocentní pravděpodobnost toho, že se student vrátí z hospody na přednášku (tu ovšem samozřejmě nevnímá)? Ze zadání se jedná o Markovův proces s maticí
0,5   0,1 0\ 0,4   0,5   0 ] . 0,1   0,4 1/
Její charakteristický polynom je (0,5 — A)2(l — A) — 0,4(1 — A). Evidentně je tedy 1 vlastní číslo této matice (další kořeny jsou pak 0,3 a 0,7). Postupem času se tedy studenti rozdělí do skupin tak, že stav bude popsán příslušným vlastním vektorem. Ten je řešením rovnice
-0,5    0,1    0\ /x\ 0,4    -0,5   0      y   = 0, 0,1     0,4    0/ \zj
což jsou právě násobky vektoru (0,0,1). Jinými slovy, všichni studenti po čase skončí v hospodě.
Tento výsledek je zřejmý i bez počítání - tím, že je nulová pravděpodobnost odchodu studenta do školy, se budou studenti postupně hromadit v hospodě. Přidáním desetiprocentní možnosti odchodu studenta do školy se toto změní. Příslušná matice bude
0,5  0,1    0 \ 0,4  0,5  0,1 . 0,1   0,4 0,9/
Opět platí, že se stav ustálí na vlastním vektoru příslušnému vlastnímu číslu 1. Ten je v tomto případě řešením rovnice
-0,5    0,1      0 \ /x\ 0,4    -0,5    0,1      y   = 0. 0,1     0,4    -0,1/ \z)
Tento výsledek je zřejmý i bez počítání - tím, že je nulová pravděpodobnost odchodu studenta do školy, se budou studenti postupně hromadit v hospodě. Přidáním desetiprocentní možnosti odchodu studenta do školy se toto změní. Příslušná matice bude
0,5  0,1    0 \ 0,4  0,5  0,1 . 0,1   0,4 0,9/
Opět platí, že se stav ustálí na vlastním vektoru příslušnému vlastnímu číslu 1. Ten je v tomto případě řešením rovnice
-0,5    0,1      0 \ /x\ 0,4    -0,5    0,1      y   = 0. 0,1     0,4    -0,1/ \z)
Řešením je například vektor (1,5,21). Poměrné rozložení studentů v jednotlivých skupinách pak dá násobek tohoto vektoru, který má součet složek roven 1, tj. vektor       ^, |y). Opět tedy většina studentů skončí v hospodě, někteří ale ve škol^ buc^pp.^ 1, < 1 ( t
Roztržitý profesor
Uvažujme následující situaci: Roztržitý profesor s sebou nosí deštník, ale s pravděpodobností 1/2 jej zapomene tam, odkud odchází. Ráno odchází do práce. V práci chodí na oběd do restaurace a zpět. Po skončení práce odchází domů. Uvažujme pro jednoduchost, že nikam jinam po dostatečně dlouhou dobu profesor nechodí a že v restauraci zůstává deštník na profesorově oblíbeném místě, odkud si ho může následující den vzít (pokud nezapomene). Uvažte tuto situaci jako Markovův proces a napište jeho matici. Jaká je pravděpodobnost, že se po mnoha dnech po ránu deštník bude nalézat v restauraci? (Je vhodné za časovou jednotku vzít jeden den - od rána do rána.)
Platí
11/16 3/8 A= I 3/16 3/8 1/8 1/4
Platí
3/8
A = ( 3/16 3/8
1/4
Spočítejme třeba prvek a\, tedy pravděpodobnost, že deštník začne den doma a skončí doma (bude tam i druhý den ráno): deštník může putovat třemi disjunktními cestami:
D Profesor ho hned ráno zapomene doma: pi = |.
DPD Profesor si ho vezme do práce, pak ho zapomene vzít na oběd a poté ho večer odnese domů: p2 = \ • \ • \ — |.
DPRPD Profesor bere deštník všude a nikde ho nezapomene:
n     —   I       I       I       I   — i P3   —   2   '   2   '   2   '   2   — 16"
Celkem aj = pi + p2 + P3 = jg.
Platí
/11/16 3/8 l/4\
A =    3/16 3/8 1/4 .
\ 1/8 1/4 1/2/
Spočítejme třeba prvek a\, tedy pravděpodobnost, že deštník začne den doma a skončí doma (bude tam i druhý den ráno): deštník může putovat třemi disjunktními cestami:
D Profesor ho hned ráno zapomene doma: pi = |.
DPD Profesor si ho vezme do práce, pak ho zapomene vzít na oběd a poté ho večer odnese domů: p2 = \ • \ • \ — |.
DPRPD Profesor bere deštník všude a nikde ho nezapomene:
n     —   I       I       I       I   — i P3   —   2   '   2   '   2   '   2   — 16"
Celkem aJ=pi+p2 + P3 = -jg. Vlastní vektor této matice příslušný dominantní vlastní hodnotě 1 je (2,1,1), je tedy hledaná pravděpodobnost 1/(2 + 1 + 1) = 1/4.
Důležitost webových stránek
Internetové vyhledávače umí na internetu vyhledat (skoro) všechny stránky obsahující dané slovo či frázi. Jak ale setřídit vyhledané stránky tak, aby uživatel dostal pokud možno seznam seřazený podle relevance daných stránek? Jednou z možností je následující algoritmus: soubor všech nalezených stránek považujme za systém a každou z nalezených stránek za jeden z jeho možných stavů. Popíšeme náhodné procházení těchto stránek jako Markovův proces. Pravděpodobnosti přechodu mezi jednotlivými stránkami jsou dány odkazy: každý odkaz, řekněme ze stránky A na stránku B určuje pravděpodobnost (l/(celkový počet odkazů ze stránky A)), se kterou se dostaneme ze stránky A na stránku B. Pokud z některé stránky nevedou žádné odkazy, tak ji uvažujeme jako stránku, ze které vedou odkazy na všechny ostatní. Tímto dostaneme pravděpodobnostní matici M (prvek m;j odpovídá pravděpodobnosti, se kterou se dostaneme z i-té stránky na j-tou).
Důležitost webových stránek
Internetové vyhledávače umí na internetu vyhledat (skoro) všechny stránky obsahující dané slovo či frázi. Jak ale setřídit vyhledané stránky tak, aby uživatel dostal pokud možno seznam seřazený podle relevance daných stránek? Jednou z možností je následující algoritmus: soubor všech nalezených stránek považujme za systém a každou z nalezených stránek za jeden z jeho možných stavů. Popíšeme náhodné procházení těchto stránek jako Markovův proces. Pravděpodobnosti přechodu mezi jednotlivými stránkami jsou dány odkazy: každý odkaz, řekněme ze stránky A na stránku B určuje pravděpodobnost (l/(celkový počet odkazů ze stránky A)), se kterou se dostaneme ze stránky A na stránku B. Pokud z některé stránky nevedou žádné odkazy, tak ji uvažujeme jako stránku, ze které vedou odkazy na všechny ostatní. Tímto dostaneme pravděpodobnostní matici M (prvek m;j odpovídá pravděpodobnosti, se kterou se dostaneme z i-té stránky na j-tou). Bude-li tedy člověk náhodně klikat na odkazy v nalezených stránkách íookud se dostane na stránku, ze které nevede odkaz.
Tento algoritmus lze modifikovat tím, že budeme předpokládat, že uživatel po nějaké době přestane klikat z odkazu na odkaz a opět začne náhodně na nějaké nové stránce. Řekněme, že s pravděpodobností d vybere náhodně novou stránku a s pravděpodobností (1 — d) klikne na nějaký odkaz na ní. V takovéto situaci je nyní pravděpodobnost přechodu mezi libovolnými dvěma stránkami S; a Sj nenulová, je to totiž d/n + (1 — c/)/(celkový počet odkazů ze stránky S/), pokud ze stránky S; vede odkaz na Sj, pokud ne, tak je tato pravděpodobnost d/n (1/r?, pokud z S; nevedou žádné odkazy). Podle Frobeniovy-Perronovy věty je vlastní hodnota 1 jednonásobná a dominantní, takže jí odpovídající vlastní vektor je jediný (pokud bychom volili pravděpodobnosti přechodu pouze způsobem z předchozího odstavce, tak by tomu tak nemuselo být).
Pro názornost uvažme stránky A, B, C a D. Odkazy vedou z A na B a na C, z 6 na C a z C na A, z D pak nikam. Uvažujme, že pravděpodobnost toho, že uživatel náhodně zvolí novou stránku je 1/5. Potom by matice M vypadala následovně:
/1/20	1/20	17/20	l/4\
9/20	1/20	1/20	1/4
9/20	17/20	1/20	1/4
\l/20	1/20	1/20	l/V
Pro názornost uvažme stránky A, B, C a D. Odkazy vedou z A na B a na C, z 6 na C a z C na A, z D pak nikam. Uvažujme, že pravděpodobnost toho, že uživatel náhodně zvolí novou stránku je 1/5. Potom by matice M vypadala následovně:
/1/20 1/20 17/20 l/4\
9/20 1/20 1/20 1/4
9/20 17/20 1/20 1/4 '
\l/20 1/20 1/20 1/4/
Vlastní vektor příslušný vlastní hodnotě 1 je
(305/53,175/53,315/53,1), důležitost stránek tedy bude stanovena v pořadí podle velikosti jeho odpovídajících složek, tedy C > A > B > D.
Jestliže je A primitivní matice se spektrálním poloměrem A G IR, pak je A jednoduchým kořenem charakteristického polynomu matice A, který je ostře větší než absolutní hodnota kteréhokoliv jiného vlastního čísla matice A. K vlastnímu číslu A navíc existuje vlastní vektor x s výhradně kladnými prvky x,-.