Each one produced one bacteria the initial population

A MATHEMATICAL MODEL

The model proposed by Watson1was the following:
1. A population starts with one individual at time n = 0: Z0 = 1.

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)

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

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

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:

A GENERATING-FUNCTION APPROACH

Having defined and constructed a branching process with offspring

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.,

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:

nentially: P(s) = sk, so PZn(s) = ((. . . (sk)k. . . )k)k= skn. Therefore,

Zn = kn, for n ∈ N.

fore,

(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.

Var[Zn] = σ2µn(1 + µ + µ2+ · · · + µn)

=σ2µn 1−µn+1

PZn(P(s)). Therefore, if we use the identity E[Zn+1] = P′Zn+1(1), we

get

EXTINCTION PROBABILITY

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

En = {ω ∈ Ω : Zn(ω) = 0}.

Therefore, the sequence {P[En]}n∈N is non-decreasing and “continuity of probability” (see the very first lecture) implies that

It is amazing that this probability can be computed, even if the explicit pE = P[E] = lim n∈NPZn(0) = lim n∈NP(P(. . . P(0) . . . )) � n P’s�� � .

form of the generating function PZn is not known.

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

where P is the generating function of the offspring distribution.

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

2. P(xn) = xn+1.

trickier to get. Let p′be another solution of x = P(x) on [0, 1]. Since

0 ≤ p′and P is a non-decreasing function, we have

Continuing in the same way we get

Example 7.3.

1. p0 = 1, pn = 0, n ∈ N:

3. p0 = 0, p1 = 0, . . . , pk = 1, pn = 0, n ≥ k, for some k ≥ 2: No extinction here - pE = 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.

PROBLEMS

Last Updated: March 23, 2016

(c) P′(1) < 1

(d) P′(1) ≥ 1

(c) True. The condition P′(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 P′(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.

2. Compute the extinction probability for the population.

P(s) =1 4+ 1 4s + 1 2s2.

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

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 pE of the population which starts from a single bacterium.

To compute pE, we write down the extinction equation

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, . . . ] = . . .

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

reproduces according to the probability distribution (p0, p1, p2, . . . ),

the population starting from each of the 10 initial individuals is given

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,

Last Updated: March 23, 2016

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?

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.

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 3npossible ways to choose the order of the throw which produces the single 4, so the later

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. To get the number of great-grandchildren, we first compute the generating function Q(s) of the number of fertile grandchildren.

Finally, the number of great-grandchildren is the number of fertile grandchildren multiplied by 4. Therefore, its generating function is given by

so that
Q′(1) = 4P′(1)P′(1) =100 9.

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

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.

Last Updated: March 23, 2016

pE = lim n→∞x2n+2 = lim nPeven(Podd(x2n)) = Peven(Podd(lim nx2n))

= Peven(Podd(pE)),

P(s) = as2+ bs + c

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

P(x) = x.

Last Updated: March 23, 2016

– pE = 1, if c ≥ a, and
– pE = 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.

(a) c = 0

(b) a = 0

Last Updated: March 23, 2016

Use that to write down the generating function of Zn in the linear-fractional form (7.6).

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

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.,

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:

On the other hand, by the inductive assumption,

We divide the numerator and the denominator by1 2(n + 1) to get the above expression into the form dictated by (7.6):

4. For the extinction probability we need to find the smallest solution of
s =as + b
1 − cs
in [0, 1]. The equation above transforms into a quadratic equation after we multiply both sides by 1 − cs

P[E] =1,

min(1,b c), otherwise .
c = 0,

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.

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

∞
= k=0 ∑sE[sZ1+∑∞n=2Zn|Z1 = k]P[Z1 = k]

(i) In this case,

E[S] = P′S(1) = PZ1(PS(1)) + P′Z1(PS(1))P′s(1) = 1 + µE[S].