Green-Function Criteria for Recurrence

From Returns to Total Visits

A Green function records expected visit counts. For a state $x$, its diagonal value counts visits to $x$ when the walk starts at $x$. The key question is whether this count is finite or infinite on average. The answer is governed exactly by whether the walk returns to $x$ with probability one.

This criterion is useful because recurrence can be difficult to see from individual paths, while a return probability or a Green-function sum may be easier to calculate. The distinction between the initial visit and a return after time zero is essential: every walk started at $x$ visits $x$ at time zero, whether or not it ever comes back.

Definitions and the Recurrence Criterion

Let $(X_n)_{n\in\mathbb{N}_0}$ be a discrete-time Markov chain on a countable state space $E$, with transition probabilities $p(u,v)$. Write $\mathbb{P}_x$ and $\mathbb{E}_x$ for probability and expectation when $X_0=x$. Define the first return time to $x$ by

T_x^+ = \inf\{n\in\mathbb{N}:X_n=x\},

where the infimum of the empty set is $\infty$. The time index starts at $1$, so $T_x^+$ does not count the initial visit.

Definition: A state $x$ is recurrent if $\mathbb{P}_x(T_x^+<\infty)=1$. It is transient if $\mathbb{P}_x(T_x^+<\infty)<1$. Define its return probability by $f_x=\mathbb{P}_x(T_x^+<\infty)$, and its diagonal Green function by $$ G(x,x)=\sum_{n=0}^{\infty}\mathbb{P}_x(X_n=x). $$

The Green function is also the expected total number of visits, including the visit at time zero. Indeed, if $N_x=\sum_{n=0}^{\infty}\mathbf{1}_{\{X_n=x\}}$, then monotone convergence for nonnegative sums gives $G(x,x)=\mathbb{E}_x[N_x]$, allowing either side to be infinite.

Theorem (Green-function criterion for recurrence): For every state $x$, $$ G(x,x)=\sum_{k=0}^{\infty} f_x^k = \begin{cases} \infty, & f_x=1,\\[4pt] \dfrac{1}{1-f_x}, & f_x<1. \end{cases} $$ Consequently, $x$ is recurrent if and only if $G(x,x)=\infty$.

Proof. Set $S_0=0$, and, recursively, let $S_{k+1}$ be the first time strictly after $S_k$ at which the chain is at $x$. If $S_k=\infty$, set $S_{k+1}=\infty$. The finite values among $S_0,S_1,\ldots$ are exactly the times at which the chain visits $x$. Thus $N_x=\sum_{k=0}^{\infty}\mathbf{1}_{\{S_k<\infty\}}$.

For each $k$, $\mathbb{P}_x(S_k<\infty)=f_x^k$. This holds for $k=0$. If it holds for $k$, then on the event $S_k<\infty$, the strong Markov property at $S_k$ says that the probability of a further return is $f_x$. Therefore $\mathbb{P}_x(S_{k+1}<\infty)=\mathbb{P}_x(S_k<\infty)f_x=f_x^{k+1}$.

Taking expectations of the nonnegative sum for $N_x$, and using monotone convergence, gives $\mathbb{E}_x[N_x]=\sum_{k=0}^{\infty}f_x^k$. If $f_x=1$, every term equals one and the series diverges. If $f_x<1$, the geometric series sums to $1/(1-f_x)$. Since $G(x,x)=\mathbb{E}_x[N_x]$, the claimed criterion follows.

$\square$

The argument uses successive returns, not an assumption that the chain is irreducible. It therefore applies state by state, including when some states communicate and others do not.

What the Visit Count Says About the Path

The same return-time argument gives more than an expected value. It describes whether the number of visits is finite or infinite with probability one.

Proposition: If $f_x<1$, then $$ \mathbb{P}_x(N_x=m)=(1-f_x)f_x^{m-1},\qquad m\in\mathbb{N}. $$ In particular, $N_x$ is finite almost surely. If $f_x=1$, then $N_x=\infty$ almost surely.

Proof. The event $N_x=m$ means that the walk makes $m-1$ returns after its initial visit and then makes no further return. By the strong Markov property at each return, the probability of the first $m-1$ returns is $f_x^{m-1}$, and, after the last such return, the probability of no further return is $1-f_x$. Multiplying gives the formula. When $f_x<1$, the probabilities sum to $(1-f_x)\sum_{m=1}^{\infty}f_x^{m-1}=1$, so $N_x$ is finite almost surely. When $f_x=1$, for every $m$ the probability of at least $m$ visits is one; taking the intersection over all positive integers $m$ shows that $N_x=\infty$ almost surely.

$\square$

For a transient state, the expected number of visits is finite, but the chain still visits it at least once when started there. For a recurrent state, the chain returns infinitely often almost surely, not merely with an infinite expected number of visits.

Worked Examples

Worked Example: A Deterministic Two-State Cycle

Consider the walk on $E=\{a,b\}$ that moves from $a$ to $b$ with probability one and from $b$ to $a$ with probability one. Starting from $a$, the walk is at $a$ exactly at the even times:

\mathbb{P}_a(X_n=a)= \begin{cases} 1, & n\text{ is even},\\ 0, & n\text{ is odd}. \end{cases}

It follows directly that

G(a,a)=\sum_{n=0}^{\infty}\mathbb{P}_a(X_n=a) =1+0+1+0+\cdots=\infty.

The first return time is exactly $2$, so $f_a=1$ and $a$ is recurrent. This example also illustrates why aperiodicity is not required for recurrence: visits can be restricted to particular times and still occur infinitely often.

Worked Example: A Walk That Returns Almost Surely

Let $E=\mathbb{N}_0$. From state $0$, the walk moves to $1$ with probability one. From each $n\in\mathbb{N}$, it moves to $0$ with probability $1/(n+1)$, and to $n+1$ with probability $n/(n+1)$.

Starting at $0$, the walk must first reach $1$. To avoid returning to $0$ by the time it has made its decision at state $N$, it must move upward at each of $1,2,\ldots,N$. The probability of doing so is

\prod_{n=1}^{N}\frac{n}{n+1} =\frac{1}{N+1}.

These events decrease as $N$ increases. The probability of never returning is their limiting probability, which is $\lim_{N\to\infty}1/(N+1)=0$. Hence $f_0=1$, so $0$ is recurrent and $G(0,0)=\infty$.

The walk does not have to return quickly. For instance, it can make many upward moves before choosing a transition back to $0$. Recurrence concerns whether a return eventually occurs with probability one, not how long the return takes.

Worked Example: A Walk with Positive Probability of Escape

Keep the same state space and transition structure, but from each $n\in\mathbb{N}$ let the walk move to $0$ with probability $2^{-n}$, and move to $n+1$ with probability $1-2^{-n}$. Again, the first move from $0$ is to $1$.

The probability of moving upward at every decision from $1$ through $N$ is

\prod_{n=1}^{N}(1-2^{-n}).

The probability of never returning is the limit of these probabilities as $N$ tends to infinity. This limit, denoted $L=\prod_{n=1}^{\infty}(1-2^{-n})$, is strictly positive. To verify positivity, separate the first factor and use $\log(1-u)\geq -2u$ for $0\leq u\leq 1/2$:

\log L =\log(1/2)+\sum_{n=2}^{\infty}\log(1-2^{-n}) \geq \log(1/2)-2\sum_{n=2}^{\infty}2^{-n} =\log(1/2)-1>-\infty.

Thus $L>0$, so $f_0=1-L<1$. The state $0$ is transient, and its Green function is finite:

G(0,0)=\frac{1}{1-f_0}=\frac{1}{L}<\infty.

The walk has a positive probability of escaping upward forever, even though at every individual state there is a positive probability of moving back to $0$. The infinite product accounts for the probability of avoiding return at every successive state.

Using the Criterion Carefully

The criterion compares two quantities tied to the same starting state and target state: the probability of a positive-time return to $x$, and the expected total number of visits to $x$ starting from $x$. In particular, $G(x,x)$ includes the initial visit, while $T_x^+$ does not. Changing either convention without adjusting the formula can lead to an off-by-one error.

Another important distinction is between recurrence and the expected return time. Recurrence asks whether $T_x^+<\infty$ almost surely; it does not assert that $\mathbb{E}_x[T_x^+]$ is finite. A return can occur almost surely while taking a sufficiently long time, on average, that its expected duration is infinite. The Green-function criterion concerns the number of visits, not the mean time between them.

In applications, one may proceed in either direction. If the return probability can be computed, the geometric-series identity immediately gives the diagonal Green function. If the Green sum can be evaluated or bounded, its divergence or finiteness classifies the state. The examples show both the value of this relationship and the need to check infinite products or series rather than infer long-term behavior from a few steps.

Check Your Understanding

Use the definitions and criterion above to answer the following questions.

Why does the definition of $T_x^+$ start at time $1$, while $G(x,x)$ includes the term at time $0$?
If a state has return probability $f_x=2/3$, what is $G(x,x)$?
In the walk with upward-move probabilities $n/(n+1)$, what is the probability of avoiding return through the decision at state $N$?
Why does the positive infinite product in the escape example imply transience?
Does recurrence require the expected time of the first return to be finite? Explain what recurrence requires instead.