Return Generating Functions and Renewal Decomposition

Why First Returns Organize All Returns

A visit to a state at time $n$ can occur only after the chain has either returned to that state earlier or avoided it until time $n$. The first return separates these possibilities in a particularly useful way: once the chain first returns, its subsequent evolution starts afresh from the same state. This renewal structure gives an exact relation between probabilities of being back at a state and probabilities of returning there for the first time.

We work with a time-homogeneous Markov chain $(X_n)_{n\in\mathbb{N}_0}$ on a countable state space, started at a fixed state $o$. The arguments below use the Markov property at the first return time. Write $\mathbb{P}_o$ for probability given $X_0=o$.

Definition: The first return time to $o$ is $\tau_o^+=\inf\{n\in\mathbb{N}:X_n=o\}$, with $\inf\varnothing=\infty$. For $n\in\mathbb{N}_0$, define $p_n=\mathbb{P}_o(X_n=o)$. For $n\in\mathbb{N}$, define $f_n=\mathbb{P}_o(\tau_o^+=n)$. The return-probability and first-return generating functions are $P(z)=\sum_{n=0}^{\infty}p_nz^n$ and $F(z)=\sum_{n=1}^{\infty}f_nz^n$, respectively.

In particular, $p_0=1$, while the $f_n$ need not sum to one: their sum is the probability that the chain ever returns to $o$. Both generating functions are well-defined for $0\leq z<1$, since their coefficients are probabilities. We use the convention that $o$ is recurrent if $\mathbb{P}_o(\tau_o^+<\infty)=1$, and transient if this probability is less than one.

The Renewal Equation

For a return at time $n\geq1$, there is a unique first return time $k\in\{1,\ldots,n\}$. On the event that this first return occurs at time $k$, the chain is at $o$ at time $n$ precisely when, starting from $o$ at time $k$, it is at $o$ again $n-k$ steps later. The Markov property gives that latter probability as $p_{n-k}$. Summing over the disjoint possible first return times gives the renewal equation.

Theorem: For every $n\in\mathbb{N}$, $$ p_n=\sum_{k=1}^{n} f_k p_{n-k}. $$ For $0\leq z<1$, the generating functions satisfy $$ P(z)=1+F(z)P(z)=\frac{1}{1-F(z)}. $$

Proof. The events $\{\tau_o^+=k\}$, for $1\leq k\leq n$, are disjoint. On each such event, the Markov property at time $k$ gives $\mathbb{P}_o(X_n=o\mid \tau_o^+=k)=p_{n-k}$. Therefore $p_n=\sum_{k=1}^{n}f_kp_{n-k}$, as claimed.

Multiply this identity by $z^n$ and sum over $n\geq1$. All terms are nonnegative, so the sums can be regrouped; equivalently, the coefficient of $z^n$ in the product $F(z)P(z)$ is the finite sum $\sum_{k=1}^{n}f_kp_{n-k}$. Thus $\sum_{n\geq1}p_nz^n=F(z)P(z)$. Adding $p_0=1$ yields $P(z)=1+F(z)P(z)$. For $z<1$, $F(z)<1$: indeed, $f_k$ sum to at most one and $z^k<1$ for every $k\geq1$. Rearranging proves the stated formula. \(\square

This identity is a generating-function form of renewal decomposition. The factor $F(z)$ records the first-return segment, which may be a one-step self-transition; the factor $P(z)$ records the subsequent time spent starting afresh from $o$. The constant $1$ accounts for the visit at time zero.

A Generating-Function Criterion for Recurrence

At $z=1$, the sum of the first-return probabilities is exactly the chance of ever returning. The renewal identity shows that this total probability controls whether the return-probability generating function becomes unbounded as $z$ increases to one.

Theorem: The state $o$ is recurrent if and only if $$ \lim_{z\uparrow1}P(z)=\infty. $$ It is transient if and only if this limit is finite; in that case, $$ \lim_{z\uparrow1}P(z)=\frac{1}{1-\sum_{n=1}^{\infty}f_n}. $$

Proof. Because $f_n\geq0$, monotone convergence gives $\lim_{z\uparrow1}F(z)=\sum_{n\geq1}f_n=\mathbb{P}_o(\tau_o^+<\infty)$. If $o$ is recurrent, this sum is one. The identity $P(z)=1/(1-F(z))$ then implies $P(z)\to\infty$. If $o$ is transient, the sum is some number $r<1$, so the same identity gives $P(z)\to1/(1-r)<\infty$. These cases prove both directions. \(\square

Since $p_n\geq0$, monotone convergence also gives $\lim_{z\uparrow1}P(z)=\sum_{n=0}^{\infty}p_n$, allowing the value $+\infty$. Thus the criterion can equivalently be stated as divergence of the sum of return probabilities. This identifies recurrence through the entire sequence of return probabilities, even when the first-return probabilities are easier to calculate directly.

Worked Return-Time Laws

Worked Example: A Deterministic Return After Two Steps

Consider the chain on $\{o,a\}$ that moves from $o$ to $a$ and from $a$ to $o$ with probability one. Starting from $o$, the first return occurs at time two, so $f_2=1$ and every other $f_n$ is zero. Consequently, $$ F(z)=z^2,\qquad P(z)=\frac{1}{1-z^2}=\sum_{k=0}^{\infty}z^{2k},\quad 0\leq z<1. $$ The series says $p_{2k}=1$ and $p_{2k+1}=0$. Since $F(1)=1$, the state is recurrent. The return time is nevertheless finite and deterministic: $\tau_o^+=2$ with probability one.

Worked Example: A Countable Chain with Geometric Branch Probabilities

Take the state space consisting of $o$ and states $(n,j)$ for $n\in\mathbb{N}$ and $1\leq j\leq n$. From $o$, choose $n$ with probability $2^{-n}$ and move to $(n,1)$. For $j<n$, move from $(n,j)$ to $(n,j+1)$ with probability one; from $(n,n)$, move to $o$ with probability one. The choice probabilities sum to one, since $\sum_{n\geq1}2^{-n}=1$.

Choosing branch $n$ takes $n+1$ steps to return: one step from $o$ to $(n,1)$, $n-1$ steps between the listed states, and one step back to $o$. This includes $n=1$, for which the path is $o\to(1,1)\to o$. Hence $f_{n+1}=2^{-n}$, not $2^{-n}$ at time $n$, and $$ F(z)=\sum_{n=1}^{\infty}2^{-n}z^{n+1} =\frac{z^2}{2}\sum_{n=1}^{\infty}\left(\frac{z}{2}\right)^{n-1} =\frac{z^2}{2-z}. $$ The renewal identity then gives $$ P(z)=\frac{1}{1-F(z)} =\frac{2-z}{2-z-z^2} =\frac{2-z}{(1-z)(2+z)}. $$ At $z=1$, the first-return probabilities sum to one, so $o$ is recurrent. The mean return time is finite and equals $$ \mathbb{E}_o[\tau_o^+] =\sum_{n=1}^{\infty}(n+1)2^{-n} =2+1=3. $$ Here $\sum_{n\geq1}n2^{-n}=2$ and $\sum_{n\geq1}2^{-n}=1$. This example shows that recurrence does not require an infinite expected return time.

Worked Example: A Transient State with a Possible Escape

Consider the chain on $\{o,a,b\}$ with transitions from $o$ to $a$ and $b$ each having probability $1/2$, transition $a\to o$ certain, and $b\to b$ certain. Starting at $o$, the chain returns if and only if it first chooses $a$. Therefore $f_2=1/2$, all other $f_n=0$, and $$ F(z)=\frac{z^2}{2},\qquad P(z)=\frac{1}{1-z^2/2}. $$ In particular, $\sum_{n\geq1}f_n=1/2<1$, so $o$ is transient. Expanding the geometric series also verifies the return probabilities directly: $$ P(z)=\sum_{k=0}^{\infty}\frac{z^{2k}}{2^k}, \qquad p_{2k}=2^{-k},\quad p_{2k+1}=0. $$ Thus $\sum_{n\geq0}p_n=\sum_{k\geq0}2^{-k}=2$, agreeing with the criterion's value $1/(1-1/2)=2$.

Worked Example: Two Possible First-Return Times

On the two-state space $\{o,a\}$, let the chain move from $o$ to $o$ with probability $1/2$, and from $o$ to $a$ with probability $1/2$; from $a$, let it move to $o$ with probability one. A first return takes one step in the first case and two steps in the second. Therefore $f_1=f_2=1/2$, and $$ F(z)=\frac{z+z^2}{2},\qquad P(z)=\frac{1}{1-(z+z^2)/2}. $$ The renewal equation gives $p_0=1$, $p_1=f_1p_0=1/2$, and $p_2=f_1p_1+f_2p_0=1/4+1/2=3/4$. Because $F(1)=1$, the state is recurrent. The mean first-return time is $\sum_{n\geq1}nf_n=1(1/2)+2(1/2)=3/2$.

Interpretation and a Common Pitfall

The distinction between $p_n$ and $f_n$ matters. The probability $p_n$ concerns being at $o$ at time $n$, allowing any number of earlier returns. The probability $f_n$ concerns the first return occurring exactly at time $n$. They are not generally equal: the renewal equation combines each possible first-return time with the probability of a later return over the remaining steps.

Another important distinction is between recurrence and the expected return time. Recurrence says only that the return occurs eventually with probability one. It does not assert that the return time has a finite expectation. The generating-function identity detects whether the return probability is one; further information about the shape of $F(z)$ near one can encode more about return times, but the recurrence criterion itself requires only its limiting value.

When constructing a return-time example, count transitions, not just the number used to label a branch or intermediate states. In the countable-chain example, entering the branch and leaving it are both steps. Counting those transitions correctly determines the exponent of $z$, and changing that exponent changes the generating function.

Check Your Understanding

Use the definitions and renewal identity to answer the following questions.

Why does the renewal equation sum over first-return times $k\leq n$, rather than over all possible return times without distinguishing the first?
If $F(z)=z^3$, what are the nonzero return probabilities $p_n$, and is $o$ recurrent?
For a transient state with total first-return probability $r$, what is $\lim_{z\uparrow1}P(z)$?
In the countable-chain example, why does selecting branch $n$ produce a first return at time $n+1$?
Does recurrence by itself imply a finite expected first-return time? Explain using an example above.