Maxima
Jakou největší hodnotu nabývá náhodná procházka do času n?
Rozdělení maximálních hodnot je důležité např. pro oceňování
zpětných (lookback) opcí.
Připomeňme si důsledek Věty o volbách.
Věta 5.1. Nechť S0 = 0. Pro n ≥ 1 platí
P(Sn = b & S1 · S2 · · · Sn = 0) =
|b|
n
· P(Sn = b)
a tedy
P(S1 · S2 · · · Sn = 0) =
1
n
· E(|Sn|).
Důkaz: Nechť Sn = b > 0. Podle věty o volbách je počet cest z
bodu (0, 0) do bodu (n, b), které nenavštíví počátek celkem
b
n
· Nn(0, b).
Tedy
P(Sn = b & S1·S2 · · · Sn = 0) =
b
n
·Nn(0, b)·p
n+b
2 ·q
n−b
2 =
b
n
· P(Sn = b).
Podobně pro b < 0.
Jakou maximální hodnotu nabývá N. P. do času n?
Označme
Mn = max{Si ; 0 ≤ i ≤ n}
a opět S0 = 0, tedy Mn ≥ 0.
Věta 5.2. Nechť S0 = 0. Pak pro n ≥ 1 platí
P(Mn ≥ r & Sn = b) =
P(Sn = b) pro b ≥ r
(q
p )r−b · P(Sn = 2r − b) pro b < r
Důkaz: Zřejmě Mn ≥ Sn, tedy 1. část je jasná.
Dále máme pro b < r:
Nechť Nr
n(0, b) je počet cest z (0, 0) do (n, b), které obsahují
nějaký bod s hodnotou r, t.j. (i, r) pro 0 < i < n.
Nechť pro takovou cestu c je (ic, r) první takový bod.
Uvažujme reflexi takové cesty pro ic ≤ k ≤ n okolo přímky y = r.
Tak dostaneme cestu c z (0, 0) do (n, 2r − b).
Každá taková cesta c vznikne z jednoznačně určené cesty c.
Tedy
Nr
n(0, b) = Nn(0, 2r − b)
.
Tedy
(Mn ≥ r & Sn = b) = Nr
n(0, b) · p
n+b
2 · q
n−b
2 =
=
q
p
r−b
· Nn(0, 2r − b) · p
n+2r−b
2 · q
n−2r+b
2 =
=
q
p
r−b
· P(Sn = 2r − b)
Pravděpodobnost P(Mn ≥ r) dostaneme sečtením přes všechny
hodnoty b. Speciálně, pro p = q = 1
2 dostaneme
P(Mn ≥ r) = P(Sn = r) + 2P(Sn > r). (1)
Pravděpodobnosti hodnot Sn umíme explicitně vypočítat.
Pro pst. funkci maxima platí
P(Mn = r) = P(Sn = r) + P(Sn = r + 1). (2)
Jaká je pravděpodobnost, že N.P. dosáhne nového maxima v
daném čase?
Věta 5.3. Pravděpodobnost fb(n), že N.P. se poprvé dostane do
bodu b v čase n je
fb(n) =
|b|
n
· P(Sn = b).
Důkaz: Plyne z předminulé věty a principu reverze (obrácení).
Nechť pro původní trajektorii náhodné procházky je
(0, S1, . . . , Sn) = (0, X1, X1 + X2, . . . ,
n
i=1
Xi ).
Uvažujme obrácenou trajektorii
(0, T1, . . . , Tn),
kde
(0, T1, . . . , Tn) = (0, Xn, Xn + Xn−1, . . . ,
n
i=1
Xi ).
Xi jsou IID, tedy obě mají stejné rozložení (pro libovolné p).
Původní náhodná procházka splňuje
Sn = b > 0 & S1, . . . , Sn = 0
(podmínky předminulé věty 5.1) ⇐⇒ obrácenná náhodná
procházka (která je ve tvrzení věty označená jako Sn) splňuje
Tn = b a
Tn−Tn−i = (Xn+· · ·+X1)−(Xn+· · ·+Xi+1) = X1+· · ·+Xi > 0 pro ∀i,
tedy b se nabývá poprvé v čase n, jako nové maximum (“rekord”).
Tedy
fb(n) = P(Sn = b & S1 = b, S2 = b · · · Sn−1 = b) =
b
n
· P(Sn = b).
Analogicky pro b < 0.
Pólyova věta v Rn
Definice 5.4. Mějme posloupnost náhodných vektorů
X1, X2, ..., Xn, ..., kde
Xi = X
(1)
i , X
(2)
i , ..., X
(m)
i
je m-rozměrný vektor. Nechť platí
P X
(j)
i = 1 =
1
2
a
P X
(j)
i = −1 =
1
2
pro všechna i ∈ N a pro všechna j ∈ {1, 2, ..., m}, a všechna X
(j)
i
jsou navzájem nezávislé náhodné veličiny.
m-rozměrná náhodná procházka je definována vztahem
S
(j)
n = S
(j)
0 +
n
k=1
X
(j)
k ,
tedy vektorově
Sn = S0 +
n
k=1
Xk.
Pro m = 2 uvažujme množinu mřížových bodů
Z2
= {(i, j) | i, j ∈ Z} = Z ⊕ Z.
Nechť S0 = (0, 0), pak
P [S1 = [1, 1]] = P [S1 = [−1, −1]] =
= P [S1 = [−1, 1]] = P [S1 = [1, −1]] =
1
4
Stirlingova formule
Chceme porovnat hodnotu n! (která se v různých formách
vyskytuje v kombinačních číslech pro počty trajektorií) s
mocninnými funkcemi.
Víme, že nn n (n − 1) ...21 2n, tedy nn n! 2n.
Jak rychle jde ale posloupnost an = n!
nn k nule?
Lze ji srovnat s geometrickou posloupností?
Pro n → ∞ dostaneme
an+1
an
=
(n+1)!
(n+1)n+1
n!
nn
=
n!
(n+1)n
n!
nn
=
n
n + 1
n
=
1
e
.
Tedy (zatím jen hodně přibližně) můžeme psát
n!
nn
∼
1
en
,
neboli n! ∼ nn
en .
Stirlingova formule dává přesnější odhad.
Platí
n! ≈
nn
en
√
2πn
v tom smyslu, že
limn→∞
n!
nn
en
√
2πn
= 1.
Ze Stirlingovy formule dostaneme odhad na hodnotu
u2k = P (S2k = 0) .
Lemma 5.5. Platí u2k
≈ 1√
πk
pro k → ∞, tedy
lim
k→∞
u2k
1√
πk
= 1.
Důkaz: Máme
u2k = P (S2k = 0) =
2k
k
1
2
2k
=
(2k)!
k! (2k − k)!
1
2
2k
=
(2k)!
(k!)2
1
2
2k
≈
(2k)2k
e2k
√
2π2k
kk
ek
√
2πk
2
1
2
2k
=
22kk2k
√
2π2k
kk
√
2πk
2
1
22k
=
√
2
√
2πk
=
1
√
πk
.
Tím je lemma dokázáno.
Věta 5.6. (Pólyova věta): Pravděpodobnost, že 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.
Poznamenejme, že pro m = 3 je pravděpodobnost alespoň jednoho
návratu do počátku
.
= 0, 35.
Důkaz: Jako u jednorozměrné procházky označme
p0 (n) = P (Sn = 0)
pravděpodobnost návratu v čase n, a
f0 (n) = P (Sn = 0 ∧ S1 = 0, . . . , Sn−1 = 0)
pravděpodobnost prvního návratu v čase n. Nechť P0 a F0 jsou
generující funkce těchto posloupností. Víme, že platí
F0 = 1 −
1
P0
.
Máme
P (částice se někdy vrátí do 0) =
∞
n=1
f0 (n) = F0 (1) = 1 −
1
P0 (1)
,
kde ale
P0 (1) =
∞
n=0
p0 (n) .
Odtud dostáváme, že
P (částice se vrátí do počátku) =



1 pokud
∞
n=1
p0 (n) diverguje
< 1 pokud
∞
n=1
p0 (n) konverguje
Podle Stirlingovy formule víme, že u2k ≈ 1√
πk
. Pro m = 1 je
p0 (n) = P (Sn = 0) ≈
1
πn
2
=
2
π
1
√
n
.
Víme, že
∞
n=1
1
√
n
diverguje, protože
∞
n=1
1
ns
konverguje pro s > 1 (z integrálního kriteria).
Pro m > 1 je z nezávislosti komponent
P (Sn = 0) = P S
(1)
n = S
(2)
n = ... = S
(m)
n = 0 = P S
(1)
n = 0
m
,
tedy
p0 (n) = P (Sn = 0) ≈
2
π
1
√
n
m
=
2
π
m
2 1
n
m
2
.
Dále
∞
n=1
p0 (n) ≈
∞
n=1
1
n
m
2
konverguje pro m
2 > 1, tj. m > 2.
Tedy pro m > 2 je hledaná pravděpodobnost alespoň jednoho
návratu do počátku menší než 1.
Pro m = 1 a m = 2 je tato pravděpodobnost 1.
Pravděpodobnost nekonečně monoha návratů je tedy rovna 0 pro
m > 2 a rovna 1 pro m ≤ 2.