2. technika – počítání trajektorií
Uvažujme náhodnou procházku vycházející z bodu a. Máme tedy
S0 = a, P(Xi = 1) = p, P(Xi = −1) = q,
a
Sn = a +
n
i=1
Xi .
Zvolme pevně danou cestu.
Pravděpodobnost, že prvních n kroků bude sledovat právě tuto
cestu, je rovna
pr
ql
,
kde r je počet kroků doprava a l je počet kroků doleva.
Tedy
r =| {i : Si+1 − Si = 1, i ≤ n − 1} |,
kde | . | značí velikost množiny.
Každý jev můžeme vyjádřit pomocí vhodné množiny trajektorií
(které jsou s ním v souladu).
Jeho pravděpodobnost je součet pravděpodobností těchto
trajektorií.
Máme
P(Sn = b) =
r
Mr
n(a, b)pr
qn−r
,
kde Mr
n(a, b) je počet cest (S0, S1, ..., Sn) takových, že S0 = a,
Sn = b, a majících přesně r kroků doprava.
Víme ale, že r + l = n a r − l = b − a.
Odtud 2r = n + b − a, tedy
r =
n + b − a
2
a
l =
n − b + a
2
.
r je tedy určeno hodnotami a, b, n a v označení je nadbytečné
Tedy
P(Sn = b) =
n
r
p
n+b−a
2 q
n−b+a
2 =
n
1
2 (n + b − a)
p
n+b−a
2 q
n−b+a
2 ,
pokud 1
2 (n + b − a) ∈ N (jinak je pravděpodobnost rovna 0).
Princip reflexe
Označme Nn(a, b) počet všech cest z bodu (0, a) do bodu (n, b).
Víme, že
Nn(a, b) = Mr
n(a, b) =
n
1
2 (n + b − a)
.
Nechť N0
n (a, b) je počet všech cest z bodu (0, a) do bodu (n, b),
které obsahují nějaký bod (k, 0) na ose x, tedy navštíví bod 0.
Věta 3.1. (princip reflexe): Je-li a, b > 0, pak platí
N0
n (a, b) = Nn(−a, b).
Důkaz: Každá cesta z bodu (0, −a) do (n, b) protne osu x poprvé
v nějakém bodě (k, 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)
– cestami (0, a) do (n, b), které navštíví osu x.
Tedy N0
n (a, b) = Nn(−a, b).
Věta 3.2. (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
b
n
Nn (0, b) ,
kde Nn (0, b) je počet všech cest z bodu (0, 0) do bodu (n, b).
Důkaz: Pro všechny takové cesty je první krok bod (1, 1) (jinak se
nutně dostaneme do nuly), tedy jejich počet je roven (z časové
homogenity):
Nn−1 (1, b) − N0
n−1 (1, b) = Nn−1 (1, b) − Nn−1 (−1, b)
Dále máme
Nn−1 (1, b) − Nn−1 (−1, b) =
n − 1
1
2(n − 1 + b − 1)
−
n − 1
1
2 (n + b)
=
n − 1
m − 1
−
n − 1
m
=
b
n
n
m
=
b
n
Nn (0, b) ,
kde jsme označili m = 1
2 (n + b).
Využili jsme identitu
n − 1
m − 1
−
n − 1
m
=
b
n
n
m
Její důkaz je za domácí úkol
Příklad 3.3. (Úloha o volbách) Kandidát A má α hlasů; kandidát
B dostal β hlasů, kde α > β, tj. kandidát A zvítězil. Jaká je
pravděpodobnost, že během voleb byl A celou dobu před B?
Označme Xi = 1, je-li i-tý hlas pro A, Xi = −1, je-li i-tý hlas pro
kandidáta B. Je tedy n = α + β. Součet
Sk =
k
i=1
Xi
popisuje, o kolik vede A nad B v čase k (případně prohrává, je-li
Sk < 0).
Podle věty o volbách je trajektorií z bodu (0, 0) do bodu
(α + β, α − β), které se nedostanou do 0, přesně
α − β
α + β
Nα+β (0, α − β) .
Hledaná pravděpodobnost je tedy
α−β
α+β Nα+β (0, α − β)
Nα+β (0, α − β)
=
α − β
α + β
.
Nyní se budeme zajímat o to, jaká je pravděpodobnost, že se
náhodná procházka nevrátí do 0. Máme S0 = 0 a chceme
S1 = 0, ..., Sn = 0, jinak řečeno S1S2...Sn = 0.
Věta 3.4. Je-li S0 = 0, pak pro n ≥ 1 platí
P(S1S2...Sn = 0 | Sn = b) =
| b |
n
P(Sn = b),
tedy
P(S1S2...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.
Generující funkce
Uvažujeme posloupnost reálných čísel
a = {an; n = 0, 1, 2, ..} .
Taková posloupnost obsahuje velké množství informace, kterou
můžeme výhodně “zakódovat” do jediného objektu (funkce).
S ním budeme moci lépe pracovat.
Získáme možnost použít operace (např. derivaci), které pro
posloupnosti nemají smysl.
Generující funkce posloupnosti a je funkce daná součtem mocninné
řady
Ga(s) =
∞
n=0
ansn
pro s ∈ R, pro která řada konverguje.
Posloupnost a dostaneme z generující funkce Ga zpět vztahem
an =
G
(n)
a (0)
n!
,
kde G
(n)
a (0) je n-tá derivace Ga v bodě 0.
Příklad: Nechť a = {0, 1, 0, −1, 0, 1, 0, ...} . Pak
Ga = s − s3
+ s5
− s7
+ ... ,
což je geometrická řada s prvním členem s a s kvocientem
q = −s2. Tedy
Ga(s) =
s
1 + s2
pro | s |< 1 (obor konvergence).
Dále budeme definovat generující funkci diskrétní náhodné veličiny.
Nechť X je diskrétní náhodná veličina, která nabývá hodnoty v
množině {0, 1, 2, ...} , s pravděpodobnostní funkcí
f (i) = P(X = i).
Generující funkce náhodné veličiny X je definovaná jako generující
funkce její pravděpodobnostní funkce, tedy
GX (s) =
∞
i=0
f (i)si
=
∞
i=0
P(X = i)si
.
Platí zřejmě
GX (s) = E(sX
).
Základní vlastnosti generujících funkcí:
– Existuje nezáporné číslo R (poloměr konvergence) takové, že
G(s) konverguje pro | s |< R a diverguje pro | s |> R.
– G(s) můžeme derivovat nebo integrovat člen po členu, libovolně
mnohokrát, pro | s |< R.
–Jednoznačnost: Je-li Ga(s) = Gb(s) pro | s |< R , kde
0 < R ≤ R, pak an = bn pro všechna n.
Příklady generujících funkcí náhodných veličin:
1. Konstantní náhodná veličina. P(N = k) = 1, kde k ∈ N ∪ {0}.
Máme
GN(s) = 1sk
= sk
.
2. Bernoulliho náhodná veličina. P(N = 1) = p a
P(N = 0) = 1 − p. Tedy
GN(s) = ps1
+ (1 − p)s0
= 1 − p + ps.
3. Geometrické rozdělení. P(N = k) = p(1 − p)k pro k ∈ N .
Počet neúspěchů před prvním úspěchem
Dostaneme
GN(s) =
∞
i=0
pN(n)sn
=
∞
n=0
p(1 − p)n
sn
=
∞
n=0
p [(1 − p)s]n
=
=
p
1 − (1 − p)s
=
p
1 − s + sp
.
4. Poissonovo rozdělení s parametrem λ.
P(X = k) =
λk
k!
e−λ
.
Tedy
GX (s) =
∞
i=0
λi
i!
e−λ
si
= e−λ
∞
i=0
(λs)i
i!
= e−λ
eλs
= eλs−λ
= eλ(s−1)
,
s využitím n
xn
n! = ex .
Charakteristiky náhodných veličin a generující funkce
Základní charakteristiky n.v., E(X) a Var(X), lze snadno spočítat
pomocí GX (s).
Věta: Nechť X je náhodná veličina s generující funkcí GX (s). Pak
platí:
E(X) = GX (1).
Obecně,
E(X(X − 1)...(X − k + 1)) = G
(k)
X (1)
(tzv. k-tý faktoriální moment).
Důkaz: První tvrzení je speciální případ druhého. Máme
G
(k)
X (s) =
i
si−k
i(i − 1)...(i − k + 1)pX (i) =
= E(sX−k
X(X − 1)...(X − k + 1)).
Pro s = 1 dostaneme
G
(k)
X (1) = E(X(X − 1)...(X − k + 1)).
Pro rozptyl dostaneme speciálně vztah
Var(X) = E(X2
) − E(X)2
= E(X(X − 1) + X) − E(X)2
=
= E(X(X − 1)) + E(X) − E(X)2
= GX (1) + GX (1) − GX (1)
2
.
Součty náhodných veličin Něchť a = {ai , i ≥ 0} a
b = {bi , i ≥ 0} jsou dvě posloupnosti, pak konvoluce c = a b je
posloupnost definovaná vztahem
cn = a0bn + a1bn−1 + ... + anb0.
Jsou-li Ga, Gb generující funkce posloupností a a b, pak generující
funkce posloupnosti c je
Gc(s) =
∞
n=0
cnsn
=
∞
n=0
n
i=0
ai bn−i sn
=
=
∞
i=0
ai si
∞
n=i
bn−i sn−i
=
∞
i=0
ai si
∞
n=0
bnsn
= Ga(s)Gb(s).
Tím jsme dokázali následující tvrzení.
Věta 3.5. Generující funkce konvoluce dvou posloupností je
součinem generujících funkcí těchto posloupností.
Věta Nechť X a Y jsou nezávislé náhodné veličiny. Pak
GX+Y (s) = GX (s)GY (s).
Důkaz:
E(sX+Y
) = E(sX
sY
) = E(sX
)E(sY
)
první rovnost plyne z vlastností exponenciály, druhá z nezávislosti X
a Y .
– Jiný důkaz dostaneme využitím předchozí věty.
Obecně, pro součet více nezávislých náhodných veličin dostaneme:
Je-li S = X1 + X2 + ... + Xn, kde Xi jsou nezávislé, pak z předchozí
věty plyne
GS = GX1 GX2 ...GXn .
Definice 3.6. Sdružená pravděpodobnostní generující funkce
náhodných veličin, nabývajících hodnot v N ∪ {0}, je definovaná
jako
GX1,X2 (s1, s2) = P (X1 = i ∧ X2 = j) si
1sj
2 = E(sX1
1 sX2
2 )
Analogicky je možné definovat sdruženou pravděpodobnostní
generující funkci pro více náhodných veličin.