11. Galtonův – Watsonův proces větvení
11.1. Definice: Nechť jedinec tvořící nultou generaci může dát vznik 0, 1, 2, ... jedincům
(potomkům) první generace. Analogicky každý jedinec z první generace může dát vznik 0, 1, 2,
... jedincům druhé generace atd. Přitom předpokládáme, že
a) počet potomků X náhodně zvoleného jedince má pravděpodobnostní funkci
( )


 =
==
jinak0
0,1,2,...kprop
kXP k
, která nezávisí na zvoleném jedinci ani na generaci, do níž
přísluší;
b) jedinci z dané generace dávají vzniknout svým potomkům vzájemně nezávisle.
Označme Xn počet jedinců n-té generace (speciálně je X0 = 1). Za uvedených předpokladů
posloupnost náhodných veličin { }0n Nn;X ∈ tvoří homogenní markovský řetězec s množinou
stavů J = {0, 1, 2, ...}. Tento řetězec se nazývá Galtonův – Watsonův proces větvení.
11.2. Označení: Zavedeme náhodné veličiny Unk, k = 1, 2, ... které mají stejné rozložení jako
náhodná veličina X1 a jsou stochasticky nezávislé jak mezi sebou, tak na veličinách X0, X1, ...
Veličina Unk udává počet potomků k-tého jedince v n-té generaci. Je zřejmé, že
Xn+1 = Un1 + Un2 + ... + UnXn.
Ilustrace:
………………………………………………
11.3. Věta: Pravděpodobnosti přechodu pij = P(Xn = j / Xn-1 = i) splňují vztah: { }*i
jij pp:Jj,i =∈∀
s počáteční podmínkou


 =
=
jinak0
0proj1
p j0 , tedy matice přechodu má tvar














+
=
KKKK
K
K
K
20
2
110
2
0
210
pp2ppp2p
ppp
001
P
.
Důkaz: ( ) { }*i
j
i
1k
k,1n1n
X
1k
k,1n1nnij pjUPiX/jUPiX/jXPp
1n
=





==





====== ∑∑ =
−−
=
−−
−
podle věty 10.10.
11.4. Příklad: Nechť { }0n Nn;X ∈ je Galtonův – Watsonův proces větvení s množinou stavů
J = {0, 1, 2, ...} a vektorem počátečních pravděpodobností p(0) = (¼, ¼ , ½ , 0, ...). Najděte
matici přechodu P.
Řešení:














=














+
=
KKKK
K
K
K
KKKK
K
K
K
16/516/216/1
2/14/14/1
001
ppp2pp2p
ppp
001
P 2
12010
2
0
210
11.5. Věta: Pro pravděpodobnostní vytvořující funkci náhodné veličiny Xn+1 platí:



=
=
=+
0pron0
,2,1pron))z(g(g
)z(g
XX
X
n
1n
K
, kde gX(z) je pravděpodobnostní vytvořující funkce
náhodné veličiny X1.
Důkaz: Protože ∑=
+ =
nX
1k
nk1n UX je součet náhodného počtu náhodných veličin, tvrzení plyne
z věty 10.15.
11.6. Příklad: Nechť { }0n Nn;X ∈ je Galtonův – Watsonův proces větvení, přičemž
pravděpodobnostní vytvořující funkce náhodné veličiny X1 má tvar ( )β
−α−= z11)z(gX , kde
0 < α, β < 1 jsou konstanty. Najděte pravděpodobnostní vytvořující funkci náhodné veličiny Xn.
Řešení: ( )[ ]{ } ( )[ ] ( )
2
2
z11z11z1111))z(g(g)z(g 1
XXX
β+ββββ
−α−=−αα−=−α−−α−==
( )[ ]{ } ( )[ ] ( )
3232
2
23
z11z11z1111))z(g(g)z(g 111
XXX
ββ+β+ββ+βββ+β
−α−=−αα−=−α−−α−==
Obecně: ( )
nn2
n
z11)z(g 1
X
ββ++β+β+
−α−= K
pro n = 1, 2, ...
11.7. Věta: Nechť µ je střední hodnota a σ2
je rozptyl náhodné veličiny X1. Pak pro střední
hodnotu a rozptyl náhodné veličiny Xn platí:
,)X(E n
n µ=
( )





=µσ
≠µ
−µ
−µµσ
=
−
1pron
1pro
1
1
)X(D
2
n1n2
n
.
Důkaz: Provedeme matematickou indukcí. Z věty 10.15. plyne:
1nn
nX,1n1,1n1n )X(E)UU(E)X(E n
+
+++ µ=µµ=µ=++= K .
Nechť µ ≠ 1. Pak
( )
( )
1
1
1
1
1
)X(E)X(D)UU(D)X(D
1nn2n21n21n21n22
2n2
n1n2
2
n
2
nX,1n1,1n1n n
−µ
−µµσ
=
−µ
µσ−µσ+µσ−µσ
=
=σµ+µ
−µ
−µµσ
=σ+µ=++=
++++
−
+++ K
Nechť µ = 1.
Pak D(Xn+1) = D(Xn) + σ2
= n σ2
+ σ2
= (n + 1) σ2
.
11.8. Příklad: Pro zadání příkladu 11.4. vypočtěte střední hodnotu a rozptyl počtu potomků v nté
generaci.
(Připomeňme, že vektor počátečních pravděpodobností p(0) = (¼, ¼ , ½ , 0, ...).)
Řešení:
( )
4
5
2
1
2
4
1
1
4
1
0XE 1 =⋅+⋅+⋅=µ= ,
( ) ( ) ( )[ ]
16
11
4
5
2
1
2
4
1
1
4
1
0XEXEXD
2
2222
1
2
1
2
1 =





−⋅+⋅+⋅=−=σ=
( )
n
n
4
5
XE 





=
( ) ( )








−





⋅





⋅





⋅=
−µ
−µµσ
=
−−
1
4
5
4
5
16
11
4
1
1
XD
n1n2n1n2
n
11.9. Věta: Označme qn = P(Xn = 0) pravděpodobnost vyhynutí v n-té generaci. Pak platí:
)0(gq nXn = .
Důkaz: ( ) ( ) nnX
0k
k
nX q0XP)0(gzkXP)z(g nn
===⇒== ∑
∞
=
.
11.10. Věta: Nechť 0 < p0 < 1. (Krajní případy p0 = 0 a p0 = 1 vylučujeme, protože pro p0 = 0 je
qn = 0 pro všechna n = 1, 2, ... a pro p0 = 1 je qn = 1 pro všechna n = 1, 2, ...)
a) Je-li µ ≤ 1, pak 1qlim n
n
=
∞→
.
b) Je-li µ > 1, pak ξ=
∞→
n
n
qlim , kde ( )1,0∈ξ je nejmenší kladný kořen rovnice z = gX(z).
Interpretace: Je-li µ ≤ 1, pak s pravděpodobností 1 proces dosáhne jen konečně mnoha generací.
Je-li µ > 1, pak s pravděpodobností ξ proces dosáhne konečně mnoha generací a
s pravděpodobností 1 – ξ dosáhne nekonečně mnoha generací.
Důkaz: nebudeme provádět.
11.11. Příklad: Pro Galtonův – Watsonův proces z příkladu 11.4. najděte limitní hodnotu
pravděpodobnosti vyhynutí.
Řešení:
V příkladu 11.8. bylo vypočteno, že ( )
4
5
XE 1 = . Protože 1
4
5
> , podle tvrzení b) věty 11.10.
ξ=
∞→
n
n
qlim , kde ( )1,0∈ξ je nejmenší kladný kořen rovnice z = gX(z) = =∑=
2
0k
k
k zp
2
1
1
4
893
z01z3z2,z2z1z4z
2
1
z
4
1
4
1
12
222
=
−±
=⇒=+−++=⇒++= . Podmínku splňuje kořen ½,
tedy limitní hodnota pravděpodobnost i vyhynutí je 0,5.
11.12. Poznámka: Předchozí výsledky lze snadno zobecnit na případ, kdy nultá generace je
tvořena k0 ≥ 1 jedinci. Pak pro n = 1, 2, ... platí.
a) ( ) n
0n kXE µ=
b)
( )





=µσ
≠µ
−µ
−µµσ
=
−
1pronk
1pro
1
1
k
)X(D
2
0
n1n2
0
n
c)



>µξ
≤µ
=
∞→ 1pro
1pro1
qlim
0kn
n
Lze si totiž představit, že vedle sebe se navzájem nezávisle větví k0 populací, z nichž každá
vznikla z právě jednoho jedince.