Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar

__________________________________________________________________________

Recurrence

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________

Rating

Rating

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

Section Starter Question

Section Starter Question

__________________________________________________________________________

Key Concepts

Key Concepts

  1. A random walk is recurrent if the walk almost surely returns to the origin infinitely many times. A random walk is transient if returning to the origin is a negligible event, alternatively, if the walk almost surely returns to the origin only finitely many times.
  2. Every random walk is either recurrent or transient.
  3. The random walk on the line is transient if p12. If p = 12 then the random walk on the line is recurrent.
  4. The walk is recurrent if and only if
    n=1 T n = 0 = +.

  5. Let S be the set of points attainable by the random walk. If the random walk is transient, then almost surely every point of S is reached only finitely many times.
  6. If the random walk is transient, then almost surely lim n|Tn| = +.
  7. If the random walk is recurrent, then almost surely the random walk reaches every point in S infinitely many times.

__________________________________________________________________________

Vocabulary

Vocabulary

  1. In a nearest neighbor random walk on the line, at time n the walker takes a step to the right to Tn + 1 with probability p and takes a step to the left to Tn 1 with probability q = 1 p and continues this random process.
  2. A random walk is recurrent if the walk almost surely returns to the origin infinitely many times.
  3. A random walk is transient if the walk almost surely returns to the origin only finitely many times.
  4. A random walk is centered if 𝔼 Y i = 0.

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

Definitions

Imagine an individual on a number line, starting at some position T0. In a nearest neighbor random walk on the line at time n, n 0 the walker takes a step to the right to Tn + 1 with probability p and takes a step to the left to Tn 1 with probability q = 1 p and continues this random process. Then instead of the total fortune at any time, consider the geometric position on the line at any time.

A probability model for the random walk is the set of all infinite sequences of 0’s and 1’s, Ω = {0, 1}. Let

Y k(ω) = 2ωk 1,

then Y k is a random variable taking on the value +1 with probability p or 1 with probability 1 p. Y k (the dependence on the sequence ω is usually suppressed) indicates right or left at step k. Then as usual,

Tn = k=1nY i

is a random variable indicating the position on the line.

A random walk is recurrent if the walk almost surely returns to the origin infinitely many times. That is, the walk is recurrent if the event [Tn = 0] i.o. is an almost sure event. A random walk is transient if [Tn = 0] i.o. is a negligible event, alternatively, if the walk almost surely returns to the origin only finitely many times.

Note that in principle it is possible that for a random walk defined by some step probability the event [Tn = 0] i.o. could have probability P where 0 < P < 1. In this possibility the random walk would be neither recurrent nor transient. However, Corollary 1 below shows that all random walks are either recurrent or transient, so the two categories are mutually exclusive.

One more definition: A random walk is centered if 𝔼 Y i = 0.

The theorems in this section can be generalized to other settings including random walks based on more general step distributions, including steps with continuous distributions, and to Markov chains.

Random Walk on the Line

Let Y k be a random variable taking on the value +1 with probability p or 1 with probability 1 p. Y k indicates right or left at step k and

Tn = k=1nY i.

The following are immediate consequences of previous theorems:

  1. If p > 12 (respectively p < 12), the Strong Law of Large Numbers implies that Tn almost surely approaches + (respectively ). Thus, the random walk on the line is transient if p12. Equivalently, if the walk is not centered, the walk is transient.
  2. If p = 12 the Law of the Iterated Logarithm implies that limsup Tn = and liminf Tn = . Since the length of each step is 1, then the random walk on the line is recurrent.
  3. However, consider the random walk on the line with Y n = 3 = 25 and Y n = 2 = 35. This is a centered random walk. Furthermore, the Law of the Iterated Logarithm implies that limsup Tn = and liminf Tn = . However, because the steps are not unit length, the walk may “step over” the origin, so previous theorems alone are not enough to imply the walk is recurrent.

General Results

Definition. For m,s,t with s t, let As,tm be the event consisting of the random walks that return to the starting point at least m times between steps s and t. That is,

ω As,tm if and only if |{n : s n t,T n(ω) = 0}| m.

Lemma 1. For every m and t

A1,tm ( A 1,t1)m.

Remark. The left side of this lemma expresses the probability of at least m zeroes anywhere in the interval [1,t]. The right side of this lemma expresses the mth power of the probability of at least 1 zero in [1,t]. The inequality that the left side is less than the right side is not obvious, so the lemma has a substantial conclusion.

Proof.

  1. Clearly A1,tm = 0 if m > t.
  2. If m = 1, the statement of the lemma As,t1 ( A 1,t1)1 is clear. The proof now proceeds by induction with this step as the base case.
  3. Let m = 2. Consider the first two returns to the origin and write the event A1,t2 as a finite union of pairwise disjoint events A1,t2 = 1j<kt [Ti0, 1 i < j] and [Tj = 0]  and [Ti0,j < i < k] and [Tk = 0] .

  4. Then A1,t2 = 1j<kt [Ti0, 1 i < j] and [Tj = 0]  and [Ti Tj0,j < i < k]and [Tk Tj = 0] .

  5. Since [Ti0, 1 i < j] and [Tj = 0] is independent of [Ti Tj0,j < i < k] and [Tk Tj = 0], A1,t2 = 1j<kt [Ti0, 1 i < j] and [Tj = 0] × [Ti Tj0,j < i < k] and [Tk Tj = 0] .

  6. Note that [Ti Tj0,j < i < k] and [Tk Tj = 0] = [Tij0,j < i < k]and [Tkj = 0] .

  7. Then A1,t2 = 1j<kt [Ti0, 1 i < j] and [Tj = 0] × [Tij0, 1 i < k j] and [Tkj = 0] .(1)

  8. Thus A1,t2 j=1t l=1t [T i0, 1 i < j] and [Tj = 0] × [Ti0, 1 i < l] and [Tl = 0] .

  9. Notice that
    A1,t1 j=1t [T i0, 1 i < j] and [Tj = 0] .

  10. Therefore A1,t2 ( A 1,t1)2.
  11. The induction step for m > 2 is similar.

Lemma 2. For every m and t

( A1,t1)m A 1,mtm .

Remark. This lemma expresses the clear fact that the probability of at least m zeroes anywhere in the interval [1,mt] is greater than the probability of at least 1 zero in [1,t], at least a second zero in [t + 1, 2t] and so on. The proof formalizes this.

Proof. The proof is again by induction.

  1. Start from (1) and rewrite it as A1,2t2 = 1j<k2t [Ti0, 1 i < j] and [Tj = 0] × [Tij0, 1 i < k j] and [Tkj = 0] .

  2. Then A1,2t2 j=1t k=j+1j+t [T i0, 1 i < j] and [Tj = 0] × [Tij0, 1 i < k j] and [Tkj = 0] .

  3. Change variables l = k j A1,2t2 j=1t [T i0, 1 i < j] and [Tj = 0] × l=1t [T i0, 1 i < l] and [Tl = 0] .

  4. This simplifies to
    ( A1,2t2) ( A 1,t1)2.

  5. The induction step for m > 2 is similar.

Theorem 3. The walk is recurrent, that is,

[Tn = 0] i.o.  = 1,

if and only if

lim n there exists k n such that Tk = 0  = 1.

Remark. The second condition of the theorem implies that the random walk almost surely returns to the origin at least once.

Proof.

()
This follows immediately from the definition of [Tn = 0] i.o.  = 1.
()
  1. Let m , and let A1,m be the event that the sequence (Tn)n1 has at least m zeroes. For each t > 0, A1,m A 1,mtm.
  2. By Lemma 2
    A1,t1 m A 1,mtm

  3. Now assume the condition
    lim n there exists k n such that Tk = 0  = 1.

    Then lim t A1,t1 = 1, so the event A1,m contains an event with probability arbitrarily close to 1. Therefore A1,m is an almost sure event.

  4. Then event that the sequence (Tn)n1 has infinitely many zeroes is the intersection of the sets A1,m for all m . Since the countable intersection of almost sure events is almost sure, the sequence (Tn)n1 almost surely has infinitely many zeroes. Thus the random walk is recurrent.

Theorem 4.

  1. If
    n=1 T n = 0 < +.

    then

    [Tn = 0] i.o.  = 0.

  2. If
    n=1 T n = 0 = +.

    then

    [Tn = 0] i.o.  = 1.

Remark. Note the similarity of Property 2 implying recurrence to the second Borel-Cantelli Lemma. However, the Borel-Cantelli Lemma cannot be directly applied because the random variables Tn are not independent.

Proof.

1.
If the series n=1 T n = 0 converges, then the event [Tn = 0] i.o. is a negligible event by the first Borel-Cantelli Lemma.
2.
  1. The sequence A1,n1 for n 1 is increasing and bounded by 1, so the limit exists: ρ = lim n A1,n1. The condition 2 to prove is ρ = 1.
  2. k=1n T k = 0 = 𝔼 k=1nχ [Tk=0]

  3. k=1n T k = 0 = 𝔼 |[j : 1 j n,Tj = 0]| = j=1nj  (T k)1kn includes j zeroes  = j=1nj A 1,nj A 1,nj+1 = j=1n A 1,nj

    by summation by parts, or just by expansion.

  4. Then by Lemma 1
    k=1n T k = 0 j=1n A 1,n1 j j=1nρj.

  5. Therefore k=1 T k = 0 = + implies ρ = 1.
  6. Then lim nA1,n1 = 1 by Theorem 3.

Corollary 1. Every random walk is either recurrent or transient.

Proof. Since the series of non-negative terms n=1 T n = 0 must either converge or diverge, then respectively [Tn = 0] i.o.  = 0, i.e. the walk is transient or [Tn = 0] i.o.  = 1, i.e. the walk is recurrent. □

Lemma 5.

  1. The random walk Tn on satisfies
    n=1 T n = x 1 + n=1 T n = 0

    for every x

  2. n=1 |T n| m (2m + 1) 1 + n=1 T n = 0

    for every m > 0.

Proof.

1.
  1. Decompose the event [Tn = x] into a union of pairwise disjoint events based on the first time the random walk reaches the point x:
    Ti = x = k=1n [T nx, 1 i < k] and [Tk = x] and [Tn Tk = 0] .

  2. Then by independence and invariance of probability under shifting
    Tn = x = k=1n [T ix, 1 i < k] and [Tk = x] × Tnk = 0 .

  3. Then n=1 T n = x = n=1 k=1n [T ix, 1 i < k] and [Tk = x] × Tnk = 0 = k=1 n=k [T ix, 1 i < k] and [Tk = x] × Tnk = 0 = k=1n [T ix, 1 i < k] and [Tk = x] × n=1 T nk = 0

    using the definition T0 = 0. Note that the change of order of summation is justified since all terms are non-negative.

  4. Since the events [Tix, 1 i < k] and [Tk = x] are pairwise disjoint over k, the sum of their probabilities is at most 1. This finishes the proof of part 1.
2.
This follows at once from
|Tn| m = xN,|x|m Tn = x

along with the fact that |{x N,|x| m}| = 2m + 1.

Definition. Let S be the semigroup generated under addition on the allowed steps in the random walk. Alternatively, the S is the set of points attainable in the random walk.

Theorem 6.

  1. If the random walk is transient, then every point of S is almost surely reached only finitely many times.
  2. If the random walk is transient, then almost surely lim n|Tn| = +.
  3. If the random walk is recurrent, then S is a group.
  4. If the random walk is recurrent, then the random walk almost surely reaches every point in S infinitely many times.

Proof.

1.
  1. Let x S be given, and choose m so that |x| m.
  2. Suppose the random walk is transient. Then Theorem 4 implies that n=1 T n = 0 converges.
  3. Then by Lemma 5, n=1 |T n| m converges for any m > 0.
  4. Then by the Borel-Cantelli Lemma, every point of S is almost surely only reached finitely many times.
2.
From the previous part, if the random walk is transient, then every point S is almost surely reached only finitely many times. It follows at once that almost surely lim n|Tn| = +.
3.
  1. Suppose the random walk (Tn)n=1 is recurrent.
  2. Let x S and fix a k 0 such that Tk = x > 0.
  3. Then almost surely, there is an n > k such that Tn = 0.
  4. Since an almost sure event and a finite type event with positive probability cannot be disjoint, there is an ω such that Tk(ω) = x and Tn(ω) = 0 with k < n.
  5. Then x S and since S is already a semigroup, S is a group.
4
  1. The plan of the proof is as follows:
    1. The random walk almost surely returns to zero infinitely many times.
    2. Each time the walk returns to 0, it is the same as if a new walk, independent of the previous one, were starting.
    3. This gives an infinite sequence of identical, independent experiments, with each one having a positive probability of reaching the point x.
    4. Then the random walk almost surely reaches the point x infinitely many times.
  2. By step 5 in the proof of Theorem 4, ρ = lim n A1,n1 = 1 and therefore lim n A1,t1 = 1.
  3. Then by Lemma 2, lim t A1,mtm = 1 for any m > 0.
  4. Then lim t A1,tm = 1.
  5. If m, s, t are positive integers, then As,tm A 1,tm+s, so lim t As,tm = 1.
  6. Let x S and 𝜖 > 0. Fix k so that Tk = x > 0. Set δ = 1 Tk = x < 1. Define a sequence nj for j 0 by the recurrence n0 = 1, nj nj1 > k, Anj1,njk1 > 1 2j𝜖.
  7. For j 1, let Bj be the event the random walk returns to the origin at least once between steps nj1 and nj k and does not visit x between steps nj1 and nj. In symbols
    Bj = Anj1,njk1 [T nx,nj1 n nj]

  8. Let J and K be two positive integers such that 0 < J < K. The next step is to find an upper bound for the probability of the event that the random walk does not reach x between steps nJ1 and nK. Using Problems 5 and 6 below:
    Tnx,nJ1 n nK j=JK(A nj1,njk1)C + j=JKB j .

  9. Furthermore,
    j=JK(A nj1,njk1)C j=JK2j𝜖 21J𝜖.

  10. Let j be a positive integer allowed to vary between nj1 and nj k. (Pay careful attention to distinction of lj and j in subscripts. In fact, pay careful attention to all subscripts.) If event Bj occurs then there is a unique j such that
    [Ti0,nj1 l < j],Tj = 0,Tj+kx.

    That is, j is the first zero of Tn on nj1 i nj k. Note that the event in the display above is a superset of Bj.

  11. Then
    j=JKB j lJ,lK j=JK (A nj1,njk1)C [T j = 0] [Tj+kx] .

  12. Since the increment TlK+k TlK is independent of the random walk from TlK1 j=JK (A nj1,lj11)C [T j = 0] [Tj+kx] = j=JK1 (A nj1,lj11)C [T j = 0] [Tj+kx] (AnK1,lK11)C [T j = 0] × TlK+k TlKx.

  13. The invariance property implies J,K j=JK (A nj1,lj11)C [T j = 0] [Tj+kx] δ J,K j=JK1 (A nj1,lj11)C [T j = 0] [Tj+kx] .

  14. Therefore, by recursion on the sum J,K j=JK (A nj1,lj11)C [T j = 0] [Tj+kx] δKJ+1.

  15. Combining all the inequalities
    Tnx,nJ1 n nK 21J𝜖 + δKJ+1.

  16. For each J > 0, fix K > 0, depending on J, so K(J) such that δKJ+1 21J𝜖.
  17. The event E Ω such that M(ω) = x for only finitely many n is in the union
    J>0[Tnx,nJ1 n nK(J)].

  18. By the choices above
    J>0 Tnx,nJ1 n nK(J) < 4𝜖.

    This shows that E is a negligible event.

  19. Thus, the random walk almost surely reaches the point x infinitely many times for any x S. Since S is countable, the random walk almost surely reaches every point in S.

Recurrence in Centered Random Walks

One more definition: A random walk is centered if 𝔼 Y i = 0.

Theorem 7. A random walk on is recurrent if and only if it is centered.

Proof.

()
Proof by contrapositive. The Strong Law of Large Numbers implies that
lim nTn n = 𝔼 Y 1

almost surely. If the walk is not centered, so that 𝔼 Y 1 0, then lim n|Tn| = +, so the walk is transient, i.e. not recurrent.

()
The following argument uses the Weak Law of Large Numbers applied to any centered random walk on . Use the reversed form of part 2 of Lemma 5 to see that
1 + n=1 T n = 0 1 2m + 1 n=1 |T n| m.

Then for any positive integer a,

1 + n=1 T n = 0 1 2m + 1 n=1ma |T n| m.

and since n ma, or m na

1 + n=1ma T n = 0 1 2m + 1 n=1 |T n|n a.

The generalized Weak Law of Large Numbers implies that

lim n |Tn|n a = 1

so by an argument from elementary analysis

lim n 1 2m + 1 n=1ma |T n|n a = a 2.

Finally this implies that

1 + n=1 T n = 0 a 2.

Since a is an arbitrary integer, this means the series with terms Mn = 0 diverges and the random walk is recurrent.

Remark. In the Bernoulli trials case that Y i takes only two values, the deMoivre-Laplace Central Limit Theorem implies that

T2n = 0 1 n

Then the series n=0 T n = 0 diverges. Then Theorem 4 implies the recurrence.

Remark. Another possible proof in the Bernoulli trials case that Y i takes only two values uses the Law of the Iterated Logarithm. Recall that this implies that

limsup nTn = liminf nTn =

almost surely. Suppose |Y i| < M. If lim n|Tn| = + then given 2M there is some N such that |Tn| > 2M for n N. Yet there is also n1 > N such that Tn1 > 2M and n2 > n1 such that Tn2 < 2M. Because the maximum individual step length is M, there must be some n3 with n1 < n3 < n2 where 2M < Tn3 < 2M. So it is not possible that lim n|Tn| = +. Then the converse of part 2 of Theorem 6 implies the random walk is recurrent.

Sources

This section is adapted from: E. Lesigne, Heads or Tails: An Introduction to Limit Theorems in Probability, Chapter 13, American Mathematical Society, Student Mathematical Library, Volume 28, 2005. The statement of Theorem 4 is adapted from A Course in Probability Theory, Second Edition by K.L. Chung, Academic Press, 1974, Theorem 8.3.2, page 267.

_______________________________________________________________________________________________

Algorithms, Scripts, Simulations

Algorithms, Scripts, Simulations

Algorithm

Scripts

__________________________________________________________________________

Problems to Work

Problems to Work for Understanding

  1. Show explicitly that
    lim n there exists k n such that Tk = 0  = 1.

    follows from the definition of

    [Tn = 0] i.o.  = 1,

  2. Show explicitly that
    lim n there exists k n such that Tk = 0  = 1.

    implies that the random walk almost surely returns to the origin at least once.

  3. In Theorem 6, provide a rigorous argument for the proof of part 2:

    …if the random walk is transient, then every point S is almost surely reached only finitely many times. It follows at once that almost surely lim n|Tn| = +.

  4. In Theorem 6, provide a rigorous argument for the first steps in the proof of part 3. Specifically, suppose the random walk (Tn)n=1 is recurrent. Let x S and show that there is a k 0 such that Tk = x > 0.
  5. For any sets E, F, G, so that if E = F G, then E FC G.
  6. Using Problem 5, in step 8 of the proof of part 3. of Theorem 6, provide a rigorous argument for the inequality
    Tnx,nJ1 n nK j=JK(A nj1,njk1)C + j=JKB j .

  7. Write a simulation program to demonstrate the inequality in Lemma 1: For every m and t
    A1,tm ( A 1,t1)m.

  8. Write a simulation program to demonstrate the inequality in Lemma 2:
    ( A1,t1)m A 1,mtm .

  9. Write a simulation program to demonstrate the inequality in Lemma 1:
    n=1 T n = x 1 + n=1 T n = 0

    for every x N

  10. Write a simulation program to demonstrate the inequality in Lemma 2:
    n=1 |T n| m (2m + 1) 1 + n=1 T n = 0

    for every m > 0.

__________________________________________________________________________

Books

Reading Suggestion:

References

[1]   Kai Lai Chung. A Course in Probability Theory. Academic Press, 1974.

[2]   Emmanuel Lesigne. Heads or Tails: An Introduction to Limit Theorems in Probability, volume 28 of Student Mathematical Library. American Mathematical Society, 2005.

__________________________________________________________________________

Links

Outside Readings and Links:

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable effort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reflects the thoughts, interests and opinions of its author. They do not explicitly represent official positions or policies of my employer.

Information on this website is subject to change without notice.

Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1

Email to Steve Dunbar, sdunbar1 at unl dot edu

Last modified: Processed from LATEX source on February 6, 2018