First-Return Decomposition of the Green Function

Return Probabilities and First Returns

A return to the origin at time $n$ can happen in several ways: the walk may return for the first time at $n$, or it may return earlier and then return again after the remaining steps. Splitting according to the first return time turns this path decomposition into a renewal equation. Summing the return probabilities then gives a direct test for recurrence.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a countable state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Write $o\in S$ for the state of interest, and let $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$ be the natural filtration. We use $\mathbb{P}_o$ and $\mathbb{E}_o$ when $X_0=o$. The results below apply in particular to a random walk on $\mathbb{Z}^d$ started at the origin.

Definition: The return probability at time $n$ is $u_n=\mathbb{P}_o(X_n=o)$, with $u_0=1$. The first positive return time is $T_o^+=\inf\{n\ge1:X_n=o\}$, with $\inf\varnothing=\infty$. Set $f_n=\mathbb{P}_o(T_o^+=n)$ for $n\ge1$, and $r_o=\mathbb{P}_o(T_o^+<\infty)=\sum_{n\ge1}f_n$. The return Green function is the possibly infinite sum $G(o,o)=\sum_{n\ge0}u_n$. The state $o$ is recurrent if $r_o=1$, and transient if $r_o<1$.

These definitions concern visits starting at $o$. The Green function counts the initial visit at time zero as well as every later visit: if $V=\sum_{n\ge0}\mathbf{1}_{\{X_n=o\}}$, then $G(o,o)=\mathbb{E}_o[V]$, allowing the value infinity. Indeed, expectations of the increasing partial sums of $V$ converge to the expectation of $V$ by the monotone convergence theorem.

The First-Return Renewal Equation

Theorem (First-return decomposition): For every integer $n\ge1$, $$ u_n=\sum_{k=1}^{n} f_k u_{n-k}. $$ For $0\le z<1$, define $U(z)=\sum_{n\ge0}u_nz^n$ and $F(z)=\sum_{n\ge1}f_nz^n$. Then $$ U(z)=\frac{1}{1-F(z)}. $$

Proof. Fix $n\ge1$. On the event $\{X_n=o\}$, the chain has a first positive return at some time $k$ with $1\le k\le n$. The events $\{T_o^+=k\}$, for these values of $k$, are disjoint and partition $\{X_n=o\}$. For a value $k$ with $f_k>0$, the Markov property at the deterministic time $k$, conditional on the history through time $k$, gives $\mathbb{P}_o(X_n=o\mid\mathcal{F}_k)=\mathbb{P}_{X_k}(X_{n-k}=o)=u_{n-k}$ on $\{T_o^+=k\}$, since $X_k=o$ there. Thus $\mathbb{P}_o(X_n=o,T_o^+=k)=f_ku_{n-k}$. If $f_k=0$, the event $\{T_o^+=k\}$ has probability zero, so its joint probability with $\{X_n=o\}$ is zero, which is also $f_ku_{n-k}$. Summing over $k=1,\ldots,n$ proves the renewal equation. Now multiply by $z^n$ and sum over $n\ge1$. All terms are nonnegative, so the double sum can be regrouped, giving $U(z)-1=F(z)U(z)$. The series converge for $0\le z<1$, since $u_n\le1$ and $\sum_{n\ge1}f_n\le1$. Also $F(z)\le z\sum_{n\ge1}f_n\le z<1$, so division by $1-F(z)$ is valid and yields the identity. $\square$

The equation is a convolution: the first-return time contributes $f_k$, and after that return the probability of being back at the origin $n-k$ steps later is $u_{n-k}$. At $z=1$, the same identity needs care because either series may diverge. The recurrence test below handles that endpoint using the total return probability $r_o$.

Worked Example: A Recurrent Two-State Chain

Consider $S=\{o,a\}$ and the transition matrix, with rows and columns ordered $o,a$, $$ P=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac12&\tfrac12\end{bmatrix}. $$ Each row sums to $\tfrac12+\tfrac12=1$. Starting at $o$, find the first-return probabilities and the Green function.

A first return at time $1$ occurs by moving from $o$ to $o$, so $f_1=\tfrac12$. For $n\ge2$, the first step must be from $o$ to $a$, the chain must stay at $a$ for the next $n-2$ steps, and then move to $o$. Therefore $$ f_n=\tfrac12\left(\tfrac12\right)^{n-2}\tfrac12 =\left(\tfrac12\right)^n,\qquad n\ge2. $$ The sum of the first-return probabilities is $\sum_{n\ge1}f_n=\sum_{n\ge1}(1/2)^n=1$, so the origin is recurrent.

For every $n\ge1$, $u_n=\tfrac12$: after one step the distribution is $(\tfrac12,\tfrac12)$, and multiplying that row vector by $P$ leaves it unchanged. Hence $G(o,o)=1+\sum_{n\ge1}\tfrac12=\infty$. The generating functions also verify the decomposition: $$ F(z)=\sum_{n\ge1}\left(\tfrac z2\right)^n=\frac{z}{2-z}, \qquad U(z)=1+\sum_{n\ge1}\frac{z^n}{2} =1+\frac{z}{2(1-z)} =\frac{2-z}{2(1-z)} =\frac{1}{1-F(z)}. $$ As a coefficient check, $u_2=f_1u_1+f_2u_0=\tfrac12\cdot\tfrac12+\tfrac14\cdot1=\tfrac12$, agreeing with the direct calculation.

Worked Example: A Transient Walk on the Integer Lattice

Let $(X_n)_{n\ge0}$ be a random walk on $S=\mathbb{Z}$, started at $X_0=0$, whose independent increments are $0$ and $1$, each with probability $\tfrac12$. From any state $i$, the transition probabilities are $p_{ii}=\tfrac12$ and $p_{i,i+1}=\tfrac12$; all other entries are zero. Each transition-kernel row sums to $\tfrac12+\tfrac12=1$. Compute $f_n$, $u_n$, and $G(0,0)$.

The walk is at $0$ at time $n$ exactly when all $n$ increments are zero. Thus $u_n=(\tfrac12)^n$ for $n\ge0$. A first positive return happens only at time $1$, when the first increment is zero. If the first increment is $1$, the walk can never return to $0$, since subsequent increments are nonnegative. Therefore $f_1=\tfrac12$, and $f_n=0$ for every $n\ge2$. In particular, $r_0=\tfrac12$, so the origin is transient.

The Green function is the geometric series $$ G(0,0)=\sum_{n\ge0}\left(\tfrac12\right)^n =\frac{1}{1-\tfrac12}=2. $$ The renewal equation checks at every time: for $n\ge1$, its right side is $f_1u_{n-1}=\tfrac12(\tfrac12)^{n-1}=(\tfrac12)^n=u_n$; all terms with $k\ge2$ vanish. The generating functions give the same result: $F(z)=z/2$ and $U(z)=1/(1-z/2)=1/(1-F(z))$.

Recurrence Is Equivalent to Green-Function Divergence

Theorem (Green-function recurrence criterion): For a discrete-time Markov chain started at $o$, $$ G(o,o)=\infty\quad\Longleftrightarrow\quad r_o=1. $$ More precisely, $G(o,o)=1/(1-r_o)$ when $r_o<1$, while $G(o,o)=\infty$ when $r_o=1$.

Proof. Define successive return times by $R_0=0$ and $R_{m+1}=\inf\{n>R_m:X_n=o\}$ when $R_m<\infty$; set $R_{m+1}=\infty$ if $R_m=\infty$. These are stopping times for the natural filtration. We first show $\mathbb{P}_o(R_m<\infty)=r_o^m$ for every $m\ge0$. For any finite $t$ with $\mathbb{P}_o(R_m=t)>0$, the Markov property at deterministic time $t$ says that, given the history through $t$, the probability of a later return is $r_o$ on $\{R_m=t\}$, because $X_t=o$. Consequently $\mathbb{P}_o(R_m=t,\ R_{m+1}<\infty)=\mathbb{P}_o(R_m=t)r_o$. If $\mathbb{P}_o(R_m=t)=0$, both sides are zero; no conditioning on that null event is needed. Summing over the countable set of finite $t$ gives $\mathbb{P}_o(R_{m+1}<\infty)=r_o\mathbb{P}_o(R_m<\infty)$. Since $R_0=0$, induction proves the claim.

On every sample path, the visits to $o$ occur exactly at the finite times among $R_0,R_1,\ldots$. Therefore $V=\sum_{m\ge0}\mathbf{1}_{\{R_m<\infty\}}$. Taking expectations and using monotone convergence, $$ G(o,o)=\mathbb{E}_o[V] =\sum_{m\ge0}\mathbb{P}_o(R_m<\infty) =\sum_{m\ge0}r_o^m. $$ If $r_o<1$, this geometric series equals $1/(1-r_o)$, which is finite. If $r_o=1$, every term is $1$, so the sum diverges. These two cases prove both directions. They also show that $r_o=1$ entails infinitely many returns almost surely: for every $m$, $\mathbb{P}_o(R_m<\infty)=1$, and the intersection of these countably many probability-one events still has probability one. $\square$

Worked Example: A First-Return Law with a Geometric Tail

Consider $S=\{o,a\}$ with $$ P=\begin{bmatrix}\tfrac13&\tfrac23\\[2pt]\tfrac12&\tfrac12\end{bmatrix}. $$ The first row sums to $\tfrac13+\tfrac23=1$, and the second sums to $\tfrac12+\tfrac12=1$. Starting from $o$, compute the first-return law, its total mass, and the generating function.

At time $1$, a return occurs if the chain stays at $o$, so $f_1=\tfrac13$. For $n\ge2$, the chain must move to $a$ at time $1$, remain at $a$ through time $n-1$, and move to $o$ at time $n$. Thus $$ f_n=\tfrac23\left(\tfrac12\right)^{n-2}\tfrac12 =\tfrac23\left(\tfrac12\right)^{n-1},\qquad n\ge2. $$ Summing the tail with its first term shown, $$ r_o=\sum_{n\ge1}f_n =\tfrac13+\tfrac23\sum_{n\ge2}\left(\tfrac12\right)^{n-1} =\tfrac13+\tfrac23\cdot1=1. $$ The origin is recurrent, and the criterion gives $G(o,o)=\infty$.

For $0\le z<1$, the first-return generating function is $$ F(z)=\tfrac z3+\tfrac23\sum_{n\ge2}\left(\tfrac12\right)^{n-1}z^n =\tfrac z3+\frac{z^2}{3(1-z/2)} =\frac{z(2+z)}{6-3z}. $$ Therefore $$ U(z)=\frac{1}{1-F(z)} =\frac{6-3z}{6-5z-z^2}. $$ The initial coefficients provide a direct check. Here $u_0=1$, $u_1=f_1=\tfrac13$, and the renewal equation gives $u_2=f_1u_1+f_2u_0=\tfrac13\cdot\tfrac13+\tfrac13\cdot1=\tfrac49$. Directly, the two-step return probability is $p_{oo}^{(2)}=p_{oo}p_{oo}+p_{oa}p_{ao}=\tfrac13\cdot\tfrac13+\tfrac23\cdot\tfrac12=\tfrac49$.

Interpreting the Criterion and Avoiding a Pitfall

The criterion says that the Green function is an expected count of visits, not a probability. In a transient case, it is finite and equals $1/(1-r_o)$; in a recurrent case, returns occur infinitely often almost surely and the expected total number of visits is infinite. The criterion does not assert that $u_n$ itself has a limit, nor does it require aperiodicity. Periodic chains may have $u_n=0$ at many times and still have a divergent sum of return probabilities.

Common mistake: conditioning on an impossible return time. Writing $\mathbb{P}_o(X_n=o\mid T_o^+=k)$ without checking $f_k>0$ is not valid when $f_k=0$, because conditional probability given a null event is undefined. The proof handles positive-mass values by conditioning, and handles zero-mass values by observing that the joint probability is zero. A separate algebraic mistake is to retain only the possibility of returning at the final step. In the recurrent two-state example, that incorrect calculation would give $u_2=f_2u_0=\tfrac14$. The correct decomposition includes both first-return times: $u_2=f_1u_1+f_2u_0=\tfrac14+\tfrac14=\tfrac12$.

For a lattice random walk, this decomposition is useful because it separates the distribution of the first return from all subsequent returns. One can study either side: the first-return probabilities determine $U(z)$ through $U(z)=1/(1-F(z))$, while the divergence of the total return Green function determines whether the origin is recurrent. Any endpoint argument at $z=1$ must respect possible divergence; the return-time proof establishes the criterion without treating divergent series as finite quantities.

Check Your Understanding

Use the definitions and verify any numerical answer by substitution.

For a chain started at $o$, what event is measured by $f_n$, and how does it differ from the event measured by $u_n$?
In the renewal equation for $u_4$, write out every term and identify what the index $k$ represents.
If $r_o=\tfrac34$, compute $G(o,o)$ and state the probability of infinitely many returns.
Why is it invalid to condition on $\{T_o^+=k\}$ when $f_k=0$, and how does the decomposition proof handle that case?
For the two-state recurrent example, verify $u_2=f_1u_1+f_2u_0$ using the stated values.

First-Return Decomposition of the Green Function

What You'll Learn