11 13 Branching processes in discrete time Flashcards
look at notes
notes done?
Branching processes in discrete time:Introduction
assumptions
Assume each individual of a population lives a fixed time (one generation) and produces at the end of its life a #offspring that is a RV with
some probability pₖ
#offspring for each is i.i.d
thus defines a branching process in discrete time.
All Markov processes are memoryless
Branching processes in discrete time: offspring distribution
{pₖ}ₖ₌₀ ∞
collection of all pₖ
P {X = k} ≡ Probability{X = k} = pk, k = 0, 1, 2, . . .
where p_k = P {X = k}
All Markov processes are memoryless
the number of individuals in generation n + 1, called
Zₙ₊₁, depend on Zₙ (number of individuals in generation n), but not on the past history of
the process Z0,Z1, · · · ,Zₙ₋₁(number of individuals in each generation 0 to n − 1).
Branching processes in discrete time:
Zₙ - #individuals in the nth generation
The #individuals in the (n+1)th generation?
The #individuals in the (n+1)th generation written as the sum of Zₙ independent RVs:
Zₙ₊₁ = X₁+X₂+X₃+..+X_{Zₙ}
{Zₙ independent Rvs in this sum}
X_i are iid
X_i represent #offspring of the ith member of the nth generation, independent realisations
(Markov property is satisfied- this is also a RV)
Branching processes in discrete time: Extinction of the population when?
if Z_n = 0 ⇒
Z_m = 0 for all m > n
if p₀≠ 0: one individual can have no offspring
extinction happens if all individuals in one gen have no offspring
Branching processes in discrete time: The mean
assume Z_0 given
Z₀=1 define the mean number of offspring of one individual i of the population in a given generation as µ
µ ≡ E(Xᵢ) = E(X)
= Σ{ₖ₌₀,..∞} kpₖ = p₁ + 2p₂ + 3p₃ + · · ·
idd for every individual i of every generation n, thus
E(Xᵢ) = E(X) and
the mean number of offspring of one individual is µ
Branching processes in discrete time: The mean number of individuals in generation n+1
E(Zₙ₊₁)
= E(ΣXᵢ) (for i=1,…,Zₙ)
= E(X₁) +…+E(X_{Zₙ})
= µ +…µ = µ E[Zₙ]
(Zₙ terms)
Zₙ is RV taking values k=0,1,….,E(Zₙ₊₁) also infinite sum of terms kµ with weights p(Zₙ=k) probability of k individuals in gen n having on average µ offspring:
E(Zₙ₊₁) = Σ{ₖ₌₀,..∞} kµP{Zₙ=k}
= µ E(Zₙ)
iterating:
E(Zₙ) = µE(Zₙ₋₁) = µµE(Zₙ₋₂)=…
=µⁿ⁻¹ µE(Z₀) = Z₀µⁿ = Z₀ exp(n lnu)
Branching processes in discrete time: The mean number of individuals in generation n+1 used to show exponential function:
iterating
E(Zₙ) = µE(Zₙ₋₁) = µµE(Zₙ₋₂)=…
=µⁿ⁻¹ µE(Z₀) = Z₀µⁿ = Z₀ exp(n lnu)
Thus: mean number of individuals increases exponentially as a function
of n if µ > 1, and decreases exponentially with n if µ < 1
Branching processes in discrete time: Extinction of the population looking into this
probability that the population is not extinct by generation n is
If Zₙ individuals in gen n then the probability that the pop goes extinct in gen n+1 is p₀^{Zₙ}
(Zₙ is an RV so hard to find)
However, if Zₙ=0 for some n then Zₘ=0 for all m>n
Thus the probability that the population goes extinct by generation n (i.e. at, or before, generation n) is
0 ≤ P { population is extinct by n} = P {Zn = 0}.
probability that the population is not extinct by generation n is
0 ≤ P { population is not extinct by n} =
P {Zₙ ≥ 1}
= P {Zₙ = 1}+P {Zₙ = 2}+P {Zₙ = 3}+· · · .
Branching processes in discrete time: Comparing probabilities of extinction to E(Zₙ)
E(Zₙ)
= P{Zₙ=1}+2P{Zₙ=2}+3P{Zₙ=3}+…
Thus
probability that the population is not extinct by generation n is
0 ≤ P { population is not extinct by n } ≤ E(Zₙ).
We know that E(Zₙ) = Z₀µⁿ
Branching processes in discrete time:Conditions
0 ≤ P { population is not extinct by n } ≤ E(Zₙ) = Z₀µⁿ
If µ < 1 POPULATION EXTINCT sooner or later/guaranteed
P {Zₙ ≥ 1} ≤ µⁿ
P { population not extinct } → 0 as n → ∞
If µ > 1 then extinction is not guaranteed, but is still possible
This means that in this case, the population can go extinct or keep growing with a certain probability. Some realisations of the population obeying the rules of the branching process go extinct, but some never do and keep growing.
Branching processes in discrete time: notation the probability uₙ that the population consisting initially of a single individual Z₀ = 1 is extinct by generation n
uₙ ≡ P {Zₙ= 0|Z₀ = 1}.
Branching processes in discrete time: finding the probability uₙ that the population consisting initially of a single individual Z₀ = 1 is extinct by generation n
uₙ ≡ P {Zₙ= 0|Z₀ = 1}.
u₀=0
u₁ =p₀
(if p₀=0 no pop extinction ever, so for this analisis assume 0<p₀<1)
uₙ prob of extinction by time for gen n and is an increasing function of n as it includes the possible extinction events at 1,2,..,n
Branching processes in discrete time:
uₙ ≡ P {Zₙ= 0|Z₀ = 1}.
uₙ = φ(uₙ₋₁ ), with u₀ = 0,
how we found
k individuals when n = 0: probability that whole pop dies out before the nth gen is the prob that, independently k sub-families starting with one individual die out
P {Zₙ = 0|Z₀ = k} = uₙᵏ
if k individuals when n=1 we have
P {Zₙ = 0|Z₀ = k} =P {Zₙ₋₁ = 0|Z₀ = k} = uₙ₋₁ᵏ
If Z₀ =1
P {Z₁ = k|Z₀ = 1} = P {X = k} = pₖ
can then write expression of u_n in terms of u_{n-1} summing over all poss values of k which links to pgf of X
Branching processes in discrete time: Example
Suppose that p0 = 0.2, p1 = 0.4 and p2 = 0.4.
Then φ(z) =
.
φ(z) = 0.2 + 0.4z + 0.4z^2
,
u1 = 0.2,
u2 = φ(u1) = φ(0.2) = 0.2 + 0.4 × 0.2 +0.4 × 0.2^2
for increasing n: 0,1,2,3,4,5
un
u0=0
u1= φ(u0)=0.296
u2=0.353…
Branching processes in discrete time:
Is extinction the ultimate fate of the population?
*uₙ is an increasing function of n when p_0 > 0
*As n → ∞, uₙ approaches a limit u (with 0 ≤ u ≤ 1) which is the probability that extinction ever occurs,
and satisfies
u = φ(u)
the probability u that the pop extinction ever occurs is a fixed point! solutions s.t 0 ≤ u ≤ 1.
from pgf properties φ(1) = 1 is always a solution
u=1 always a fixed point
Branching processes in discrete time:
Is extinction the ultimate fate of the population?
show u=1 is a unique fixed point
extinction certain
u = 1 is the unique fixed point of φ when φ’(1) ≤ 1
and it corresponds to population extinction with probability Hence,
population extinction is certain when φ’(1) ≤ 1.
diagram: φ(u) against u increases and meets line y=u
population extinction possible but not certain
when φ’(1) > 1 , there is another solution u∞= φ(u∞)
giving a fixed point
0 < u∞ < 1 (stable as |φ’(u∞)|<1) and u=1 unstable as because |φ’(1)| > 1)
diagram: φ(u) against u increases and meets line y=u twice, once at u∞ then at 1
Extinction summary:
*The mean number of offspring from one individual is µ = φ’(1).
- If µ ≤ 1 then extinction is guaranteed: u_n → 1 as n → ∞.
The entire population goes extinct, sooner or later.
*If µ > 1 then extinction is not guaranteed (but still possible):
un → u∞ as n → ∞,
where 0 < u∞ < 1 and satisfies u∞ = φ(u∞).
*In a fraction u∞ of all realisations of the branching process, the population goes extinct, and in the other realisations (a fraction 1 − u∞ of them) there is no extinction and the population grows unbounded
Example. Suppose that p0 = 0.2, p1 = 0.4 and p2 = 0.4. Then, φ(z) =
extinction?
φ(z) = 0.2 + 0.4z +0.4z²
φ’(z) = 0.4 + 0.8z, and the solution to is
u = 0.2 + 0.4u + 0.4u²
0 = 0.2 − 0.6u + 0.4u²
⇒ two fixed points: u = 0.5, u = 1.
Here, µ = φ’(1) = 0.4 + 0.8 = 1.2 > 1, and hence u = 0.5 is stable and gives the extinction probability ⇒ probability that the population ever goes extinct is u∞ = 0.5
Interested in more general branching processes in discrete time: what do we need for a complete understanding of a discrete-time branching process describing the number of individuals in a population?
pdf of each of the RVs Z_n
giving the number of individuals in the nth generation of the
population. These can be obtained from the probability generating functions for Zn,
pgf for discrete time branching processes: Deriving the pgf for the #individuals Zₙ in each generation n
Z_0
Z_1
we use initial condition Z₀=1 assuming single individual in the population and assume each individual in all generations leave behind X offspring with pgf of X φ(z)
- If Z₀=1 : Z₁ has the same probability distribution as X pgf φ(z)
- pgf for each Zₙ:
gₙ(z) = ΣP(Z ₙ=k)zᵏ = E(Z^{Zₙ})
(k=0,…,∞)
*Z₀=1
g₀(z)=z or δₖ,₁zᵏ
where δₖ,₁ kronecker delta function
g₁(z) = φ(z) as same probabilities Z₁=k as X=k as its the initial individual
δₖ,₁ kronecker delta function
δₖ,ₘ = 1 if k=m
=0 if k/= m
pgf for discrete time branching processes: Deriving the pgf for the #individuals Zₙ in each generation n
Zₙ₊₁
related to Zₙ?
Zₙ₊₁ = Σ Xᵢ from i=1 to Z ₙ £
each parent i contributing to pop in Zₙ₊₁
RV sum of RVs
so pgf:
gₙ₊₁ (z) = E(z^{Zₙ₊₁})
= E(z^(£))
= Σ_{k=0,∞} P(Zₙ=k)E(z^{Σ {i=1,k}Xᵢ})
= Σ{k=0,∞} P(Zₙ=k)E(z^X₁)….E(z^Xₖ)
=Σ_{k=0,∞} P(Zₙ=k) (φ(z)ᵏ) = gₙ(φ(z))
** thus we have the recurrence relation**
gₙ₊₁(z)=gₙ(φ(z)) for n ≥ 0, with g₀(z) = z
pgf for discrete time branching processes: Deriving the pgf for the #individuals Zₙ in each generation summary pgf for Z_n
g₁(z)=φ(z)
g₂(z)= g₁(φ(z)) = φ(φ(z))
….
gₙ(z)= φ(….φ(φ(z)…) (n-1 compositions)
= φ(gₙ₋₁)
gₙ₊₁(z)=φ(gₙ(z))
meaning we also have
gₙ₊₁(z) = φ(gₙ(z)) for n ≥ 0, with g₀(z) = z,
pgf for discrete time branching processes: Deriving the pgf for the #individuals Zₙ in each generation WHEN Z_0=k>1
Each individual of the initial gen produces an independent family
Z_n in generation n is a sum of k identically distributed RVs
E(z^{Z_n} | Z₀=k)
=(E(z^{Zₙ}| Z₀=1))ᵏ
= (gₙ(z))ᵏ
(gₙ(z) is pgf of Zₙ when Z₀=1
This means that it
suffices to focus on the case with Z₀ = 1 to obtain gₙ(z) and then simply
use above to find the probability generating function of Zₙ if initially Z₀ = k>1
Example. If the probabilities of having no children, one child and two children are
respectively p0, p1 and p2, then how many grandchildren can you have and with what
probability?
Let X be #children and let Z₂ be #grandchildren
g₂(z) be the pgf of Z₂.
assume p₀+ p1 + p₂ = 1,
with pₙ = 0 for n /∈ {0, 1, 2}.
pgf of X :** φ(z) = p₀ + p₁z + p₂z²**
pgf of Z₂:
g₂(z) = φ(φ(z))
= p₀ + p₁φ(z) + p₂φ(z)²
= p₀ + p₁(p₀ + p₁z + p₂z²)+ p₂(p₀ + p₁z + p₂z²)
=p₀ + p₀p₁ + p₀²p₂ + (p₁² + 2p₂p₀p₁)z²+ (2p₂²p₁)z³
+(p₂³)z⁴
defn of g₂(z) ≡
sum_k [ P {Z₂ = k} zᵏ
P {Z₂ = 0} = P { zero grandchildren } = p₀ + p₀p₁ + p₀²p₂
P {Z₂ = 1} =P{1 grandchild} = p₁² + 2p₂p₀p₁
P {Z₂ = 2} = P {2 grandchildren } = p₁p₂ + pp₁² + 2p₂²p₀
P{Z₂=3} =P{3 grandchildren } = 2p₂²p₁
P {Z₂ = 4} = P{ 4 grandchildren } = p₂³
{z }
pgf for discrete time branching processes: summary part 2
We have obtained two equivalent forms for the recurrence relation giving the pgf of Zₙ₊₁, with
g₀(z) = z (Z₀ = 1):
gₙ₊₁(z) = gₙ(φ(z)) and gₙ₊₁(z) = φ(gₙ(z)).
It is also instructive to look at the second version:
gₙ₊₁(z) ≡ E(z^{Zₙ₊₁} ) = p₀ + p₁ E(z^{Zₙ₊₁}|Z₁ = 1) + p₂E(z^{Zₙ₊₁} |Z₁ = 2) + · · ·
= p₀ + p₁ E(z^{Zₙ}|Z₀ = 1) + p₂E(z^{Zₙ}|Z₀ = 2) + · · ·
= p₀ + p₁ gₙ(z) + p₂gₙ²(z) + · · ·
=Σₖ pₖgₙᵏ(z) ≡ φ(gₙ(z)).
