Lecture 7: Branching processes 1 of 20

Course: M362K Intro to Stochastic Processes

Term: Fall 2014
Instructor: Gordan Zitkovic

Lecture 7
Branching processes

A BIT OF HISTORY

In the mid 19th century several aristocratic families in Victorian Eng-

land realized that their family names could become extinct. Was it just
unfounded paranoia, or did something real prompt them to come to
this conclusion? They decided to ask around, and Sir Francis Galton (a
“polymath, anthropologist, eugenicist, tropical explorer, geographer,
inventor, meteorologist, proto-geneticist, psychometrician and statisti-
cian” and half-cousin of Charles Darwin) posed the following question
(1873, Educational Times):

How many male children (on average) must each generation of a family have in
order for the family name to continue in perpetuity?

An answer came from Reverend Henry William Watson soon after, and
the two wrote a joint paper entitled One the probability of extinction of
Sir Francis Galton
families in 1874. By the end of this lecture, you will be able to give a
precise answer to Galton’s question.

A MATHEMATICAL MODEL

The model proposed by Watson1 was the following: 1

A similar model was proposed and an-
alyzed earlier, in 1845, independently, by
1. A population starts with one individual at time n = 0: Z0 = 1. Irénée-Jules Bienaymé.

2. After one unit of time (at time n = 1) the sole individual produces
Z1 identical clones of itself and dies. Z1 is an N0 -valued random
variable.

3. (a) If Z1 happens to be equal to 0 the population is dead and noth-

ing happens at any future time n ≥ 2.
(b) If Z1 > 0, a unit of time later, each of Z1 individuals gives birth
to a random number of children and dies. The first one has Z1,1
children, the second one Z1,2 children, etc. The last, Z1th one,
gives birth to Z1,Z1 children. We assume that the distribution of Irénée-Jules Bienaymé

Last Updated: March 23, 2016

Lecture 7: Branching processes 2 of 20

the number of children is the same for each individual in every

generation and independent of either the number of individuals
in the generation and of the number of children the others have.
This distribution, shared by all Zn,i and Z1 , is called the offspring
distribution. The total number of individuals in the second gen-
eration is now
Z1
Z2 = ∑ Z1,k .
k =1

(c) The third, fourth, etc. generations are produced in the same way.
If it ever happens that Zn = 0, for some n, then Zm = 0 for all
m ≥ n - the population is extinct. Otherwise,
Zn
Zn+1 = ∑ Zn,k .
k =1

Definition 7.1. A stochastic process with the properties described in

(1), (2) and (3) above is called a (simple) branching process.

The mechanism that produces the next generation from the present
one can differ from application to application. It is the offspring dis-
tribution alone that determines the evolution of a branching process.
With this new formalism, we can pose Galton’s question more pre-
cisely:
Under what conditions on the offspring distribution will the process { Zn }n∈N0
never go extinct, i.e., when does

P[ Zn ≥ 1 for all n ∈ N0 ] = 1 (7.1)

hold?

CONSTRUCTION AND SIMULATION OF

BRANCHING PROCESSES

Before we answer Galton’s question, let us figure out how to simulate

a branching process, for a given offspring distribution { pn }n∈N0 (pk =
P[ Z1 = k ]). The distribution { pn }n∈N0 is N0 -valued - we have learned
how to simulate such distributions in Lecture 3. We can, therefore,
assume that a transformation function F is known, i.e., that the random
variable η = F (γ) is N0 -valued with pmf { pn }n∈N0 , where γ ∼ U [0, 1].
Some time ago we assumed that a probability space with a sequence
{γn }n∈N0 of independent U [0, 1] random variables is given. We think
of {γn }n∈N0 as a sequence of random numbers produced by a com-
puter. Let us first apply the function F to each member of {γn }n∈N0
to obtain an independent sequence {ηn }n∈N0 of N0 -valued random
variables with pmf { pn }n∈N0 . In the case of a simple random walk,

Last Updated: March 23, 2016

Lecture 7: Branching processes 3 of 20

we would be done at this point - an accumulation of the first n ele-

ments of {ηn }n∈N0 would give you the value Xn of the random walk
at time n. Branching processes are a bit more complicated; the incre-
ment Zn+1 − Zn depends on Zn : the more individuals in a generation,
the more offspring they will produce. In other words, we need a black
box with two inputs - “randomness” and Zn - which will produce
Zn+1 . What do we mean by “randomness”? Ideally, we would need
exactly Zn (unused) elements of {ηn }n∈N0 to simulate the number of
children for each of Zn members of generation n. This is exactly how
one would do it in practice: given the size Zn of generation n, one
would draw Zn simulations from the distribution { pn }n∈N0 , and sum
up the results to get Zn+1 . Mathematically, it is easier to be more
wasteful. The sequence {ηn }n∈N0 can be rearranged into a double
sequence2 { Zn,i }n∈N0 ,i∈N . In words, instead of one sequence of inde- 2
Can you find a one-to-one and onto
pendent random variables with pmf { pn }n∈N0 , we have a sequence mapping from N into N × N?

of sequences. Such an abundance allows us to feed the whole “row”

{ Zn,i }i∈N into the black box which produces Zn+1 from Zn . You can
think of Zn,i as the number of children the ith individual in the nth
generation would have had he been born. The black box uses only the
first Zn elements of { Zn,i }i∈N and discards the rest:
Zn
Z0 = 1, Zn+1 = ∑ Zn,i ,
i =1

where all { Zn,i }n∈N0 ,i∈N are independent of each other and have the
same distribution with pmf { pn }n∈N0 . Once we learn a bit more about
the probabilistic structure of { Zn }n∈N0 , we will describe another way
to simulate it.

A GENERATING-FUNCTION APPROACH

Having defined and constructed a branching process with offspring

distribution { Zn }n∈N0 , let us analyze its probabilistic structure. The
first question the needs to be answered is the following: What is the
distribution of Zn , for n ∈ N0 ? It is clear that Zn must be N0 -valued, so
its distribution is completely described by its pmf, which is, in turn,
completely determined by its generating function. While an explicit
expression for the pmf of Zn may not be available, its generating func-
tion can always be computed:

Proposition 7.2. Let { Zn }n∈N0 be a branching process, and let the generat-
ing function of its offspring distribution { pn }n∈N0 be given by P(s). Then
the generating function of Zn is the n-fold composition of P with itself, i.e.,

PZn (s) = P( P(. . . P(s) . . . )), for n ≥ 1.

| {z }
n P’s

Last Updated: March 23, 2016

Lecture 7: Branching processes 4 of 20

Proof. For n = 1, the distribution of Z1 is exactly { pn }n∈N0 , so PZ1 =

P(s). Suppose that the statement of the proposition holds for some
n ∈ N. Then
Zn
Zn+1 = ∑ Zi,n ,
i =1
can be viewed as a random sum of Zn independent random variables
with pmf { pn }n∈N0 , where the number of summands Zn is indepen-
dent of { Zn,i }i∈N . By Proposition 5.16 in the lecture on generating
functions, we have seen that the generating function PZn+1 of Zn+1 is a
composition of the generating function P(s) of each of the summands
and the generating function PZn of the random time Zn . Therefore,

PZn+1 (s) = PZn ( P(s)) = P( P(. . . P( P(s)) . . . ))),

| {z }
n + 1 P’s

and the full statement of the Proposition follows by induction.

Let us use Proposition 7.2 in some simple examples.

Example 7.3. Let { Zn }n∈N0 be a branching process with offspring dis-

tribution { pn }n∈N0 . In the first three examples no randomness occurs
and the population growth can be described exactly. In the other ex-
amples, more interesting things happen.

1. p0 = 1, pn = 0, n ∈ N:
In this case Z0 = 1 and Zn = 0 for all n ∈ N. This infertile popula-
tion dies after the first generation.

2. p0 = 0, p1 = 1, pn = 0, n ≥ 2:
Each individual produces exactly one child before he/she dies. The
population size is always 1: Zn = 1, n ∈ N0 .

3. p0 = 0, p1 = 0, . . . , pk = 1, pn = 0, n ≥ k, for some k ≥ 2:
Here, there are k kids per individual, so the population grows expo-
n
nentially: P(s) = sk , so PZn (s) = ((. . . (sk )k . . . )k )k = sk . Therefore,
Zn = kn , for n ∈ N.

4. p0 = p, p1 = q = 1 − p, pn = 0, n ≥ 2:
Each individual tosses a (a biased) coin and has one child of the
outcome is heads or dies childless if the outcome is tails. The gener-
ating function of the offspring distribution is P(s) = p + qs. There-
fore,
PZn (s) = ( p + q( p + q( p + q(. . . ( p + qs))))) .
| {z }
n pairs of parentheses

The expression above can be simplified considerably. One needs to

realize two things:

Last Updated: March 23, 2016

Lecture 7: Branching processes 5 of 20

(a) After all the products above are expanded, the resulting expres-
sion must be of the form A + Bs, for some A, B. If you inspect
the expression for PZn even more closely, you will see that the
coefficient B next to s is just qn .
(b) PZn is a generating function of a probability distribution, so A +
B = 1.

Therefore,
PZn (s) = (1 − qn ) + qn s.
Of course, the value of Zn will be equal to 1 if and only if all of the
coin-tosses of its ancestors turned out to be heads. The probability
of that event is qn . So we didn’t need Proposition 7.2 after all.
This example can be interpreted alternatively as follows. Each in-
dividual has exactly one child, but its gender is determined at ran-
dom - male with probability q and female with probability p. As-
suming that all females change their last name when they marry,
and assuming that all of them marry, Zn is just the number of indi-
viduals carrying the family name after n generations.

5. p0 = p2 , p1 = 2pq, p2 = q2 , pn = 0, n ≥ 3:
In this case each individual has exactly two children and their gen-
der is female with probability p and male with probability q, inde-
pendently of each other. The generating function P of the offspring
distribution { pn }n∈N is given by P(s) = ( p + qs)2 . Then

PZn = ( p + q( p + q(. . . p + qs)2 . . . )2 )2 .

| {z }
n pairs of parentheses

Unlike the example above, it is not so easy to simplify the above

expression.

Proposition 7.2 can be used to compute the mean and variance of

the population size Zn , for n ∈ N.

Proposition 7.4. Let { pn }n∈N0 be a pmf of the offpsring distribution of a

branching process { Zn }n∈N0 . If { pn }n∈N0 admits an expectation, i.e., if
∞
µ= ∑ kpk < ∞,
k =0

then

E[ Zn ] = µn . (7.2)

If the variance of { pn }n∈N0 is also finite, i.e., if

∞
σ2 = ∑ (k − µ)2 pk < ∞,
k =0

Last Updated: March 23, 2016

Lecture 7: Branching processes 6 of 20

then

Var[ Zn ] = σ2 µn (1 + µ + µ2 + · · · + µn )

σ2 µn 1−µn+1 , µ 6= 1, (7.3)
1− µ
=
 σ 2 ( n + 1), µ=1

Proof. Since the distribution of Z1 is just { pn }n∈N0 , it is clear that

E[ Z1 ] = µ and Var[ Z1 ] = σ2 . We proceed by induction and assume
that the formulas (7.2) and (7.3) hold for n ∈ N. By Proposition 7.2,
the generating function PZn+1 is given as a composition PZn+1 (s) =
PZn ( P(s)). Therefore, if we use the identity E[ Zn+1 ] = PZ0 n+1 (1), we
get

PZ0 n+1 (1) = PZ0 n ( P(1)) P0 (1) = PZ0 n (1) P0 (1) = E[ Zn ]E[ Z1 ] = µn µ
= µ n +1 .

A similar (but more complicated and less illuminating) argument can

be used to establish (7.3).

EXTINCTION PROBABILITY

We now turn to the central question (the one posed by Galton). We

define extinction to be the following event:

E = {ω ∈ Ω : Zn (ω ) = 0 for some n ∈ N}.

It is the property of the branching process that Zm = 0 for all m ≥ n

whenever Zn = 0. Therefore, we can write E as an increasing union of
sets En , where
En = {ω ∈ Ω : Zn (ω ) = 0}.
Therefore, the sequence {P[ En ]}n∈N is non-decreasing and “continuity
of probability” (see the very first lecture) implies that

P[ E] = lim P[ En ].
n ∈N

The number p E = P[ E] is called the extinction probability. Using

generating functions, and, in particular, the fact that P[ En ] = P[ Zn =
0] = PZn (0) we get

p E = P[ E] = lim PZn (0) = lim P( P(. . . P(0) . . . )) .

n ∈N n ∈N | {z }
n P’s

It is amazing that this probability can be computed, even if the explicit

form of the generating function PZn is not known.

Last Updated: March 23, 2016

Lecture 7: Branching processes 7 of 20

Proposition 7.5. The extinction probability p E is the smallest non-negative

solution of the equation

x = P( x ), called the extinction equation,

where P is the generating function of the offspring distribution.

Proof. Let us show first that p E is a solution of the equation x = P( x ).

Indeed, P is a continuous function, so P(limn→∞ xn ) = limn→∞ P( xn )
for every convergent sequence { xn }n∈N0 in [0, 1] with xn → x∞ . Let us
take a particular sequence given by

xn = P( P(. . . P(0) . . . )) .
| {z }
n P’s

Then

1. p E = P[ E] = limn∈N xn , and

2. P( xn ) = xn+1 .

Therefore,

p E = lim xn = lim xn+1 = lim P( xn ) = P( lim xn ) = P( p E ),

n→∞ n→∞ n→∞ n→∞

and so p E solves the equation P( x ) = x.

The fact that p E is the smallest solution of x = P( x ) on [0, 1] is a bit
trickier to get. Let p0 be another solution of x = P( x ) on [0, 1]. Since
0 ≤ p0 and P is a non-decreasing function, we have

P (0) ≤ P ( p 0 ) = p 0 .

We can apply the function P to both sides of the inequality above to

get
P( P(0)) ≤ P( P( p0 )) = P( p0 ) = p0 .
Continuing in the same way we get

P[ En ] = P( P(. . . P(0) . . . )) ≤ p0 ,
| {z }
n P’

we get p E = limn∈N P[ En ] ≤ limn∈N p0 = p0 , so p E is not larger then

any other solution p0 of x = P( x ).

Example 7.6. Let us compute extinction probabilities in the cases from

Example 7.3.

1. p0 = 1, pn = 0, n ∈ N:
No need to use any theorems. p E = 1 in this case.

Last Updated: March 23, 2016

Lecture 7: Branching processes 8 of 20

2. p0 = 0, p1 = 1, pn = 0, n ≥ 2:
Like above, the situation is clear - p E = 0.

3. p0 = 0, p1 = 0, . . . , pk = 1, pn = 0, n ≥ k, for some k ≥ 2:
No extinction here - p E = 0.

4. p0 = p, p1 = q = 1 − p, pn = 0, n ≥ 2:
Since P(s) = p + qs, the extinction equation is s = p + qs. If p = 0,
the only solution is s = 0, so no extinction occurs. If p > 0, the only
solution is s = 1 - the extinction is guaranteed. It is interesting to
note the jump in the extinction probability as p changes from 0 to
a positive number.

5. p0 = p2 , p1 = 2pq, p2 = q2 , pn = 0, n ≥ 3:
Here P(s) = ( p + qs)2 , so the extinction equation reads

s = ( p + qs)2 .

p2
This is a quadratic in s and its solutions are s1 = 1 and s2 = q2 , if
we assume that q > 0. When p < q, the smaller of the two is s2 .
When p ≥ q, s = 1 is the smallest solution. Therefore

p2
p E = min(1, ).
q2

PROBLEMS

Problem 7.1. Let { Zn }n∈N0 be a simple branching process which starts

from one individual. Each individual has exactly three children, each 1.0

of whom survives until reproductive age with probability 0 < p < 1, 0.8

and dies before he/she is able to reproduce with probability q = 1 − p,

independently of his/her siblings. The children that reach reproduc- 0.6

tive age reproduce according to the same rule.

0.4

1. Write down the generating function for the offspring distribution.

0.2

2. For what values of p will the population go extinct with certainty

0.2 0.4 0.6 0.8 1.0
(probability 1). Hint: You don’t need to compute much. Just find the derivative
P0 (1) and remember the picture from class one the right

Solution:

1. The number of children who reach reproductive age is binomially

distributed with parameters 3 and p. Therefore, P(s) = ( ps + q)3 .

2. We know that the extinction happens with probability 1 if and only

if the graphs of functions s and P(s) meet only at s = 1, for s ∈

Last Updated: March 23, 2016

Lecture 7: Branching processes 9 of 20

[0, 1]. They will have met once before somewhere on [0, 1) if and
only if P0 (1) > 1. Therefore, the extinction happens with certainty
if P0 (1) = 3p( p 1 + q) = 3p ≤ 1, i.e., if p ≤ 1/3.

Problem 7.2. Let { Zn }n∈N0 be a branching process with offspring dis-

tribution { pn }n∈N0 and generating function P(s) = ∑∞ n
n=0 pn s . The
extinction is inevitable if

(a) p0 > 0

(b) P( 21 ) > 1
4

(c) P0 (1) < 1

(d) P0 (1) ≥ 1

(e) None of the above

Solution: The correct answer is (c).

(a) False. Take p0 = 1/3, p1 = 0, p2 = 2/3, and pn = 0, n > 2. Then

the equation P(s) = s reads 1/3 + 2/3s2 = s, and s = 1/2 is its
smallest solution. Therefore, the probability of extinction is 1/2.

(b) False. Take p0 = 0, p1 = 1/2, p2 = 1/2, and pn = 0, n > 2. Then

the equation P(s) = s reads 1/2s + 1/2s2 = s, and s = 0 is its
smallest solution. Therefore, the probability of extinction is 0,
but P(1/2) = 1/4 + 1/8 > 1/4.

(c) True. The condition P0 (1) < 1, together with the convexity of
the function P imply that the graph of P lies strictly above the
45-degree line for s ∈ (0, 1). Therefore, the only solution of the
equation P(s) = s is s = 1.

(d) False. Take the same example as in (a), so that P0 (1) = 4/3 >
1. On the other hand, the extinction equation P(s) = s reads
1/3 + 2/3s2 = s. Its smallest solution is s = 1/2.

(e) False.

Problem 7.3. Bacteria reproduce by cell division. In a unit of time,

a bacterium will either die (with probability 41 ), stay the same (with
probability 14 ), or split into 2 parts (with probability 21 ). The population
starts with 100 bacteria at time n = 0.

1. Write down the expression for the generating function of the distri-
bution of the size of the population at time n ∈ N0 . (Note: you can
use n-fold composition of functions.)

Last Updated: March 23, 2016

Lecture 7: Branching processes 10 of 20

2. Compute the extinction probability for the population.

3. Let mn be the largest possible number of bacteria at time n. Find

mn and compute the probability that there are exactly mn bacteria
in the population at time n, n ∈ N0 .

4. Given that there are 1000 bacteria in the population at time 50, what
is the expected number of bacteria at time 51?

Solution:
1. The generating function for the offspring distribution is

P(s) = 1
4 + 41 s + 12 s2 .
We can think of the population Zn at time n, as the sum of 100
independent populations, each one produced by one of 100 bacteria
in the initial population. The generating function for the number
of offspring of each bacterium is

P(n) (s) = P( P(. . . P(s) . . . ))

| {z }
n Ps

Therefore, since sums of independent variables correspond to prod-

ucts in the world of generating functions, the generating function
of Zn is given by
h i100
PZn (s) = P(n) (s) .

2. What happens to the offspring of one of the 100 bacteria in the zero-
th generation is independent of what happens to the offspring of
the others. Therefore, whether the progeny of one of those bacteria
goes extinct is independent of the extinction of the progeny of any
other. Hence, the extinction probability of the entire population
(which starts from 100) is the 100-th power of the extinction prob-
ability p E of the population which starts from a single bacterium.
To compute p E , we write down the extinction equation

s= 1
4 + 41 s + 21 s2 .
Its solutions are s1 = 1 and s2 = 12 , so p = s2 = 21 . Therefore, the
extinction probability for the entire population is ( 21 )100 .

3. The maximum size of the population at time n will occur if each

of the initial 100 bacteria splits into 2 each time, so mn = 100 × 2n .
For that to happen, there must be 100 splits to produce the first
generation, 200 for the second, 400 for the third, . . . , and 2n−1 ×
100 for the n-th generation. Each one of those splits happens with
probability 12 and is independent of other splits in its generation,
given the previous generations. It is clear that for Zn = mn , we
must have Zn−1 = mn−1 , . . . , Z1 = m1 , so

Last Updated: March 23, 2016

Lecture 7: Branching processes 11 of 20

P[ Zn = mn ] = P[ Zn = mn , Zn−1 = mn−1 , . . . Z1 = m1 , Z0 = m0 ]
= P[ Zn = mn | Zn−1 = mn−1 , Zn−2 = mn−2 , . . . ]P[ Zn−1 = mn−1 , Zn−2 = mn−2 , . . . ]
= P[ Zn = mn | Zn−1 = mn−1 ]×
× P[ Zn−1 = mn−1 | Zn−2 = mn−2 , Zn−3 = mn−3 , . . . ]P[ Zn−2 = mn−2 , . . . ]
= ...
= P[ Zn = mn | Zn−1 = mn−1 ]P[ Zn−1 = mn−1 | Zn−2 = mn−2 ] . . . P[ Z0 = m0 ]
= ( 21 )mn−1 ( 21 )mn−2 . . . ( 21 )m0
n −1 ) n −1)
= ( 21 )100(1+2+···+2 = ( 12 )100×(2

4. The expected number of offspring of each of the 1000 bacteria is

given by P0 (1) = 54 . Therefore, the total expected number of bacte-
ria at time 51 is 1000 × 54 = 1250.

Problem 7.4. A branching process starts from 10 individuals, and each

reproduces according to the probability distribution ( p0 , p1 , p2 , . . . ),
where p0 = 1/4, p1 = 1/4, p2 = 1/2, pn = 0, for n > 2. The extinction
probability for the whole population is equal to

(a) 1
1
(b) 2
1
(c) 20
1
(d) 200
1
(e) 1024

Solution: The correct answer is (e). The extinction probability for

the population starting from each of the 10 initial individuals is given
by the smallest solution of 1/4 + 1/4s + 1/2s2 = s, which is s =
1/2. Therefore, the extinction probability for the whole population
is (1/2)10 = 1/1024.

Problem 7.5. A (solitaire) game starts with 3 silver dollars in the pot.
At each turn the number of silver dollars in the pot is counted (call it
K) and the following procedure is repeated K times: a die is thrown,
and according to the outcome the following four things can happen

• If the outcome is 1 or 2 the player takes 1 silver dollar from the

pot.

• If the outcome is 3 nothing happens.

Last Updated: March 23, 2016

Lecture 7: Branching processes 12 of 20

• If the outcome is 4 the player puts 1 extra silver dollar in the

pot (you can assume that the player has an unlimited supply of
silver dollars).

• If the outcome is 5 or 6, the player puts 2 extra silver dollars in

the pot.

If there are no silver dollars on in the pot, the game stops.

1. Compute the expected number of silver dollars in the pot after turn
n ∈ N.

2. Compute the probability that the game will stop eventually.

3. Let mn be the maximal possible number of silver dollars in the pot

after the n-th turn? What is the probability that the actual number
of silver dollars in the pot after n turns is equal to mn − 1?

Solution: The number of silver dollars in the pot follows a branch-

ing process { Zn }n∈N0 with Z0 = 3 and offspring distribution whose
generating function P(s) is given by

P(s) = 1
3 + 16 s + 16 s2 + 13 s3 .

1. The generating function PZn of Zn is ( P( P(. . . P(s) . . . )))3 , so

3n +1
E[ Zn ] = PZ0 n (1) = 3( P0 (1))n = 3( 16 + 2 16 + 3 31 )n =
2n

2. The probability p that the game will stop is the extinction probabil-
ity of the process. We solve the extinction equation P(s) = s to get
the extinction probability corresponding to the case Z0 = 1, where
there is 1 silver dollar in the pot:

P(s) = s ⇔ 2 + s + s2 + 2s3 = 6s ⇔ (s − 1)(s + 2)(2s − 1) = 0.

The smallest solution in [0, 1] of the equation above is 1/2. To get

the true (corresponding to Z0 = 3) extinction probability we raise
it to the third power to get p = 18 .

3. The maximal number mn of silver dollars in the pot is achieved if

we roll 5 or 6 each time. In that case, there will be 3 rolls in the first
turn, 9 = 32 in the second, 27 = 33 in the third, etc. That means
that after n turns, there will be at most mn = 3n+1 silver dollars
in the pot. In order to have exactly mn − 1 silver dollars in the pot
after n turns, we must keep getting 5s and 6s throughout the first
n − 2 turns. The probability of that is

n−1 +3n−2 +···+3 1 n− 3

( 31 )3 = ( 31 ) 2 3 2.

Last Updated: March 23, 2016

Lecture 7: Branching processes 13 of 20

After that, we must get a 5 or a 6 in 3n − 1 throws and a 4 in a

single throw during turn n. There are 3n possible ways to choose
the order of the throw which produces the single 4, so the later
probability is
n n
3n ( 13 )3 −1 ( 16 ) = 12 ( 13 )3 −n .

We multiply the two probabilities to get

1 n +1 − n − 3
P[ Zn = mn − 1] = 12 ( 13 ) 2 3 2.

Problem 7.6. It is a well-known fact(oid) that armadillos always have

identical quadruplets (four offspring). Each of the 4 little armadillos
has a 1/3 chance of becoming a doctor, a lawyer or a scientist, inde-
pendently of its 3 siblings. A doctor armadillo will reproduce further
with probability 2/3, a lawyer with probability 1/2 and a scientist with
probability 1/4, again, independently of everything else. If it repro-
duces at all, an armadillo reproduces only once in its life, and then
leaves the armadillo scene. (For the purposes of this problem assume
that armadillos reproduce asexually.) Let us call the armadillos who
have offspring fertile.

1. What is the distribution of the number of fertile offspring? Write

down its generating function.

2. What is the generating function for the number of great-grandchildren

an armadillo will have? What is its expectation? (Note: do not ex-
pand powers of sums)

3. Let the armadillo population be modeled by a branching process,

and let’s suppose that it starts from exactly one individual at time
0. Is it certain that the population will go extinct sooner or later?

Solution:

1. Each armadillo is fertile with probability p, where

p = P[ Fertile ] = P[ Fertile | Lawyer ] P[ Lawyer ]

+ P[ Fertile | Doctor ] P[ Doctor ]
+ P[ Fertile | Scientist ] P[ Scientist ]
1
= 2 × 13 + 32 × 13 + 14 × 1
3 = 5
12 .

Therefore, the number of fertile offspring is binomial with n = 4

5
and p = 12 . The generating function of this distribution is P(s) =
7 5 4
( 12 + 12 s) .

2. To get the number of great-grandchildren, we first compute the

generating function Q(s) of the number of fertile grandchildren.

Last Updated: March 23, 2016

Lecture 7: Branching processes 14 of 20

This is simply given by the composition of P with itself, i.e.,

7 5 7 5 4 4
P( P(s)) = ( 12 + 12 ( 12 + 12 s ) ) .

Finally, the number of great-grandchildren is the number of fertile

grandchildren multiplied by 4. Therefore, its generating function is
given by

Q(s) = P( P(s4 )) = ( 12
7
+ 5 7
12 ( 12 + 5 4 4 4
12 s ) ) .

The compute the expectation, we need to evaluate Q0 (1):

Q0 (s) = ( P( P(s4 )))0 = P0 ( P(s4 )) P0 (s4 )4s3

and
P0 (s) = 4 12
5 7
( 12 + 5 3
12 s ) ,

so that
Q0 (1) = 4P0 (1) P0 (1) = 100
9 .

3. We need to consider the population of fertile armadillos. Its off-

7 5
spring distribution has generating function P(s) = ( 12 + 12 s)4 , so
the population will go extinct with certainty if and only if the ex-
tinction probability is 1, i.e., if s = 1 is the smallest solution of
the extinction equation s = P(s). We know, however, that P0 (1) =
5
5 × 12 = 106 > 1, so there exists a positive solution to P ( s ) = s
which is smaller than 1. Therefore, it is not certain that the popula-
tion will become extinct sooner or later.

Problem 7.7. Branching in alternating environments. Suppose that a

branching process { Zn }n∈N0 is constructed in the following way: it
starts with one individual. The individuals in odd generations repro-
duce according to an offspring distribution with generating function
Podd (s) and those in even generations according to an offspring distri-
bution with generating function Peven (s). All independence assump-
tions are the same as in the classical case.

1. Find an expression for the generating function PZn of Zn .

2. Derive the extinction equation.

Solution:

1. Since n = 0 is an “even” generation, the distribution of the number

of offspring of the initial individual is given by Peven (s). Each of
the Z1 individuals in the generation n = 1 reproduce according the
generating function Podd , so

PZ2 (s) = P Z (s) = Peven ( Podd (s)).

∑k=1 1 Z2,k

Last Updated: March 23, 2016

Lecture 7: Branching processes 15 of 20

Similarly, PZ3 (s) = Peven ( Podd ( Peven (s))), and, in general, for n ∈
N0 ,

PZ2n (s) = Peven ( Podd ( Peven (. . . Podd (s) . . . )),, and

| {z }
2n Ps
(7.4)
PZ2n+1 (s) = Peven ( Podd ( Peven (. . . Peven (s) . . . )), .
| {z }
2n+1 Ps

2. To compute the extinction probability, we must evaluate the limit

p E = P[ E] = lim P[ Zn = 0] = lim PZn (0).

n→∞ n→∞

Since the limit exists (see the derivation in the classical case in the
notes), we know that any subsequence also converges towards the
same limit. In particular, p E = limn→∞ x2n , where

xn = P[ Zn = 0] = PZn (0).

By the expression for PZn above, we know that x2n+2 = Peven ( Podd ( x2n )),
and so

p E = lim x2n+2 = lim Peven ( Podd ( x2n )) = Peven ( Podd (lim x2n ))
n→∞ n n
= Peven ( Podd ( p E )),

which identifies

p E = Peven ( Podd ( p E )), (7.5)

as the extinction equation. I will leave it up to you to figure out

whether p E is characterized as the smallest positive solution to (7.5).

Problem 7.8. In a branching process, the offspring distribution is given

by its characteristic function

P(s) = as2 + bs + c

where a, b, c > 0 and a + b + c = 1.

(i) Find the extiction probability for this branching process.

(ii) Give a necessary and sufficient condition for sure extinction.

Solution:

(i) By Proposition 7.5 in the lecture notes, the extinction probability

is the smallest non-negative solution to

P( x ) = x.

Last Updated: March 23, 2016

Lecture 7: Branching processes 16 of 20

So, in this case (remembering that b = 1 − a − c):

ax2 + bx + c = x ⇒ ax2 − ( a + c) x + c = 0,

i.e.,
( ax − c)( x − 1) = 0.
The solutions of this equation are 1 and c/a, and, so, the small-
est solution in [0, 1] is

– p E = 1, if c ≥ a, and
– p E = c/a, if c < a.

(ii) The discussion above immediately yields the answer to question

(ii): the necessary and sufficient condition for certain extinction
is c ≥ a.

Problem 7.9 (Optional). The purpose of this problem is to describe

a class of offspring distributions (pmfs) for which an expression for
PZn (s) can be obtained.
An N0 -valued distribution is said to be of fractional-linear type if its
generating function P has the following form

as + b
P(s) = , (7.6)
1 − cs
for some constants a, b, c ≥ 0. In order for P to be a generating function
of a probability distribution we must have P(1) = 1, i.e. a + b + c = 1,
which will be assumed throughout the problem.

1. What (familiar) distributions correspond to the following special

cases (in each case identify the distribution and its parameters):

(a) c = 0
(b) a = 0

2. Let A be the following 2 × 2 matrix

" # " #
a b n a(n) b(n)
A= and let A = (n)
−c 1 c d(n)

be its nth power (using matrix multiplication, of course). Using

mathematical induction prove that

a(n) s + b(n)
P ( P ( . . . P ( s ) . . . ) = (n) . (7.7)
| {z } c s + d(n)
n Ps

Last Updated: March 23, 2016

Lecture 7: Branching processes 17 of 20

3. Take a = 0 and b = c = 1/2. Show inductively that

" #
1 −( n − 1 ) n
An = n . (7.8)
2 −n n+1

Use that to write down the generating function of Zn in the linear-

fractional form (7.6).

4. Find the extinction probability as a function of a, b and c in the

general case (don’t forget to use the identity a + b + c = 1!).

Solution: Note: It seems that not everybody is familiar with the prin-
ciple of mathematical induction. It is a logical device you can use if
you have a conjecture and want to prove that it is true for all n ∈ N.
Your conjecture will be typically look like

For each n ∈ N, the statement P(n) holds.

where P(n) is some assertion which depends on n. For example, P(n)

could be
n ( n + 1)
“ 1+2+3+···+n = ” (7.9)
2
The principle of mathematical induction says that you can prove that
your statement is true for all n ∈ N by doing the following two things:

1. Prove the statement for n = 1, i.e., prove P(1). (induction basis)

2. Prove that the implication P(n) ⇒ P(n + 1) always holds, i.e., prove
the statement for n + 1 if you are, additionally, allowed to use the
statement for n as a hypothesis. (inductive step)

As an example, let us prove the statement (7.9) above. For n = 1, P(1)

reads “1 = 1”, which is evidently true. Supposing that P(n) holds, i.e.,
that
n ( n + 1)
1+2+···+n = ,
2
we can add n + 1 to both sides to get

n ( n + 1) n ( n + 1) + 2( n + 1)
1 + 2 + · · · + n + ( n + 1) = + ( n + 1) =
2 2
2
n + 3n + 2 (n + 1)(n + 2)
= = ,
2 2
which is exactly P(n + 1). Therefore, we managed to prove P(n + 1)
using P(n) as a crutch. The principle of mathematical induction says
that this is enough to be able to conclude that P(n) holds for each n,
i.e., that (7.9) is a ture statement for all n ∈ N.
Back to the solution of the problem:

Last Updated: March 23, 2016

Lecture 7: Branching processes 18 of 20

1. (a) When c = 0, P(s) = as + b - Beronulli distribution with success

probability a = 1 − b.
(b) For a = 0, P(s) = 1−bcs - Geometric distribution with success
probability b = 1 − c.

2. For n = 1, a(1) = a, b(1) = b, c(1) = −c and d(1) = 1, so clearly

a (1) s + b (1)
P(s) = .
c (1) s + d (1)
Suppose that the equality (7.7) holds for some n ∈ N. Then
" # " #" #
a ( n +1) b ( n +1) n +1 n a(n) b(n) a b
=A = A A = (n)
c ( n +1) d ( n +1) c d(n) − c 1
" #
a a(n) − c b(n) b a(n) + b(n)
=
a c(n) − c d(n) b c(n) + d(n)

On the other hand, by the inductive assumption,

a(n) P ( s ) + b(n) a(n) 1as−+csb + b(n)

P ( P ( . . . P ( s ) . . . ) = (n) =
| {z } c P ( s ) + d(n) c(n) 1as−+csb + d(n)
n+1 Ps

( a a(n) − c b(n) ) s + b a(n) + b(n)

= .
( a c(n) − c d(n) ) s + b c(n) + d(n)

Therefore, (7.7) also holds for n + 1. By induction, (7.7) holds for

all n ∈ N.

3. Here
" # " # " #
0 1/2 1 0 1 1 (1 − 1) 1
A= = 2 = 21
−1/2 1 −1 2 −1 1+1

so the statement holds for n = 1 (induction basis). Suppose that

(7.8) holds for some n. Then
" # " #
n +1 n 1 −( n − 1) n 1 0 1
A = A A = 2n
−n n + 1 2 −1 2
" # " #
1 −n −(n − 1) + 2n 1 −n n+1
= n +1 = n +1
2 − n − 1 − n + 2( n + 1) 2 −(n + 1) n + 2

which is exactly (7.8) for n + 1 (inductive step). Thus, (7.8) holds

for all n ∈ N. By the previous part, the generating function of Zn
is given by
− 1 (n − 1)s + 21 n
PZn (s) = 21 .
− 2 ns + 12 (n + 1)

Last Updated: March 23, 2016

Lecture 7: Branching processes 19 of 20

We divide the numerator and the denominator by 21 (n + 1) to get

the above expression into the form dictated by (7.6):
−1 s + n
− nn+ 1 n +1
PZn (s) = n .
1 − n+ 1s

Note that a = − nn− 1

+1 , b =
n
n +1 and c = n
n +1 so that a + b + c =
−n+1+n+n = 1, as required.
n +1

4. For the extinction probability we need to find the smallest solution

of
as + b
s=
1 − cs
in [0, 1]. The equation above transforms into a quadratic equation
after we multiply both sides by 1 − cs

s − cs2 = as + b, i.e., cs2 + ( a − 1)s + b = 0. (7.10)

We know that s = 1 is a solution and that a − 1 = −b − c, so we

can factor (7.10) as

cs2 + ( a − 1)s + b = (s − 1)(cs − b).

If c = 0, the only solution is s = 1. If c 6= 0, the solutions are 1 and

c . Therefore, the extinction probability P[ E ] is given by
b


1, c = 0,
P[ E ] =
min(1, b ), otherwise .
c

Problem 7.10 (Optional). For a branching process { Zn }n∈N0 , denote

by S the total number of individuals that ever lived, i.e., set
∞ ∞
S= ∑ Zn = 1 + ∑ Zn .
n =0 n =1

(i) Assume that the offspring distribution has the generating func-
tion given by
P(s) = p + qs.
Find the generating function PS in this case.

(ii) Assume that the offspring distribution has the generating func-
tion given by
P(s) = p/(1 − qs).
Find PS in this case.

(iii) Find the general expression for E[S] and calculate this expecta-
tion in the special cases (i) and (ii).

Last Updated: March 23, 2016

Lecture 7: Branching processes 20 of 20

Solution: In general, the r.v. S satisfies the relationship

∞
∞ ∞
PS (s) = E[s1+∑n=1 Zn ] = ∑ E[s1+∑n=1 Zn |Z1 = k]P[Z1 = k]
k =0
∞ ∞
= ∑ sE[sZ1 +∑n=2 Zn |Z1 = k]P[Z1 = k]
k =0

When Z1 = k, the expression Z1 + ∑∞ n=2 Zn counts the total number

of individuals in k separate and independent Branching processes -
one for each of k members of the generation at time k = 1. Since this
random variable is the sum of k independent random variables, each
of which has the same distribution as S (why?), we have
∞
E[s Z1 +∑n=2 Zn | Z1 = k] = [ PS (s)]k .

Consequently, PS is a solution of the following equation

∞
PS (s) = s ∑ [ PS (s)]k P[Z1 = k] = sP( PS (s)).
k =0

(i) In this case,

sp
PS (s) = s( p + qPS (s)) ⇒ PS (s) = .
1 − sq

(iii) Here, PS (s) must satisfy

PS (s)(1 − qPS (s)) − sp = 0,

i.e.,

qPS (s)2 − PS (s) + sp = 0.

Solving the quadratic, we get as the only sensible solution (the

one that has PS (0) = 0):
p
1 − 1 − 4spq
PS (s) = .
2q
Note that PS (1) < 1 if p < q. Does that surprise you? Should
not: it is possible that S = +∞.

(iii) Using our main “recursion” for PS (s), we get

PS0 (s) = (sPZ1 ( PS (s)))0 = PZ1 ( PS (s)) + sPZ0 1 ( P(s)) P0 (s).

So, for s = 1,

E[S] = PS0 (1) = PZ1 ( PS (1)) + PZ0 1 ( PS (1)) Ps0 (1) = 1 + µE[S].

If µ ≥ 1, E[S] = +∞. If µ < 1,

1
E[ S ] = .
1−µ

Last Updated: March 23, 2016