88 CONTINUOUS MARKOV CHAINS3.4. birth-death. Continuous birth-death Markov chains are very sim-ilar to countable Markov chains. One new concept is “explosion” whichmeans that an infinite number of state change events can happen in afinite amount of time.3.4.1. birth and explosion. Suppose that people never die and thatbirth is a Poisson process.Xt= population at time tS = {1, 2, 3, · · · }λn= rate of birth when population size is nIn other words,α(n, n + 1) = λnα(n, n) = −λnand all other entries of the infinite matrix A are zero.Question: What is the probability of explosion?I.e., What is the probability that the population size will go to infinitein a finite amount of time?Answer: This probability is either 0 or 1!Proof. Suppose thatp = P(explosion occurs at some time T < 1000)Then either p = 0 or p > 0.If p = 0 then the population will never explode.If p > 0 thenP(no explosion in 1000 years) = 1 − p < 1If we wait N millennia then the probability of no explosion will be(1 − p)NSince this goes to 0 as N → ∞, the probability of never having anexplosion is zero. !So, we just have to determine whether the population is destined toexplode or not. To figure this out I computed the expected time itwould take for the population size to go to infinity. If this time if finitewe have an explosion.T1= time it takes to jump 1 → 2T2= time it takes to jump 2 → 3T = time to explosion = T1+ T2+ · · ·MATH 56A SPRING 2008 STOCHASTIC PROCESSES 89E(T ) = E!"Tn#="E(Tn) =∞"n=11λnTheorem 3.10. The population exploses a.s. if and only if∞"n=11λnconverges.3.4.2. conversion to discrete time. Next I considered birth and death.But I didn’t want 0 to be an absorbing state. So, I assumed that therewas spontaneous generation.Xt∈ S = {0, 1, 2, 3, · · · }with all rates positive:0 < λn= birth rate when Xt= n , n ≥ 00 < µn= death rate when Xt= n , n ≥ 1Let J1, J2, · · · be the jump times (the times when the population sizejumps).We convert to discrete time so that we can use the formulas that wealready know:Zk= population size after k birth-death eventsThe transition probabilities for this countable Markov chain are givenby:Lemma 3.11.P(Zk+1= n + 1 | Zk= n ) =λnλn+ µnP(Zk+1= n − 1 | Zk= n ) =µnλn+ µnProof. If we chop up the time into small intervals of length ∆t thenonly one event will occur in each interval. The probability that therewill be a birth in one of these time intervals isP(Xt+∆t= n + 1 | Xt= n ) ≈ λn∆tand the probability of death will beP(Xt+∆t= n − 1 | Xt= n ) ≈ µn∆t90 CONTINUOUS MARKOV CHAINSSince only one of these occur, the probability of a birth or death willbe the sum:P(Xt+∆t'= n | Xt= n ) ≈ λn∆t + µn∆tand the conditional probability of a birth will be:P(Xt+∆t= Xt+ 1 | Xt+∆t'= Xt) ≈λn∆tλn∆t + µn∆t=λnλn+ µnTaking the limit as ∆t → 0 we get:•nn + 1 •∆t ∆t ∆t t t + ∆tP(Xt+dt= Xt+ 1 | Xt+dt'= Xt) ≈λndtλndt + µndt=λnλn+ µn!(1) When is Zntransient, null-recurrent, positive recurrent?(2) When is Xtexplosive?(3) What is the relation between explosion and recurrence?The correct answer to the last problem is thatZnrecurrent ⇒ XtnonexplosiveThe reason is that, when Znis recurrent, with probability one youreturn to the same state over and over. The expected return time isthe same each time, say 100 years. If you return to the same placeonce every 100 years, it will take forever to return an infinite numbersof times. If you want to explode after that you don’t have time.Example 3.12. I asked these questions in the special case:λn= birth rate = n + 1µn= death rate = nMATH 56A SPRING 2008 STOCHASTIC PROCESSES 91· · · ≤ n n + 1 ≤ · · ·• •λnµn+13.4.3. positive recurrent. To see if Xtis positive recurrent we have tofind an invariant distribution. This comes from the picture above. Inorder for the rate of movement from ≤ n to ≥ n + 1 to be the same asthe reverse rate, the invariant distribution must satisfy:π(n)λn= π(n + 1)µn+1So,π(n + 1) = π(n)λnµn+1= π(n − 1)λn−1λnµnµn+1= · · · = π(0)λnλn−1· · · λ0µn+1µn· · · µ1The sum of these numbers must be finite. So,Theorem 3.13. Xtis positive recurrent if and only if∞"n=0λnλn−1· · · λ0µn+1µn· · · µ1< ∞I.e., iff the series converges.In the special case λn= n + 1, µn= n each fraction is equal to 1.So, the sum is1 + 1 + 1 + 1 + · · · = ∞So, the series diverges and the Markov chain is not positive recurrent.3.4.4. transient. To see if Xtis transient, we look at the discrete chainZnand try to find the function α(n) so that α(0) = 1 and inf α(n) = 0.The equation for α (n) is:α(n) ="p(n, m)α(m)Since we can only go up and down by one this is:α(n) = p(n, n + 1)α(n + 1) + p(n, n − 1)α(n − 1)α(n) =λnα(n + 1)λn+ µn+µnα(n − 1)λn+ µn(λn+ µn)α(n) = λnα(n + 1) + µnα(n − 1)This equation can be rewritten asµn(α(n) − α(n − 1)$ %& '∆nα) = λn(α(n + 1) − α(n)$ %& '∆n+1α)µn∆nα = λn∆n+1α92 CONTINUOUS MARKOV CHAINSSo,∆n+1α =µnλn∆nα =µnλnµn−1λn−1∆n−1α = · · ·α(n + 1) − α(n) =µn· · · µ1λn· · · λ1(α(1) − α(0))α(n) − α(n − 1) =µn−1· · · µ1λn−1· · · λ1(α(1) − α(0))Adding these up and canceling terms we get:α(n + 1) − α(0) =n"k=0µk−1· · · µ1λk−1· · · λ1(α(1) − α(0))Theorem 3.14. Xtis transient if and only ifn"k=0µk−1· · · µ1λk−1· · · λ1< ∞I.e., iff this series converges.In the special case λn= n + 1, µn= n , the fraction is:µk−1· · · µ1λk−1· · · λ1=(k − 1) · · · 1k · · · 2=1kBut this gives the harmonic series:"1k= ∞So, the chains Znand Xtare not transient.Therefore, it must be null-recurrent.3.4.5. explosion. Recurrent implies nonexplosive. So, there is no ex-plosion. The correct calculation which shows this is:yn= expected time it takes to get from X = n to X = n + 1yn=1λn+ µn+µnλn+ µn(yn−1+ yn)yn=12n + 1+n2n + 1(yn−1+ yn)n + 12n + 1yn=12n + 1n2n + 1yn−1yn= 1 +n2n + 1yn−1≥ 1since y0= 1. So,"yn≥ 1 + 1 + 1 + · · · = ∞and there is no