Download as:
Rating : ⭐⭐⭐⭐⭐
Price: $10.99
Language:EN
Pages: 20

Each one produced one bacteria the initial population

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?

A MATHEMATICAL MODEL

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

2 of 20
Zn+1 = Zn

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

4 of 20

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,

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

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

distribution {pn}n∈N is given by P(s) = (p + qs)2. Then PZn = (p + q(p + q(. . . p + qs)2. . . )2)2 .

Unlike the example above, it is not so easy to simplify the above� n pairs of parentheses�� �

6 of 20

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

P[En] = P(P(. . . P(0) . . . ))≤ p′,

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

Problem 7.1. Let {Zn}n∈N0 be a simple branching process which starts from one individual. Each individual has exactly three children, each

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

(probability 1). Hint: You don’t need to compute much. Just find the derivative

0.6

0.2 0.4 0.6 0.8 1.0

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.

Lecture 7: Branching processes

10 of 20

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

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

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

Lecture 7: Branching processes

12 of 20

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.

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

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

+ P[ Fertile | Doctor ] P[ Doctor ]

(7 12+ 5 12s)4.

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

15 of 20

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

16 of 20

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

An=1
n
2n −n

n + 1

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

that

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:

(b) For a = 0, P(s) = 1−cs- Geometric distribution with success b

probability b = 1 − c.

On the other hand, by the inductive assumption,

P(P(. . . P(s) . . . )� n+1 Ps�� �

=a(n)P(s) + b(n) c(n)P(s) + d(n) =

= 2n+1 1 �−n − 1 −n (n − 1) + 2n −n + 2(n + 1)

1 0 1
2

1

2 −n
(n + 1)
= 1
2n+1
19 of 20

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.

20 of 20


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,

PS(s) = s(p + qPS(s)) ⇒ PS(s) =

sp
1 − sq.

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

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

Copyright © 2009-2023 UrgentHomework.com, All right reserved.