2. Countable Markov Chains2.1. Concept and examples2.2. extinction probabilityMATH 56A SPRING 2008STOCHASTIC PROCESSESKIYOSHI IGUSAContents2. Countable Markov Chains 582.1. Concept and examples 582.2. extinction probability 60Date: February 13, 2008.5758 COUNTABLE MARKOV CHAINS2. Countable Markov ChainsWe will now talk about countably infinite Markov chains. The con-cept is the same but having an infinite number of states makes severalqualitative differences.2.1. Concept and examples. We will study Markov chains withcountably infinite number of states. For example, we could take thenonnegative integers:S = {0, 1, 2, 3, 4, · · · }or all integers:S = Z = {· · · , −3, −2, −1, 0, 1, 2, 3, · · · }.We will also study the set of integer points in n-dimensional space:S = Zn= {(x1, x2, · · · , xn) ∈ Rn| each xi∈ Z}.This is called the integer lattice in Rn.The transition matrix P is now infinite:P = (pij) = (p(i, j)).The numbers still mean the same thing:pij= p(i, j) = P(Xn+1= j | Xn= i).And they still satisfy the condition that 0 ≤ pij≤ 1 and the rows addup to one. But now this means that we have an infinite series addingto 1. For example, if S = {0, 1, 2 · · · } then the condition is:pi0+ pi1+ pi2+ pi3+ · · · = 1.In the general case, the condition is:Xjpij= 1.2.1.1. example: random walk on Z. In the first example I only posedthe question but didn’t answer it. This is the example where S = Zand, at each point, there is a probability of p of going to the right and1 − p of going to the left:• • •p//1−poo• •P(Xn+1= x + 1 | Xn= x) = p(x, x + 1) = pP(Xn+1= x − 1 | Xn= x) = p(x, x − 1) = 1 − pMATH 56A SPRING 2008 STOCHASTIC PROCESSES 59The question is: If p ≥12then how certain is it that you will go to+∞? You might want to write the question as:P( limn→∞Xn= ∞) = ?However, this doesn’t quite make sense because the limit may not ex-ist. The Markov chain might (and will) oscillate wildly. The correctquestion is:P(lim sup Xn= ∞) = ?Definition 2.1. For any sequence or real numbers xn,lim sup xn:= limn→∞(sup{xn, xn+1, xn+2, · · · })where “sup” is short for supremum which means maximum for a finiteset and least upper bound for an infinite set.For any sequence of real numbers x0, x1, · · · the supremumssup{x0, x1, · · · } ≥ sup{x1, x2, · · · } ≥ sup{x2, x3, · · · } ≥ · · ·form a nonincreasing sequence of real numbers which may all be +∞.Therefore, they always have a limit in the set of real numbers unionwith +∞:lim sup xn∈ [−∞, +∞].(Any bounded nonincreasing sequence has a limit.)Similarly, the “liminf” is defined bylim inf xn= limn→∞(inf{xn, xn+1, · · · }) ∈ [−∞, ∞].60 COUNTABLE MARKOV CHAINS2.2. extinction probability. In the next example, S = {0, 1, 2, 3, · · · }is the population size of some single celled organism. Suppose that, ineach generation, every cell either:(1) dies with probability p0or(2) divides into k cells with probability pk.Since these are all the possibilities we have:po+ p1+ p2+ · · · = 1.We have a countable Markov chain whereXn= # cells in generation n.2.2.1. branching process. This is an example of a branching process. Toexplain what this means I drew a picture:•X0= 1 X1= 2••X2= 3O••Each cell, for example the cell indicated with a circle, starts a branchwhich looks just like the whole thing. In other words, we have a “frac-tal” in which every piece looks like the whole. This is a branchingprocess.2.2.2. question. The question is: What is the extinction probability?This isa := P(lim inf Xn= 0 | X0= 1).This is the probability of extinction when we start with one cell. Butwhat if we start with more than one?Lemma 2.2. P(lim inf Xn= 0 | X0= k) = ak.Proof. I drew a picture to indicate that for each of the k starting cells,there is a probability a that that cell and all of its descendants willdie out. Assuming independence, the probability that this will happento each of k cells is aksince we multiply probabilities of independentevents. MATH 56A SPRING 2008 STOCHASTIC PROCESSES 61With this lemma we get a formula for the extinction probability:a = P(X∞= 0 | X0= 1)=∞Xk=0P(X∞= 0 | X1= k)| {z }akP(X1= k | X0= 1)| {z }pka =∞Xk=0akpk.This is, by definition, the generating function of the sequence pk.2.2.3. generating functions. The definition of the generating functionφ(s) isφ(s) :=∞Xk=0skpk= p0+ sp1+ s2p2+ s3p3+ · · ·So, the extinction probability a is the solution of the equation:a = φ(a)We looked at the general properties of the generating function andfed in the specifics of our example. First,φ(0) = p0> 0.We are going to assume that p0> 0. Otherwise, every cell is immortaland there will be no chance of extinction. Next,φ(1) =Xpk= p0+ p1+ p2+ · · · = 1.This is because the probabilities add to 1.φ0(s) =∞Xk=1ksk−1pk= p1+ 2sp2+ 3s2p3+ · · ·φ0(1) =Xkpk= E(K) = µ.This is, by definition, the expected value µ = E(K) of the randomvariable K which is the number of offspring of any one cell. It is stan-dard probability notation that the lower case letters are the particularvalues of upper case letters.We also need the second derivative:φ00(s) =∞Xk=2k(k − 1)sk−2pk= 2p2+ 6sp3+ 12s2p4+ · · ·This function is ≥ 0 for all s ≥ 0 andφ00(s) > 062 COUNTABLE MARKOV CHAINSmeaning the function is concave up for all s > 0 if at least one ofthe numbers p2, p3, · · · is positive. For example, this must be true ifE(K) = 1 since K is sometimes zero: p0= P(K = 0) > 0, it must alsosometimes be greater than 1 to have an average of 1.Lemma 2.3. a is the smallest positive real number so that a = φ(a).I will give the proof later. First, I want to show what this means.Case 1. Suppose that µ > 1. In that case, the slope of the curve y =φ(s) at s = 1 is greater than 1. Since the y-intercept is φ(0) = p0> 0,φ(1) = 1 and φ is concave up, the graph must look like this:The curves y = φ(s) and y = s must meet at some point s = a = φ(a)where 0 < a < 1. So, there is a nonzero probability of extinctionand a nonzero probability of indefinite survival. It could go either way.Someone once told me “May you have a thousand sons.” Even if peoplehave, on the average, a thousand children, if there is a chance of deaththen there is a chance of extinction of the species.Case 2. Suppose µ < 1. In this case the slope is less than 1 at s = 1and the graph looks like this:So, a = 1. This implies thatP(extinction | X0= k) = ak= 1.MATH