Steven R. Dunbar
Department of Mathematics
203 Avery Hall
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

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________ ### Section Starter Question

__________________________________________________________________________ ### Key Concepts

1. A random walk is recurrent if the walk almost surely returns to the origin inﬁnitely 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 ﬁnitely many times.
2. Every random walk is either recurrent or transient.
3. The random walk on the line is transient if $p\ne 1∕2$. If $p=1∕2$ then the random walk on the line is recurrent.
4. The walk is recurrent if and only if
$\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]=+\infty .$

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 ﬁnitely many times.
6. If the random walk is transient, then almost surely $\underset{n\to \infty }{lim}|{T}_{n}|=+\infty$.
7. If the random walk is recurrent, then almost surely the random walk reaches every point in $S$ inﬁnitely many times.

__________________________________________________________________________ ### Vocabulary

1. In a nearest neighbor random walk on the line, at time $n$ the walker takes a step to the right to ${T}_{n}+1$ with probability $p$ and takes a step to the left to ${T}_{n}-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 inﬁnitely many times.
3. A random walk is transient if the walk almost surely returns to the origin only ﬁnitely many times.
4. A random walk is centered if $𝔼\left[{Y}_{i}\right]=0$.

__________________________________________________________________________ ### Mathematical Ideas

#### Deﬁnitions

Imagine an individual on a number line, starting at some position ${T}_{0}$. In a nearest neighbor random walk on the line at time $n$, $n\ge 0$ the walker takes a step to the right to ${T}_{n}+1$ with probability $p$ and takes a step to the left to ${T}_{n}-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 inﬁnite sequences of 0’s and 1’s, $\Omega ={\left\{0,1\right\}}^{\infty }$. Let

${Y}_{k}\left(\omega \right)=2{\omega }_{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 $\omega$ is usually suppressed) indicates right or left at step $k$. Then as usual,

${T}_{n}=\sum _{k=1}^{n}{Y}_{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 inﬁnitely many times. That is, the walk is recurrent if the event is an almost sure event. A random walk is transient if is a negligible event, alternatively, if the walk almost surely returns to the origin only ﬁnitely many times.

Note that in principle it is possible that for a random walk deﬁned by some step probability the event could have probability $P$ where $0. 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.

A random walk is centered if $𝔼\left[{Y}_{i}\right]=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

${T}_{n}=\sum _{k=1}^{n}{Y}_{i}.$

The following are immediate consequences of previous theorems:

1. If $p>1∕2$ (respectively $p<1∕2$), the Strong Law of Large Numbers implies that ${T}_{n}$ almost surely approaches $+\infty$ (respectively $-\infty$). Thus, the random walk on the line is transient if $p\ne 1∕2$. Equivalently, if the walk is not centered, the walk is transient.
2. If $p=1∕2$ the Law of the Iterated Logarithm implies that $limsup{T}_{n}=\infty$ and $liminf{T}_{n}=-\infty$. 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 $ℙ\left[{Y}_{n}=-3\right]=2∕5$ and $ℙ\left[{Y}_{n}=2\right]=3∕5$. This is a centered random walk. Furthermore, the Law of the Iterated Logarithm implies that $limsup{T}_{n}=\infty$ and $liminf{T}_{n}=-\infty$. 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

Deﬁnition. For $m,s,t\in ℕ$ with $s\le t$, let ${A}_{s,t}^{m}$ 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,

Lemma 1. For every $m$ and $t$

$ℙ\left[{A}_{1,t}^{m}\right]\le {\left(ℙ\left[{A}_{1,t}^{1}\right]\right)}^{m}.$

Remark. The left side of this lemma expresses the probability of at least $m$ zeroes anywhere in the interval $\left[1,t\right]$. The right side of this lemma expresses the $m$th power of the probability of at least $1$ zero in $\left[1,t\right]$. 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 $ℙ\left[{A}_{1,t}^{m}\right]=0$ if $m>t$.
2. If $m=1$, the statement of the lemma $ℙ\left[{A}_{s,t}^{1}\right]\le {\left(ℙ\left[{A}_{1,t}^{1}\right]\right)}^{1}$ is clear. The proof now proceeds by induction with this step as the base case.
3. Let $m=2$. Consider the ﬁrst two returns to the origin and write the event ${A}_{1,t}^{2}$ as a ﬁnite union of pairwise disjoint events

4. Then

5. Since is independent of ,

6. Note that

7. Then

8. Thus

9. Notice that

10. Therefore $ℙ\left[{A}_{1,t}^{2}\right]\le {\left(ℙ\left[{A}_{1,t}^{1}\right]\right)}^{2}$.
11. The induction step for $m>2$ is similar.

Lemma 2. For every $m$ and $t$

${\left(ℙ\left[{A}_{1,t}^{1}\right]\right)}^{m}\le ℙ\left[{A}_{1,mt}^{m}\right].$

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

Proof. The proof is again by induction.

1. Start from (1) and rewrite it as

2. Then

3. Change variables $l=k-j$

4. This simpliﬁes to
$\left(ℙ\left[{A}_{1,2t}^{2}\right]\right)\ge {\left(ℙ\left[{A}_{1,t}^{1}\right]\right)}^{2}.$

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

Theorem 3. The walk is recurrent, that is,

if and only if

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 deﬁnition of .
($⇐$)
1. Let $m\in ℕ$, and let ${A}_{1,\infty }^{m}$ be the event that the sequence ${\left({T}_{n}\right)}_{n\ge 1}$ has at least $m$ zeroes. For each $t>0$, ${A}_{1,\infty }^{m}\supseteq {A}_{1,mt}^{m}$.
2. By Lemma 2
${\left(ℙ\left[{A}_{1,t}^{1}\right]\right)}^{m}\le ℙ\left[{A}_{1,mt}^{m}\right]$

3. Now assume the condition

Then $\underset{t\to \infty }{lim}ℙ\left[{A}_{1,t}^{1}\right]=1$, so the event ${A}_{1,\infty }^{m}$ contains an event with probability arbitrarily close to $1$. Therefore ${A}_{1,\infty }^{m}$ is an almost sure event.

4. Then event that the sequence ${\left({T}_{n}\right)}_{n\ge 1}$ has inﬁnitely many zeroes is the intersection of the sets ${A}_{1,\infty }^{m}$ for all $m\in ℕ$. Since the countable intersection of almost sure events is almost sure, the sequence ${\left({T}_{n}\right)}_{n\ge 1}$ almost surely has inﬁnitely many zeroes. Thus the random walk is recurrent.

Theorem 4.

1. If
$\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]<+\infty .$

then

that is, the walk is transient.

2. If
$\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]=+\infty .$

then

that is, the walk is recurrent.

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 ${T}_{n}$ are not independent.

Proof.

1.
If the series $\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]$ converges, then the event is a negligible event by the ﬁrst Borel-Cantelli Lemma.
2.
1. The sequence $ℙ\left[{A}_{1,n}^{1}\right]$ for $n\ge 1$ is increasing and bounded by $1$, so the limit exists: $\rho =\underset{n\to \infty }{lim}ℙ\left[{A}_{1,n}^{1}\right]$. The condition 2 to prove is $\rho =1$.
2. $\sum _{k=1}^{n}ℙ\left[{T}_{k}=0\right]=𝔼\left[\sum _{k=1}^{n}{\chi }_{\left[{T}_{k}=0\right]}\right]$

3. by summation by parts, or just by expansion.

4. Then by Lemma 1
$\sum _{k=1}^{n}ℙ\left[{T}_{k}=0\right]\le \sum _{j=1}^{n}{\left(ℙ\left[{A}_{1,n}^{1}\right]\right)}^{j}\le \sum _{j=1}^{n}{\rho }^{j}.$

5. Therefore $\sum _{k=1}^{\infty }ℙ\left[{T}_{k}=0\right]=+\infty$ implies $\rho =1$.
6. Then $\underset{n\to \infty }{lim}{A}_{1,n}^{1}=1$ by Theorem 3.

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

Proof. Since the series of non-negative terms$\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]$ must either converge or diverge, then respectively , i.e. the walk is transient or , i.e. the walk is recurrent. □

Lemma 5.

1. The random walk ${T}_{n}$ on $ℤ$ satisﬁes
$\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=x\right]\le 1+\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]$

for every $x\in ℤ$

2. $\sum _{n=1}^{\infty }ℙ\left[|{T}_{n}|\le K\right]\le \left(2K+1\right)\left(1+\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]\right)$

for every $K>0$.

Proof.

1.
1. Decompose the event $\left[{T}_{n}=x\right]$ into a union of pairwise disjoint events based on the ﬁrst time $k$ the random walk reaches the point $x$:

2. Then by independence and invariance of probability under shifting

3. Then

using the deﬁnition ${T}_{0}=0$. Note that the change of order of summation is justiﬁed since all terms are non-negative.

4. Since the events $\left[\left[{T}_{i}\ne x,1\le i and $\left[{T}_{k}=x\right]$ are pairwise disjoint over $k$, the sum of their probabilities is at most $1$. This ﬁnishes the proof of part 1.
2.
This follows at once from
$ℙ\left[|{T}_{n}|\le K\right]=\sum _{x\in ℤ,|x|\le K}ℙ\left[{T}_{n}=x\right]$

along with the fact that $|\left\{x\in ℤ,|x|\le K\right\}|=2K+1$.

Deﬁnition. 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 ﬁnitely many times.
2. If the random walk is transient, then almost surely $\underset{n\to \infty }{lim}|{T}_{n}|=+\infty$.
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$ inﬁnitely many times.

Proof.

1.
1. Let $x\in S$ be given, and choose $m$ so that $|x|\le K$.
2. Suppose the random walk is transient. Then Theorem 4 implies that $\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]$ converges.
3. Then by Lemma 5, $\sum _{n=1}^{\infty }ℙ\left[|{T}_{n}|\le K\right]$ converges for any $K>0$.
4. Then by the Borel-Cantelli Lemma, every point of $S$ is almost surely only reached ﬁnitely many times.
2.
From the previous part, if the random walk is transient, then every point $S$ is almost surely reached only ﬁnitely many times. It follows at once that almost surely $\underset{n\to \infty }{lim}|{T}_{n}|=+\infty$.
3.
1. Suppose the random walk ${\left({T}_{n}\right)}_{n=1}^{\infty }$ is recurrent.
2. Let $x\in S$ and ﬁx a $k\ge 0$ such that $ℙ\left[{T}_{k}=x\right]>0$.
3. Then almost surely, there is an $n>k$ such that ${T}_{n}=0$.
4. Since an almost sure event and a ﬁnite type event with positive probability cannot be disjoint, there is an $\omega$ such that ${T}_{k}\left(\omega \right)=x$ and ${T}_{n}\left(\omega \right)=0$ with $k.
5. Then $-x\in 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 inﬁnitely 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 inﬁnite 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$ inﬁnitely many times.
2. By step 5 in the proof of Theorem 4, $\rho =\underset{n\to \infty }{lim}ℙ\left[{A}_{1,n}^{1}\right]=1$ and therefore $\underset{n\to \infty }{lim}ℙ\left[{A}_{1,t}^{1}\right]=1$.
3. Then by Lemma 2, $\underset{t\to \infty }{lim}ℙ\left[{A}_{1,mt}^{m}\right]=1$ for any $m>0$.
4. Then $\underset{t\to \infty }{lim}ℙ\left[{A}_{1,t}^{m}\right]=1$.
5. If $m$, $s$, $t$ are positive integers, then ${A}_{s,t}^{m}\supseteq {A}_{1,t}^{m+s}$, so $\underset{t\to \infty }{lim}ℙ\left[{A}_{s,t}^{m}\right]=1$.
6. Let $x\in S$ and $𝜖>0$. Fix $k$ so that $ℙ\left[{T}_{k}=x\right]>0$. Set $\delta =1-ℙ\left[{T}_{k}=x\right]<1$. Deﬁne a sequence ${n}_{j}$ for $j\ge 0$ by the recurrence $\begin{array}{llll}\hfill {n}_{0}& =1,\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {n}_{j}-{n}_{j-1}& >k,\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill ℙ\left[{A}_{{n}_{j-1},{n}_{j}-k}^{1}\right]& >1-{2}^{-j}𝜖.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$
7. For $j\ge 1$, let ${B}_{j}$ be the event the random walk returns to the origin at least once between steps ${n}_{j-1}$ and ${n}_{j}-k$ and does not visit $x$ between steps ${n}_{j-1}$ and ${n}_{j}$. In symbols
${B}_{j}={A}_{{n}_{j-1},{n}_{j}-k}^{1}\cap \left[{T}_{n}\ne x,{n}_{j-1}\le n\le {n}_{j}\right]$

8. Let $J$ and $K$ be two positive integers such that $0. The next step is to ﬁnd an upper bound for the probability of the event that the random walk does not reach $x$ between steps ${n}_{J-1}$ and ${n}_{K}$. Using Problems 5 and 6 below:
$ℙ\left[{T}_{n}\ne x,{n}_{J-1}\le n\le {n}_{K}\right]\le ℙ\left[\bigcup _{j=J}^{K}{\left({A}_{{n}_{j-1},{n}_{j}-k}^{1}\right)}^{C}\right]+ℙ\left[\bigcap _{j=J}^{K}{B}_{j}\right].$

9. Furthermore,
$ℙ\left[\bigcup _{j=J}^{K}{\left({A}_{{n}_{j-1},{n}_{j}-k}^{1}\right)}^{C}\right]\le \sum _{j=J}^{K}{2}^{-j}𝜖\le {2}^{1-J}𝜖.$

10. Let ${\ell }_{j}$ be a positive integer allowed to vary between ${n}_{j-1}$ and ${n}_{j}-k$. (Pay careful attention to distinction of ${l}_{j}$ and ${\ell }_{j}$ in subscripts. In fact, pay careful attention to all subscripts.) If event ${B}_{j}$ occurs then there is a unique ${\ell }_{j}$ such that
$\left[{T}_{i}\ne 0,{n}_{j-1}\le l<{\ell }_{j}\right],\phantom{\rule{1em}{0ex}}{T}_{{\ell }_{j}}=0,\phantom{\rule{1em}{0ex}}{T}_{{\ell }_{j}+k}\ne x.$

That is, ${\ell }_{j}$ is the ﬁrst zero of ${T}_{n}$ on ${n}_{j-1}\le i\le {n}_{j}-k$. Note that the event in the display above is a superset of ${B}_{j}$.

11. Then
$ℙ\left[\bigcap _{j=J}^{K}{B}_{j}\right]\le \sum _{{l}_{J},\dots {l}_{K}}ℙ\left[\bigcap _{j=J}^{K}\left({\left({A}_{{n}_{j-1},{n}_{j}-k}^{1}\right)}^{C}\cap \left[{T}_{{\ell }_{j}}=0\right]\cap \left[{T}_{{\ell }_{j}+k}\ne x\right]\right)\right].$

12. Since the increment ${T}_{{l}_{K}+k}-{T}_{{l}_{K}}$ is independent of the random walk from ${T}_{{l}_{K}-1}$ $\begin{array}{c}ℙ\left[\bigcap _{j=J}^{K}\left({\left({A}_{{n}_{j-1},{l}_{j}-1}^{1}\right)}^{C}\cap \left[{T}_{{\ell }_{j}}=0\right]\cap \left[{T}_{{\ell }_{j}+k}\ne x\right]\right)\right]=\\ ℙ\left[\bigcap _{j=J}^{K-1}\left({\left({A}_{{n}_{j-1},{l}_{j}-1}^{1}\right)}^{C}\cap \left[{T}_{{\ell }_{j}}=0\right]\cap \left[{T}_{{\ell }_{j}+k}\ne x\right]\right)\right\\ \cap \left({\left({A}_{{n}_{K-1},{l}_{K}-1}^{1}\right)}^{C}\right)\cap \left[{T}_{{\ell }_{j}}=0\right]]\\ ×ℙ\left[{T}_{{l}_{K}+k}-{T}_{{l}_{K}}\ne x\right].\end{array}$

13. The invariance property implies $\begin{array}{c}\sum _{{\ell }_{J},\dots {\ell }_{K}}ℙ\left[\bigcap _{j=J}^{K}\left({\left({A}_{{n}_{j-1},{l}_{j}-1}^{1}\right)}^{C}\cap \left[{T}_{{\ell }_{j}}=0\right]\cap \left[{T}_{{\ell }_{j}+k}\ne x\right]\right)\right]\le \\ \delta \sum _{{\ell }_{J},\dots {\ell }_{K}}ℙ\left[\bigcap _{j=J}^{K-1}\left({\left({A}_{{n}_{j-1},{l}_{j}-1}^{1}\right)}^{C}\cap \left[{T}_{{\ell }_{j}}=0\right]\cap \left[{T}_{{\ell }_{j}+k}\ne x\right]\right)\right].\end{array}$

14. Therefore, by recursion on the sum $\begin{array}{c}\sum _{{\ell }_{J},\dots {\ell }_{K}}ℙ\left[\bigcap _{j=J}^{K}\left({\left({A}_{{n}_{j-1},{l}_{j}-1}^{1}\right)}^{C}\cap \left[{T}_{{\ell }_{j}}=0\right]\cap \left[{T}_{{\ell }_{j}+k}\ne x\right]\right)\right]\le \\ {\delta }^{K-J+1}.\end{array}$

15. Combining all the inequalities
$ℙ\left[{T}_{n}\ne x,{n}_{J-1}\le n\le {n}_{K}\right]\le {2}^{1-J}𝜖+{\delta }^{K-J+1}.$

16. For each $J>0$, ﬁx $K>0$, depending on $J$, so $K\left(J\right)$ such that ${\delta }^{K-J+1}\le {2}^{1-J}𝜖$.
17. The event $E\subset \Omega$ such that $M\left(\omega \right)=x$ for only ﬁnitely many $n$ is in the union
$\bigcup _{J>0}\left[{T}_{n}\ne x,{n}_{J-1}\le n\le {n}_{K\left(J\right)}\right].$

18. By the choices above
$\sum _{J>0}ℙ\left[{T}_{n}\ne x,{n}_{J-1}\le n\le {n}_{K\left(J\right)}\right]<4𝜖.$

This shows that $E$ is a negligible event.

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

#### Recurrence in Centered Random Walks

One more deﬁnition: A random walk is centered if $𝔼\left[{Y}_{i}\right]=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
$\underset{n\to \infty }{lim}\frac{{T}_{n}}{n}=𝔼\left[{Y}_{1}\right]$

almost surely. If the walk is not centered, so that $𝔼\left[{Y}_{1}\right]\ne 0$, then $\underset{n\to \infty }{lim}|{T}_{n}|=+\infty$, 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+\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]\ge \frac{1}{\left(2K+1\right)}\sum _{n=1}^{\infty }ℙ\left[|{T}_{n}|\le K\right].$

Then for any positive integer $a$,

$1+\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]\ge \frac{1}{\left(2K+1\right)}\sum _{n=1}^{ma}ℙ\left[|{T}_{n}|\le K\right].$

and since $n\le Ka$, or $K\ge n∕a$

$1+\sum _{n=1}^{ma}ℙ\left[{T}_{n}=0\right]\ge \frac{1}{\left(2K+1\right)}\sum _{n=1}^{\infty }ℙ\left[|{T}_{n}|\le \frac{n}{a}\right].$

The generalized Weak Law of Large Numbers implies that

$\underset{n\to \infty }{lim}ℙ\left[|{T}_{n}|\le \frac{n}{a}\right]=1$

so by an argument from elementary analysis

$\underset{n\to \infty }{lim}\frac{1}{2m+1}\sum _{n=1}^{ma}ℙ\left[|{T}_{n}|\le \frac{n}{a}\right]=\frac{a}{2}.$

Finally this implies that

$1+\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]\ge \frac{a}{2}.$

Since $a$ is an arbitrary integer, this means the series with terms $ℙ\left[{M}_{n}=0\right]$ 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

$ℙ\left[{T}_{2n}=0\right]\sim \frac{1}{\sqrt{n}}$

Then the series $\sum _{n=0}^{\infty }ℙ\left[{T}_{n}=0\right]$ 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

$\underset{n\to \infty }{limsup}{T}_{n}=\infty \phantom{\rule{2em}{0ex}}\underset{n\to \infty }{liminf}{T}_{n}=-\infty$

almost surely. Suppose $|{Y}_{i}|. If $\underset{n\to \infty }{lim}|{T}_{n}|=+\infty$ then given $2M$ there is some $N$ such that $|{T}_{n}|>2M$ for $n\ge N$. Yet there is also ${n}_{1}>N$ such that ${T}_{{n}_{1}}>2M$ and ${n}_{2}>{n}_{1}$ such that ${T}_{{n}_{2}}<-2M$. Because the maximum individual step length is $M$, there must be some ${n}_{3}$ with ${n}_{1}<{n}_{3}<{n}_{2}$ where $-2M<{T}_{{n}_{3}}<2M$. So it is not possible that $\underset{n\to \infty }{lim}|{T}_{n}|=+\infty$. 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

#### Scripts

__________________________________________________________________________ ### Problems to Work for Understanding

1. Show explicitly that

follows from the deﬁnition of

2. Show explicitly that

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 ﬁnitely many times. It follows at once that almost surely $\underset{n\to \infty }{lim}|{T}_{n}|=+\infty$.

4. In Theorem 6, provide a rigorous argument for the ﬁrst steps in the proof of part 3. Speciﬁcally, suppose the random walk ${\left({T}_{n}\right)}_{n=1}^{\infty }$ is recurrent. Let $x\in S$ and show that there is a $k\ge 0$ such that $ℙ\left[{T}_{k}=x\right]>0$.
5. For any sets $E$, $F$, $G$, so that if $E=F\cap G$, then $E\cup {F}^{C}\supseteq G$.
6. Using Problem 5, in step 8 of the proof of part 3. of Theorem 6, provide a rigorous argument for the inequality
$ℙ\left[{T}_{n}\ne x,{n}_{J-1}\le n\le {n}_{K}\right]\le ℙ\left[\bigcup _{j=J}^{K}{\left({A}_{{n}_{j-1},{n}_{j}-k}^{1}\right)}^{C}\right]+ℙ\left[\bigcap _{j=J}^{K}{B}_{j}\right].$

7. Write a simulation program to demonstrate the inequality in Lemma 1: For every $m$ and $t$
$ℙ\left[{A}_{1,t}^{m}\right]\le {\left(ℙ\left[{A}_{1,t}^{1}\right]\right)}^{m}.$

8. Write a simulation program to demonstrate the inequality in Lemma 2:
${\left(ℙ\left[{A}_{1,t}^{1}\right]\right)}^{m}\le ℙ\left[{A}_{1,mt}^{m}\right].$

9. Write a simulation program to demonstrate the inequality in Lemma 1:
$\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=x\right]\le 1+\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]$

for every $x\in {ℤ}^{N}$

10. Write a simulation program to demonstrate the inequality in Lemma 2:
$\sum _{n=1}^{\infty }ℙ\left[|{T}_{n}|\le m\right]\le \left(2m+1\right)\left(1+\sum _{n=1}^{\infty }ℙ\left[{T}_{n}=0\right]\right)$

for every $m>0$.

__________________________________________________________________________ ### References

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

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

__________________________________________________________________________ __________________________________________________________________________

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 eﬀort 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 reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial positions or policies of my employer.

Information on this website is subject to change without notice.