NÁHODNÁ PROCHÁZKA POLYOVA VĚTA ZÁKONY ARCSINU Jana Faltýnková Obsah Náhodná procházka - úvod 3 Vlastnosti náhodné procházky 5 Techniky počítání s náhodnou procházkou 6 Polyova věta 15 Zákony arcsinu 19 Zdroje 22 Náhodná procházka - úvod • Jednoduchá náhodná procházka - základ diskrétních modelu pro pohyb cen aktiv, „diskrétní verze" Brownova pohybu • Stochastický proces, který můžeme popsat pomocí následující hry: - Házíme mincí - padne-li hlava, získáme 1 Kč, padne-li orel, prohrajeme 1 Kč - na začátku máme sumu £0 - v čase n pak máme sumus Sn = -So + Ya=i ^í> kde Xi je výsledek z—té hry - Xi - náh. veličiny s pravděpodobnostní funkcí: P(X, = 1) = p a P(X, = -1) = 1 - p = q (analogie Bernoulliho náhodné veličiny) • takto popsaný stochastický proces {Sn}™=1 nazýváme jednoduchá náhodná procházka • pokud p = 2 = Q, mluvíme o symetrické jednoduché náhodné procházce • Jiná interpretace náhodné procházky: náhodný pohyb částice po přímce (v každém časovém okamžiku t = 0,1,2,.. .se částice posune o 1 doprava (s pravděpodobností p) nebo o 1 doleva (s pravděpodobností q) • Grafické znázornění náhodné procházky: Body o souřadnicích (n, spojíme úsečkami —>■ lomená čára - trajektorie náhodné procházky Náhodná procházka - vlastnosti • Prostorová homogenita P(Sn = j\S0 = a) = P(Sn = j + b\S0 = a + b • Časová homogenita P{$>n = j\$>0 = a) = P{£>n+m = J | *$m = a • Markovova vlastnost („náhodná procházka nemá pa meť", „minulost ovlivňuje budoucnost jen skrze součas nost") Základní techniky počítání s náhodnou procházkou • Podmínění 1. krokem • Počítání trajektorií • Generující funkce - u diskrétních náhodných veličin, které nabývají hodnot na množině 0,1,2,..., s pravděpodobnostní funkcí f (i) = P(X = i) - Generující funkce: oo oo i=0 i=0 - (Pozn.: Generujícím funkcím je věnována samostatná státnicová otázka) Technika podmínění 1. krokem • Příklad: Házíme férovou mincí (p = \). Pokud padne hlava, získáme 1 Kč, pokud orel, prohrajeme 1 Kč. Na počátku máme sumu S0 = k a chceme si koupit auto, které stojí N Kč. Budeme tedy hrát tak dlouho, dokud nezískáme Sn = N nebo dokud nebudeme „zruinováni", tedy Sn = 0. Jaká je pravděpodobnost, že budeme zruinováni? • Řešení: - Označme: A ... hráč nakonec zbankrotuje H ... první hod padne hlava O . .. první hod padne orel - Věta o úplné pravděpodobnosti: P (A) = P(H)P(A\H) + P(0)P(A\O) Technika podmínění 1. krokem • Řešení - pokračování: - Dále označme: Pk(A) ... pravděpodobnost bankrotu při počáteční sumě k - pak Pk(A) = P(H)Pk(A\H) + P(0)Pk(A\O) - Pk(A\H) nám udává pravděpodobnost, že po prvním hodu budeme mít sumu k + 1 - v důsledku nezávislosti Xi hra začíná znovu (ale s počáteční sumou k + 1) - bude tedy platit Pk(A\H) = Pk+1(Ä) a analogicky Pk(A\0) = Pk-M) - Dále označme: Pk(A) = pk Technika podmínění 1. krokem • Řešení - pokračování: - Pak můžeme psát: 1 1 Pk = 2^+1 + 2Pk~l 1 1 - -pk) = - (pk - pk_x) - přírůstky jsou konstantní —>■ můžeme je označit jako pk+1 -pk = b, tedy pk = b-k + pd - okrajové podmínky: Po = 1 (okamžitý bankrot) = 0 (okamžitá koupě auta) - pak tedy l + Ar-6 = 0apfe = l- -| Technika počítání trajektorií • Uvažujeme náhodnou procházku vycházející z bodu a, což můžeme zapsat jako -S0 = a, P(XZ = l)=p, P(XZ = -l) = q - tedy Sn = a + Ya=i xí • Chceme-li vypočítat pravděpodobnost, že náhodná procházka bude sledovat námi předem zvolenou trajektorii, bude dána vztahem pr • q1, kde r je počet kroků doprava a / počet kroků doleva • Nyní ale chceme vypočítat pravděpodobnost, že za n kroků budeme v bodě b, začínáme-li v bodě a • musíme tedy uvážit všechny možné trajektorie, které splňují tuto podmínku - tyto trajektorie však budou mít společnou jednu podmínku - znalostí počátečního a koncového bodu je jednoznačně dán počet kroků r, které musíme udělat doprava a tedy i počet kroků /, které musíme udělat doleva Technika počítání trajektorií • Musí totiž platit: n = r + / b — a = r — l • Odtud dopočítáme _ n+b-a 2 7 _ n—b+a 1 — 2 • počet všech cest bude dán jako kombinace r prvků z celkového počtu n prvků (vybíráme r kroků doprava z n možných kroků, přičemž nezáleží na pořadí) • konkrétně tedy počet všech cest splňujících naše podmínky je Technika počítání trajektorií • hledanou pravděpodobnost pak vypočítáme jako Nn{a, b) = P(Sn = b) = n n+b—a n+b—a n—b+a P • tento vztah ovšem platí pouze pro případ, že ra+2~a G N - v opačném případě totiž žádná taková cesta neexistuje a pravděpodobnost je pak rovna 0 • dále se budeme zabývat tím, kolik cest AT°(a, b) z bodu a do bodu b navštíví někdy osu x • k tomu využijeme tzv princip reflexe (budeme uvažovat případ a, b > 0) Technika počítání trajektorií • Princip reflexe: Každá cesta z bodu (0, —a) do (n, b) protne osu x poprvé v nějakém bodě (/c, 0) . Reflexí této cesty okolo osy x dostaneme cestu z bodu (0, a) do (n, b), která navštíví osu x. Tato operace dává vzájemně jednoznačnou korespondenci mezi cestami z (0, —a) do (n, b) a cestami (0, a) do (n, b), které navštíví osu £ • Bude tedy platit vztah iV>, b) = Nn(-a, b) Technika počítání trajektorií • Věta o volbách: Je-li b > 0, pak počet cest z bodu (0, 0) do bodu (n, b), které se nevrátí do bodu 0 je • Myšlenka důkazu: Nechceme-li se vrátit do 0 a jeli b > 0, musí náš první krok vést do bodu (1,1). Poté už můžeme využít princip reflexe (odečteme ty trajektorie, které se vrátí do nuly). Tedy Vhodnou úpravou pak získáme požadovaný vztah. • aplikací věty můžeme vypočítat pravděpodobnost, že při volbách mezi kandidátem A a B vedl neustále kandidát A, pokud víme, že A získal a hlasů a B /3 hlasů, kde a > (3 —>■ z této aplikace plyne název n Nn_Al,b)-K-Áhb) věty Polyova věta • Definice: Mějme posloupnost náhodných vektorů Xi, X2,..., Xn,..., kde Y - ( Y^ Y^ yN\ je m-rozměrný vektor. Nechť platí p(^ = i) = l,p(^ = -i) = | pro všechna i GNa pro všechna j G {1,2,..., m} a všechna X-^ jsou navzájem nezávislé náhodné veličiny, m-rozměrná náhodná procházka je definována vztahem n n SiP = + Xt] rektorově Sn = S0 + £ Xk Polyova věta • Polyova věta: Pravděpodobnost, ze se náhodná procházka vrátí nekonečněkrát zpět do počátku je rovna 1 pro m = 1 a m = 2 a je rovna 0 pro m > 2. I Úvodní strana Titulní strana Obsah _ Sřrana 76 z 22 Zpěř ■ Full Screen Zavřít Konec Polyova věta • Myšlenka důkazu: - Označme: p0{n) = P(Sn = 0) /o(n) = P(Sn = 0 A SVS2... ± 0) a k nim příslušné generující funkce Po a Fq 1 - Platí vztah: F0 = 1 - — -M) - Pravděpodobnost, že se částice někdy vrátí do počátku můžeme vyjádřit jako OO -i E /»(«) = ^(i) =1" Polyova věta • Myšlenka důkazu - pokračování: - Dále využijeme Stirlingovu formuli: n r-— —v 27m n ni - Pomocí Stirlingovy formule P(S2k = 0 T 1 vyjádříme p0 (n) ~ ^J—- - Dále díky nezávislosti a na základě konvergence, resp. divergence Pq(1) = Yl™=iPo(n) dokážeme větu Zákony arcsinu • Věta: (1. zákon arcsinu pro poslední návštěvu počátku) Uvažujme symetrickou náhodnou procházku, t.j. p = \ a nechť S0 = 0. Pravděpodobnost, že poslední návštěva počátku do času 2n nastane v čase 2k, je rovna P(S2k = 0)P(S2n_2k = 0) • Myšlenka důkazu: - Pravděpodobnost, že poslední návštěva počátku do času 2n nastane v čase 2k: - z časové homogenity plyne: P(S2k = 0)P(SlS2 ■ ■ ■ S2n_2k ^0\S0 = 0) - Předpokládejme tedy že So = 0 Zákony arcsinu • Myšlenka důkazu - pokračování: - stačí dokázat, že platí: P(SiS2 ' ' ' S2n-2k 7^ 0) = P{S2n-2k = 0) - Využijeme vztahu: 1 P(S1S2 - - - S2n-2k 0) = —E(\Sn\) n - Úpravami tohoto výrazu získáme požadovanou rovnost —>■ dokážeme tak 1. zákon arcsinu • Věta: (2. zákon arcsinu) Nechť p = \ a S0 = 0. Pravděpodobnost, že náhodná procházka stráví přesně 2k časových intervalů napravo od počátku je (opět) rovna P(S2k = 0)P(S2n_2k = 0) Zákony arcsinu • Proč se těmto zákonům říká zákony arcsinu? - Ze Stirlingovy formule plyne, že P(S2k = 0)P(S. >2n-2k = 0 1 7T^/k(n — k - Označme T2n čas posledního navštívení bodu 0 do času 2n (1. zákon), resp. čas strávený napravo od počátku (2. zákon), pak pro a; G (0,1 P(T2n < 2xn E k