4Interesting problems
IA Probability
4.1 Branching processes
Branching processes are used to model population growth by reproduction. At
the beginning, there is only one individual. At each iteration, the individual
produces a random number of offsprings. In the next iteration, each offspring
will individually independently reproduce randomly according to the same
distribution. We will ask questions such as the expected number of individuals
in a particular generation and the probability of going extinct.
Consider
X
0
, X
1
, ···
, where
X
n
is the number of individuals in the
n
th
generation. We assume the following:
(i) X
0
= 1
(ii)
Each individual lives for unit time and produces
k
offspring with probability
p
k
.
(iii) Suppose all offspring behave independently. Then
X
n+1
= Y
n
1
+ Y
n
2
+ ···+ Y
n
X
n
,
where
Y
n
i
are iid random variables, which is the same as
X
1
(the superscript
denotes the generation).
It is useful to consider the pgf of a branching process. Let
F
(
z
) be the pgf of
Y
n
i
. Then
F (z) = E[z
Y
n
i
] = E[z
X
1
] =
∞
X
k=0
p
k
z
k
.
Define
F
n
(z) = E[z
X
n
].
The main theorem of branching processes here is
Theorem.
F
n+1
(z) = F
n
(F (z)) = F (F (F (···F (z) ···)))) = F (F
n
(z)).
Proof.
F
n+1
(z) = E[z
X
n+1
]
= E[E[z
X
n+1
| X
n
]]
=
∞
X
k=0
P(X
n
= k)E[z
X
n+1
| X
n
= k]
=
∞
X
k=0
P(X
n
= k)E[z
Y
n
1
+···+Y
n
k
| X
n
= k]
=
∞
X
k=0
P(X
n
= k)E[z
Y
1
]E[z
Y
2
] ···E[z
Y
n
]
=
∞
X
k=0
P(X
n
= k)(E[z
X
1
])
k
=
X
k=0
P(X
n
= k)F (z)
k
= F
n
(F (z))
Theorem. Suppose
E[X
1
] =
X
kp
k
= µ
and
var(X
1
) = E[(X − µ)
2
] =
X
(k − µ)
2
p
k
< ∞.
Then
E[X
n
] = µ
n
, var X
n
= σ
2
µ
n−1
(1 + µ + µ
2
+ ··· + µ
n−1
).
Proof.
E[X
n
] = E[E[X
n
| X
n−1
]]
= E[µX
n−1
]
= µE[X
n−1
]
Then by induction, E[X
n
] = µ
n
(since X
0
= 1).
To calculate the variance, note that
var(X
n
) = E[X
2
n
] − (E[X
n
])
2
and hence
E[X
2
n
] = var(X
n
) + (E[X])
2
We then calculate
E[X
2
n
] = E[E[X
2
n
| X
n−1
]]
= E[var(X
n
) + (E[X
n
])
2
| X
n−1
]
= E[X
n−1
var(X
1
) + (µX
n−1
)
2
]
= E[X
n−1
σ
2
+ (µX
n−1
)
2
]
= σ
2
µ
n−1
+ µ
2
E[X
2
n−1
].
So
var X
n
= E[X
2
n
] − (E[X
n
])
2
= µ
2
E[X
2
n−1
] + σ
2
µ
n−1
− µ
2
(E[X
n−1
])
2
= µ
2
(E[X
2
n−1
] − E[X
n−1
]
2
) + σ
2
µ
n−1
= µ
2
var(X
n−1
) + σ
2
µ
n−1
= µ
4
var(X
n−2
) + σ
2
(µ
n−1
+ µ
n
)
= ···
= µ
2(n−1)
var(X
1
) + σ
2
(µ
n−1
+ µ
n
+ ··· + µ
2n−3
)
= σ
2
µ
n−1
(1 + µ + ··· + µ
n−1
).
Of course, we can also obtain this using the probability generating function as
well.
Extinction probability
Let
A
n
be the event
X
n
= 0, ie extinction has occurred by the
n
th generation.
Let q be the probability that extinction eventually occurs. Let
A =
∞
[
n=1
A
n
= [extinction eventually occurs].
Since A
1
⊆ A
2
⊆ A
3
⊆ ···, we know that
q = P(A) = lim
n→∞
P(A
n
) = lim
n→∞
P(X
n
= 0).
But
P(X
n
= 0) = F
n
(0),
since F
n
(0) =
P
P(X
n
= k)z
k
. So
F (q) = F
lim
n→∞
F
n
(0)
= lim
n→∞
F (F
n
(0)) = lim
n→∞
F
n+1
(0) = q.
So
F (q) = q.
Alternatively, using the law of total probability
q =
X
k
P(X
1
= k)P(extinction | X
1
= k) =
X
k
p
k
q
k
= F (q),
where the second equality comes from the fact that for the whole population to
go extinct, each individual population must go extinct.
This means that to find the probability of extinction, we need to find a fixed
point of F . However, if there are many fixed points, which should we pick?
Theorem. The probability of extinction q is the smallest root to the equation
q = F (q). Write µ = E[X
1
]. Then if µ ≤ 1, then q = 1; if µ > 1, then q < 1.
Proof.
To show that it is the smallest root, let
α
be the smallest root. Then note
that 0
≤ α ⇒ F
(0)
≤ F
(
α
) =
α
since
F
is increasing (proof: write the function
out!). Hence F (F (0)) ≤ α. Continuing inductively, F
n
(0) ≤ α for all n. So
q = lim
n→∞
F
n
(0) ≤ α.
So q = α.
To show that
q
= 1 when
µ ≤
1, we show that
q
= 1 is the only root. We
know that
F
′
(
z
)
, F
′′
(
z
)
≥
0 for
z ∈
(0
,
1) (proof: write it out again!). So
F
is
increasing and convex. Since
F
′
(1) =
µ ≤
1, it must approach (1
,
1) from above
the F = z line. So it must look like this:
z
F (z)
So z = 1 is the only root.