Generující funkce a náhodná procházka
Uvažujme opět náhodnou procházku
Sn =
n
i=1
Xi ,
kde P(Xi = 1) = p a P(Xi = −1) = q = 1 − p. Přitom Xi jsou
nezávislé a S0 = 0.
Problém rekurence:
– Jak často se náhodná procházka vrací do počátku?
– Jaké je pravděpodobnostní rozdělení prvního návratu do počátku?
K zodpovězení těchto otázek využijeme generující funkce.
Označme
p0(n) = P(Sn = 0)
pravděpodobnost, že náhodná procházka je v 0 v čase n, a
f0(n) = P(S1 = 0, S2 = 0, ..., Sn−1 = 0, Sn = 0)
pravděpodobnost, že první návrat do počátku nastal v čase n.
Uvažujme generující funkce těchto dvou posloupností,
P0(s) =
∞
n=0
p0(n)sn
a
F0(s) =
∞
n=0
f0(n)sn
.
Máme p0(0) = 1 (neboť S0 = 0) a f0(0) = 0.
Lemma 4.1. Platí
P0(s) = 1 − 4pqs2 −1
2
.
Důkaz: Víme, že Sn = 0 ⇔ počet kroků doprava = počet kroků
doleva, tedy r = n
2 = l. Počet takových cest je n
n
2
pro n sudé a 0
pro n liché. Označme k = n
2 , tj. n = 2k. Máme
p0(2k) =
2k
k
pk
qk
a
P0(s) =
∞
k=0
2k
k
(pqs2
)k
. (1)
Tvrdíme, že P0(s) = 1√
1−4pqs2
.
Využijeme obecného binomického rozvoje
(1 + x)a
=
∞
n=0
a
n
xn
,
kde
a
n
=
a (a − 1) ... (a − n + 1)
n!
.
Pro a ∈ N je rozvoj konečný, pro a ∈ R ∧ a /∈ N je rozvoj
nekonečný. Dosazením a = −1
2 a x = −4pqs2 dostaneme
1 − 4pqs2 −1
2
=
∞
k=0
−1
2
k
−4pqs2 k
= (2)
∞
k=0
−1
2
k
(−4)k
pqs2 k
.
Porovnáním 1 a 2 tedy stačí dokázat, že
−1
2
k
(−4)k
=
2k
k
.
Pro levou stranu dostaneme
−1
2 −3
2 −5
2 ... −2k−1
2
k!
(−1)k
22k
=
2k
(−1)2k 1 · 3 · 5 · ...(2k − 1)
k!
= 2k 1 · 3 · 5 · ... · (2k − 1)
k!
.
Pro pravou stranu
2k
k
=
2k (2k − 1) (2k − 2) ...1
k!k!
= 2k
k!
(2k − 1) (2k − 3) ...3 · 1
k!k!
=
2k (2k − 1) (2k − 3) ...3 · 1
k!
.
Tedy obě strany se rovnají. Tím je lemma dokázáno.
Věta 4.2. Platí
1) P0(s) = 1 + P0(s)F0(s)
a
2) F0(s) = 1 − 1 − 4pqs2
1
2
.
Důkaz: Označme A jev, že Sn = 0 a nechť Bk jsou jevy “první
návrat do počátku nastal v k-tém kroku” (k = 1, 2, ..., n).
1) Bk jsou disjunktní a dávají rozklad, tedy
P(A) =
n
k=1
P(A | Bk)P(Bk).
Máme P(Bk) = f0(k) a P(A | Bk) = p0(n − k), z časové
homogenity. Tedy
p0(n) =
n
k=1
p0(n − k)f0(k).
Vynásobíme sn a sečteme,
∞
n=1
p0(n)sn
=
∞
n=1
n
k=1
p0(n − k)f0(k)sn
=
∞
k=1
f0(k)sk
∞
n=k
p0(n − k)sn−k
= P0(s)F0(s).
Protože
∞
n=1
p0(n)sn
= P0 − 1,
dostáváme P0 − 1 = P0F0, tedy P0 = 1 + P0F0.
Pro důkaz 2) dostáváme z 1)
F0 =
P0 − 1
P0
= 1 −
1
P0
= 1 − 1 − 4pqs2.
Důsledek 4.3. Pravděpodobnost toho, že se částice někdy vrátí
do počátku, je rovna
∞
n=1
f0(n) = F0(1) = 1− | p − q | .
Speciálně, pro symetrickou náhodnou procházku (p = q) je návrat
jistý.
Důsledek 4.4. (Pólyova věta v dimenzi 1) Symetrická náhodná
procházka se s pravděpodobností 1 vrátí do počátku.
Důsledek 4.5. Je-li p = q = 1
2 , tedy návrat je jistý, pak očekávání
času T0 prvního návratu do počátku je
E(T0) =
∞
n=1
nf0(n) = F0(1) = ∞.
Důkaz: Máme
F0(1) = 1− 1 − 4pq = 1− 1 − 4p(1 − p) = 1− 1 − 4p + 4p2 =
= 1− (1 − 2p)2 = 1− | 1−2p |= 1− | 1−p −p |= 1− | q −p | .
Pro q = p = 1
2 je F0(1) = 1 − 0 = 1.
Je-li návrat jistý, tedy p = 1
2, pak P(T0 = ∞) = 0, a tedy
E(T0) = F0(1), kde F0 = 1 − 1 − 4pqs2. Máme
F0 = −
1
2
1
1 − 4pqs2
(−4pq2s) =
4pqs
1 − 4pqs2
,
tedy lim
s→1−
F0(s) = +∞.
Časy navštívení bodu r
Označme
fr (n) = P(S1 = r, S2 = r, ..., Sn−1 = r, Sn = r)
pravděpodobnost, že se náhodná procházka dostane poprvé do
bodu r v čase n, s generující funkcí
Fr (s) =
∞
n=0
fr (n)sn
.
Věta 4.6. Platí
Fr (s) = [F1(s)]r
pro r ≥ 1,
F1(s) =
1 − 1 − 4pqs2
1
2
2qs
Důkaz: Označme Tr = min {n; Sn = r} počet kroků potřebných k
dosažení hodnoty r poprvé. Nechť r > 0. Abychom dosáhli r,
musíme se dostat nejdříve do bodu 1, a potom z bodu 1 do bodu r.
To je z prostorové homogenity totéž jako dostat se z 0 do r − 1.
Odtud plyne Tr = T1 + Tr−1. Z nezávislosti tedy dostaneme
Fr = F1Fr−1.
Máme pro n > 1
f1(n) = P(S1 = 1, S2 = 1, ..., Sn−1 = 1, Sn = 1) =: P(A) =
= P(A | S1 = 1)P(S1 = 1) + P(A | S1 = −1)P(S1 = −1) =
= P(A | S1 = 1)p + P(A | S1 = −1)q = 0p + f2(n − 1)q.
Odtud
f1(n) = f2(n − 1)q.
Vynásobíme sn
f1(n)sn
= qf2(n − 1)sn
a sečteme přes n > 1.
Tedy
n=2
f1(n)sn
=
n=2
qf2(n − 1)sn
=
n=2
sqf2(n − 1)sn−1
= sq
n=1
f2(n)sn
.
Odtud dostáváme
F1 − ps = F2qs.
Víme, že F2 = F2
1 , tedy
F1 − ps = F2
1 qs,
což vede ke kvadratické rovnici
qsF2
1 − F1 + ps = 0.
Řešením dostaneme dva kořeny
F1 =



1−
√
1−4qps2
2qs
1+
√
1−4qps2
2qs
.
Kořen
1+
√
1−4qps2
2qs ale nevyhovuje zadání, protože má v bodě 0
limitu ∞. Tím je tvrzení dokázáno.
Důsledek 4.7. Pravděpodobnost, že náhodná procházka někdy
navštíví kladnou část reálné osy, je rovna min 1, p
q .
Důkaz: Hledaná pravděpodobnost je rovna pravděpodobnosti, že
náhodná procházka navštíví bod 1. Ta je rovna
∞
n=1
f1(n),
součtu pravděpodobností, že se dostaneme do bodu 1 v nějakém
čase n. Víme, že
F1(s) =
∞
n=0
f1(n)sn
.
Dosazením s = 1 dostaneme
∞
n=1
f1(n) = F1(1) =
1 − (1 − 4pq)
1
2
2q
=
1 − 1 − 4p(1 − p)
2(1 − p)
=
1 − (1 − 2p)2
2(1 − p)
=
1− | 1 − 2p |
2(1 − p)
=
1− | q − p |
2q
=
=
1−(−(q−p))
2q = 1−p+q
2q = 2q
2q = 1 pro q < p
1−q+p
2q = 2p
2q = p
q pro q > p
.
Příklad 4.8. Ruleta má 37 čísel (včetně 0). Budeme sázet stále na
lichá čísla, tedy p = 18
37 a q = 19
37. Pravděpodobnost, že budeme
někdy vyhrávat je p
q = 18
19 .