8 BRANCHING PROCESSES HINT for part (A):The Taylor series approximation to (t)at=1 leads to the following ap- proximate relationship,valid for large n: 1-9a+10)≈1-pn0)-2p"11-pno, which at first does not seem to help,but on further inspection does.The trick is to change variables:ifn is a sequence of positive numbers that satisfies the recursion Xn+1=xn-bxn then the sequence y:=1/xn satisfies yn+i=yn+b+b/yn+.... Problem5.There's a Galton-Watson processinmy random walk!Let S be the simple nearest- neighbor random walk on the integers started at So=1.Define T to be the time of the first visit to the origin,that is,the smallest n>1 such that S=0.Define Zo =1 and T-1 Zk=>1{Xn=k and Xn+1=k+1]. n=0 In words,Zk is the number of times that the random walk Xn crosses from k to k+1 before first visiting 0. (A)Prove that the sequence {Zk}o is a Galton-Watson process,and identify the offspring dis- tribution as a geometric distribution. (B)Calculate the probability generating function of the offspring distribution,and observe that it is a linear fractional transformation.(See Ahlfors,Complex Analysis,ch.1 for the definition and basic theory of LFTs.Alternatively,try the Wikipedia article.) (C)Use the result of(B)to find out as much as you can about the distribution of Zk. (D)Show that T=Zis the total number of individuals ever born in the course of the Galton-Watson process,and show that T(the extinction time of the Galton-Watson process)is the maximum displacement M from 0 attained by the random walk before its first return to the origin.What does the result of problem 4,part(B),tell you about the distribution of M? 2.YULE'S BINARY FISSION PROCESS 2.1.Definition and Construction.The Yule process is a continuous-time branching model, in which individuals undergo binary fission at random times.It evolves as follows:Each in- dividual,independently of all others and of the past of the process,waits an exponentially distributed time and then splits into two identical particles.(It is useful for the construction below to take the view that at each fission time the fissioning particle survives and creates one new clone of itself.)The exponential waiting times all have mean 1.Because the exponential random variables are mutually independent,the probability that two fissions will occur simul- taneously is 0. A Yule process started by 1 particle at time 0 can be built from independent Poisson processes as follows.Let {Ni(t)}ieN be a sequence of independent Poisson counting processes.Since the8 BRANCHING PROCESSES HINT for part (A): The Taylor series approximation to ϕ(t ) at ζ = 1 leads to the following ap￾proximate relationship, valid for large n: 1 − ϕn+1 (0) ≈ 1 − ϕn (0) − 1 2 ϕ 00(1)(1 − ϕn (0))2 , which at first does not seem to help, but on further inspection does. The trick is to change variables: if xn is a sequence of positive numbers that satisfies the recursion xn+1 = xn − b x 2 n then the sequence yn := 1/xn satisfies yn+1 = yn + b + b /yn + .... Problem 5. There’s a Galton-Watson process inmy random walk! LetSn be the simple nearest￾neighbor random walk on the integers started at S0 = 1. Define T to be the time of the first visit to the origin, that is, the smallest n ≥ 1 such that Sn = 0. Define Z0 = 1 and Zk = T X−1 n=0 1{Xn = k and Xn+1 = k + 1}. In words, Zk is the number of times that the random walk Xn crosses from k to k +1 before first visiting 0. (A) Prove that the sequence {Zk }k≥0 is a Galton-Watson process, and identify the offspring dis￾tribution as a geometric distribution. (B) Calculate the probability generating function of the offspring distribution, and observe that it is a linear fractional transformation. (See Ahlfors, Complex Analysis, ch. 1 for the definition and basic theory of LFTs. Alternatively, try the Wikipedia article.) (C) Use the result of (B) to find out as much as you can about the distribution of Zk . (D) Show that T = P k≥1 Zk is the total number of individuals ever born in the course of the Galton-Watson process, and show that τ (the extinction time of the Galton-Watson process) is the maximum displacement M from 0 attained by the random walk before its first return to the origin. What does the result of problem 4, part (B), tell you about the distribution of M ? 2. YULE’S BINARY FISSION PROCESS 2.1. Definition and Construction. The Yule process is a continuous-time branching model, in which individuals undergo binary fission at random times. It evolves as follows: Each in￾dividual, independently of all others and of the past of the process, waits an exponentially distributed time and then splits into two identical particles. (It is useful for the construction below to take the view that at each fission time the fissioning particle survives and creates one new clone of itself.) The exponential waiting times all have mean 1. Because the exponential random variables are mutually independent, the probability that two fissions will occur simul￾taneously is 0. A Yule process started by 1 particle at time 0 can be built from independent Poisson processes as follows. Let {Nj (t )}j∈N be a sequence of independent Poisson counting processes. Since the