3 Recurrence and transience

Let \(X= \big(X(t)\big)_{t \in \mathbb {N}}\) be a random walk on a graph with vertex set \(\mathbb {G}\), starting from \(x_0 \in \mathbb {G}\).

3.1 Basic definition

Definition 3.1

The random walk \(X= \big(X(t)\big)_{t \in \mathbb {N}}\) is said to be recurrent if

\begin{align*} \mathsf{P}\Big[ X(t) = x_0 \text{ for infinitely many } t \in \mathbb {N}\Big] \, = \, 1 \end{align*}

and transient if

\begin{align*} \mathsf{P}\Big[ X(t) = x_0 \text{ for infinitely many } t \in \mathbb {N}\Big] \, = \, 0 . \end{align*}

3.2 Equivalent conditions

Usually random walks are taken to be Markov processes (Markovian random walks). Then one can use alternative formulations of recurrence and transience.

Definition 3.2

Denote by \(L = \# \left\{ t \in \mathbb {N}\, \Big| \, X(t) = x_0 \right\} \) the number of times the random walk \(X= \big(X(t)\big)_{t \in \mathbb {N}}\) is at its starting point. The random walk \(X\) is said to be expectation recurrent if \(\mathsf{E}[ L ] \, = \, +\infty \) and expectation transient if \(\mathsf{E}[ L ] \; {\lt} \; +\infty \).

Definition 3.3

The random walk \(X= \big(X(t)\big)_{t \in \mathbb {N}}\) is said to be first return recurrent if \(\mathsf{P}\big[ X(t) = x_0 \text{ for some } t {\gt} 0 \big] \, = \, 1\) and first return transient if \(\mathsf{P}\big[ X(t) = x_0 \text{ for some } t {\gt} 0 \big] \; {\lt} \; 1\).

Lemma 3.4

A Markovian random walk \(X= \big(X(t)\big)_{t \in \mathbb {N}}\) is recurrent if and only if it is expectation recurrent.

Proof ▶

…

Lemma 3.5

A Markovian random walk \(X= \big(X(t)\big)_{t \in \mathbb {N}}\) is recurrent if and only if it is first return recurrent.

Proof ▶

…

Simple random walks are Markovian, so the previous two lemmas imply that Definitions 3.1, 3.2 and 3.3 are logically equivalent for a simple random walk. This project first establishes expectation recurrence in Theorem 1.2; the other formulations are obtained as consequences.