MATH 56A SPRING 2008 STOCHASTIC PROCESSES 712.4. Transient, recurrent and null recurrent. [Guest lecture byAlan Haynes. Notes by Connie, Peter, Sam, Xioudi, Zach.] AlanHaynes reviewed the difference between transient and recurrent anddefined the notion of null recurrence.2.4.1. transient and recurrent. Suppose that {Xn} is an irreducibleaperiodic Markov chain. Fix z ∈ S and define the function α : S →[0, 1] byα(x) = P(Xn= z for some n ≥ 0 |X0= x}Facts:(1) α(x) ∈ [0, 1](2) α(z) = 1(3) If x $= z, thenα(x) =!y∈Sp(x, y)α(y)⇒ α is a right eigenvector of P = (p(x, y))x,y∈S(the probabilitytransition matrix).There are two possibilities: Xnis either transient or recur-rent.(4) Transient ⇔ the probability of returning to z (or any otherpoint) an infinite number of times is 0.⇔ α(x) < 1 for some x ∈ S⇔ infx∈Sα(x) = 0(5) Recurrent ⇔ the probability of returning to every point an in-finite number of times is 1.⇔ α(x) = 1 ∀x ∈ SWhy is it true that α (x) < 1 implies inf α(x) = 0? The proof is bycontradiction. Suppose not. Then there is some " > 0 so that α(x) ≥ "for all x ∈ S. This implies that, no matter where you are, you havea probability of at least " of returning to z. So, with probability one,you must return to z an infinite numb er of times making the chainrecurrent.Theorem 2.7. If "α : S → [0, 1] satisfies"α(x) =!y∈Sp(x, y)"α(y) for all x ∈ S\zthen α (x) ≤ "α(x) for all x ∈ S.72 COUNTABLE MARKOV CHAINSTo show that a Markov chain is transient, you should find a solution"α(x) of the equation so that "α(x) < 1 at some point x ∈ S.Example: Take the random walk on {0, 1, 2, ···} with partially re-flecting wall at 0. This means that, at 0, you either stay at 0 or go to1. Choose some p in the open interval (0, 1) and let q = 1 −p. If n ≥ 1,the transition probabilities are given byp(n, n − 1) = p (going to the left)p(n, n + 1) = q (going to the right)At n = 0 you can’t go left. The probabilities are given byp(0, 0) = p, p(0, 1) = q.Question: Is this transient or recurrent? We need to choose a point zand use the theorem.Choose z = 0. Then find a function "α that satisfies the equation inthe theorem:"α(n) =!m∈Np(n, m)"α(m) for n ≥ 1Since p(n, m) = 0 unless m = n + 1, n − 1, we can simplify this to:"α(n) = p"α(n − 1) + q"α(n + 1)This is a homogeneous linear difference equation with constant coeffi-cients. So,"α(n) = C1rn+ C2snwhere C1, C2∈ R and r, s are the roots of the equationx = p + qx2If you use the quadratic equation you get:r =1 −√1 − 4pq2q, s =1 +√1 − 4pq2qIf you use the fact that p + q = 1 you get the solution:r, s =pq, 1 (The smaller number is r.)To get this you need to factor the equation:x = (p + q)x = p + qx2p(x − 1) = q(x2− x)This is true if x = 1 or, when x $= 1 you can factor out the term x − 1to get:p = qx.MATH 56A SPRING 2008 STOCHASTIC PROCESSES 73Since the actual probability is α(n) ≤ "α(n), we want "α(n) < 1. Thishappens when one of the roots r, s is less than 1.Case 1: p =12. Then q =12. The roots are r = s = 1. Since"α(0) = C1r0+ C2s0= 1we have"α(n) = C1rn+ C2sn= C1+ C2= 1.So, the only solution of the equation is "α(n) = 1. This implies thechain is recurrent. (In fact, it is null recurrent as explained below.)Case 2: p <12. Then p =12− ", q =12+ ", pq =14− "2, 1 − 4pq = 4"2,r =1 −√1 − 4pq2q=1 − 2"1 + 2"=pq< 1.Then, one of the solutions is:"α(n) = rn→ 0 as n → ∞This implies that the chain is transient.Note: We only need one "α(n) < 1 to prove transience.Case 3: p >12. Then p =12+ ", q =12− ", pq =14− "2,r =1 −√1 − 4pq2q=1 − 2"1 − 2"= 1.The other solution iss =1 +√1 − 4pq2q=1 + 2"1 − 2"=pq> 1.This implies the chain is recurrent. (In fact, it is positive recurrent.)74 COUNTABLE MARKOV CHAINS2.4.2. null recurrence.Definition 2.8. An irreducible aperiodic chain {Xn} is called nullrecurrent if it is recurrent andlimn→∞pn(x, y) = 0 ∀x, y ∈ S.If {Xn} is recurrent but not null recurrent then it is called positiverecurrent.How do you tell the difference?Theorem 2.9. If {Xn} is positive recurrent then, for every x, y ∈ S,limn→∞pn(x, y) = π(y) > 0where π : S → [0, 1] is the invariant probability distribution.Recall the definition of invariant distribution:(1) (probability distribution)#x∈Sπ(x) = 1(2) (invariant) πP = π :π(y) =!x∈Sπ(x)p(x, y).I.e., π is a left eigenvector of P .Corollary 2.10. {Xn} is positive recurrent if and only if it has aninvariant
View Full Document
Unlocking...