Generating Functions for Return-Time Laws

Two Series That Record Returns

A return-time law records when a chain first comes back to its starting state. A different series records the probability of being at that state at each time. These series are linked: every visit after time zero must follow a first return, after which the chain starts the return process afresh. Generating functions turn that decomposition into an algebraic identity. The identity gives access both to individual return probabilities and to the total expected number of visits.

Let $(X_n)_{n\ge0}$ be a time-homogeneous Markov chain on a finite or countable state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with transition matrix $P=(p_{ij})$. Each row of $P$ sums to $1$. Its natural filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. Fix a state $i\in S$, and write $\mathbb{P}_i$ and $\mathbb{E}_i$ for probability and expectation when $X_0=i$. The first-return time is $T_i^+=\inf\{n\ge1:X_n=i\}$, with $T_i^+=\infty$ if the chain never returns. For $n\ge1$, set $f_n=\mathbb{P}_i(T_i^+=n)$, and for $n\ge0$, set $u_n=p_{ii}^{(n)}=\mathbb{P}_i(X_n=i)$, where $u_0=1$.

Definition: For $0\le s<1$, the first-return generating function and return-probability generating function are $$ F_i(s)=\sum_{n=1}^{\infty}f_n s^n,\qquad U_i(s)=\sum_{n=0}^{\infty}u_n s^n. $$ The first series weights each possible first-return time; the second weights the probability of being at $i$ at each time. Both series converge for $0\le s<1$, since $0\le f_n\le1$ and $0\le u_n\le1$.

The endpoint $s=1$ has a direct probabilistic meaning. The events $\{T_i^+=n\}$, $n\ge1$, are disjoint and their union is $\{T_i^+<\infty\}$. Therefore their probabilities sum to the eventual return probability. Define $r_i=\mathbb{P}_i(T_i^+<\infty)$. Nonnegative series give $$ F_i(1):=\sum_{n=1}^{\infty}f_n=r_i. $$ This definition at $1$ does not assert that the chain returns with probability one.

The Coefficient Renewal Equation

Proposition: For every $n\ge1$, $$ u_n=\sum_{k=1}^{n}f_k u_{n-k}. $$ Consequently, for each $n$, $u_n$ is the sum over all ordered compositions $n=k_1+\cdots+k_m$ into positive integers of the products $f_{k_1}\cdots f_{k_m}$.

Proof. Since $X_0=i$, the event $\{X_n=i\}$ for $n\ge1$ requires a first return at some time $k\in\{1,\ldots,n\}$. These possibilities are disjoint. On $\{T_i^+=k\}$, the chain is at $i$ at time $k$; by the Markov property, its conditional probability of being at $i$ at time $n$ is $p_{ii}^{(n-k)}=u_{n-k}$. Thus $$ \mathbb{P}_i(X_n=i,\ T_i^+=k)=f_k u_{n-k}. $$ Summing over the disjoint possibilities for $k$ proves the equation. To obtain the composition formula, repeatedly substitute the same equation for each term $u_{n-k}$ with $n-k\ge1$, using $u_0=1$. Each substitution selects another positive first-return length, and the process ends when the remaining time is zero. The selected lengths sum to $n$, and their contribution is their product of $f$-values. There are only finitely many compositions of a fixed positive integer $n$, so this expansion is finite. $\square$

In generating-function form, the coefficient equation says that a visit at a positive time consists of a first return followed by zero or more further returns. The identity below makes that interpretation precise and also provides a practical way to compute one series from the other.

Theorem (First-return generating-function identity): For $0\le s<1$, $$ U_i(s)=1+F_i(s)U_i(s)=\frac{1}{1-F_i(s)}. $$ At $s=1$, interpret both series by their nonnegative sums, possibly infinite. Then $$ \sum_{n=0}^{\infty}u_n= \begin{cases} \dfrac{1}{1-r_i},&r_i<1,\\[6pt] \infty,&r_i=1. \end{cases} $$

Proof. For $0\le s<1$, all terms in both series are nonnegative and the series converge. Multiplying their partial sums and grouping terms by total power is justified by nonnegativity; equivalently, the coefficient of $s^n$ in the product is the finite sum $\sum_{k=1}^{n}f_k u_{n-k}$ when $n\ge1$. The constant coefficient of $F_i(s)U_i(s)$ is zero. By the proposition, all its positive-degree coefficients are $u_n$. Hence $F_i(s)U_i(s)=U_i(s)-1$, giving $U_i(s)=1+F_i(s)U_i(s)$. Since $F_i(s)\le\sum_{n\ge1}f_n=r_i\le1$ and $s<1$ implies $F_i(s)<1$, division gives the stated formula. For the strict inequality, if $r_i=0$, then $F_i(s)=0$; if $r_i>0$, at least one $f_k>0$, and $f_k s^k<f_k$ for $0<s<1$. The case $s=0$ has $F_i(0)=0$.

As $s$ increases to $1$, the nonnegative series $F_i(s)$ increases to $r_i$, and $U_i(s)$ increases to $\sum_{n\ge0}u_n$. These limits follow by monotone convergence for series: each finite partial sum tends to its value at $1$, and the full sums are the suprema of their finite partial sums. If $r_i<1$, taking limits in $U_i(s)=1/(1-F_i(s))$ gives $1/(1-r_i)$. If $r_i=1$, the denominator decreases to zero, so $U_i(s)$ increases without bound; thus $\sum_{n\ge0}u_n=\infty$. Finally, $\sum_{n\ge0}u_n=\mathbb{E}_i[\sum_{n\ge0}\mathbf{1}_{\{X_n=i\}}]$ by monotone convergence, so it is the expected total number of visits, including the visit at time zero. $\square$

The coefficient statement and the endpoint statement answer different questions. Coefficients describe timing: $f_n$ is the probability that the first return occurs at exactly time $n$, whereas $u_n$ includes every possible return history that ends at $i$ at time $n$. Values at one summarize totals: $F_i(1)$ is the probability of ever returning, and $U_i(1)$ is the expected number of visits, including time zero. In particular, when $r_i<1$, the expected number of visits is finite; when $r_i=1$, it is infinite.

Worked Calculations

Worked Example: A First-Return Law from a Three-State Chain

Take $S=\{1,2,3\}$ and $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac13&0&\tfrac23\\ \tfrac12&0&\tfrac12 \end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac12+0=1$, $\tfrac13+0+\tfrac23=1$, and $\tfrac12+0+\tfrac12=1$, so these are valid transition probabilities. Starting from state $1$, find $F_1(s)$.

Let $g_j(s)=\mathbb{E}_j[s^{T_1};\,T_1<\infty]$ for $j\ne1$, where $T_1=\inf\{n\ge0:X_n=1\}$. Conditioning on the first step gives $g_2(s)=s(\tfrac13+\tfrac23g_3(s))$ and $g_3(s)=s(\tfrac12+\tfrac12g_3(s))$. Solving the second equation gives $(1-\tfrac{s}{2})g_3(s)=\tfrac{s}{2}$, hence $g_3(s)=s/(2-s)$. Substitution gives $$ g_2(s)=\frac{s}{3}+\frac{2s}{3}\frac{s}{2-s} =\frac{s(2-s)+2s^2}{3(2-s)} =\frac{2s+s^2}{3(2-s)}. $$ From state $1$, a one-step return has probability $\tfrac12$, and a move to state $2$ has probability $\tfrac12$. Thus $F_1(s)=\tfrac{s}{2}+\tfrac{s}{2}g_2(s)$, so $$ F_1(s)=\frac{s}{2}+\frac{s(2s+s^2)}{6(2-s)} =\frac{3s(2-s)+2s^2+s^3}{6(2-s)} =\frac{6s-s^2+s^3}{6(2-s)}. $$ At $s=1$, this gives $F_1(1)=(6-1+1)/(6(2-1))=1$: return is eventual with probability one.

Check the first coefficients. The first-return probabilities are $f_1=\tfrac12$, $f_2=\tfrac12\cdot\tfrac13=\tfrac16$, and $f_3=\tfrac12\cdot\tfrac23\cdot\tfrac12=\tfrac16$. Expanding the displayed rational function through degree three gives $\tfrac12s+\tfrac16s^2+\tfrac16s^3$, consistent with these paths. The coefficient equation gives $u_1=f_1=\tfrac12$ and $u_2=f_1u_1+f_2u_0=\tfrac12\cdot\tfrac12+\tfrac16=\tfrac5{12}$. Directly, $p_{11}^{(2)}=p_{11}p_{11}+p_{12}p_{21}=\tfrac14+\tfrac16=\tfrac5{12}$, as required. Since $F_1(1)=1$, the theorem gives infinitely many expected visits in total.

Worked Example: A Transient State with Finite Expected Visits

Take $S=\{1,2\}$ and $$ P=\begin{bmatrix} \tfrac12&\tfrac12\\ 0&1 \end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac12=1$ and $0+1=1$. From state $1$, the chain either returns immediately with probability $\tfrac12$ or moves to the absorbing state $2$, from which it cannot return. Therefore $f_1=\tfrac12$ and $f_n=0$ for every $n\ge2$, giving $F_1(s)=s/2$.

The generating-function identity yields $$ U_1(s)=\frac{1}{1-s/2}=\sum_{n=0}^{\infty}\left(\frac{s}{2}\right)^n. $$ Thus $u_n=2^{-n}$. This can also be checked directly: to be at state $1$ at time $n$, the chain must take the $1$-to-$1$ transition on all $n$ steps, which has probability $(1/2)^n$. The eventual return probability is $F_1(1)=1/2$, and the expected total number of visits, including time zero, is $U_1(1)=1/(1-1/2)=2$. Checking by summation gives $\sum_{n=0}^{\infty}2^{-n}=1/(1-1/2)=2$.

Worked Example: Returns Only at Multiples of Three

Take $S=\{1,2,3\}$ with the deterministic cycle $$ P=\begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix}. $$ Each row sums to $1$. Starting at state $1$, the chain first returns after exactly three steps, so $f_3=1$ and $f_n=0$ for $n\ne3$. Consequently $F_1(s)=s^3$ and $$ U_1(s)=\frac{1}{1-s^3}=1+s^3+s^6+s^9+\cdots. $$ The coefficients say that $u_n=1$ when $n$ is a nonnegative multiple of three and $u_n=0$ otherwise. Indeed, the deterministic path is at state $1$ precisely at those times. Here $F_1(1)=1$, so return is certain, while $U_1(1)$ is infinite because there are infinitely many visits, one every three steps.

What the Generating Function Does—and Does Not—Say

The identity is useful when one description is easier to obtain than the other. A path enumeration may give the first-return probabilities $f_n$; then the reciprocal $1/(1-F_i(s))$ gives all return probabilities $u_n$. Conversely, if the return-probability series is known, rearranging $U_i=1+F_iU_i$ gives $F_i=1-1/U_i$ for $0\le s<1$. These are statements about generating functions; extracting a particular coefficient may still require algebra or a path argument.

Common mistake. In the two-state example, it is wrong to set $f_2=p_{11}^{(2)}=\tfrac14$. The value $p_{11}^{(2)}$ is the probability of being at state $1$ at time $2$, allowing an earlier return at time $1$. A first return at time $2$ would require the chain to leave state $1$ at time $1$ and then return at time $2$; in this example the move to state $2$ is absorbing, so $f_2=0$. The incorrect expression $F_1(s)=s/2+s^2/4$ therefore counts a path that does not exist. The correction is to use $F_1(s)=s/2$, then obtain $U_1(s)=1/(1-s/2)$. A first-return probability and an $n$-step return probability are different quantities.

There is also an important endpoint distinction. A value $F_i(1)=1$ identifies certain eventual return, but does not give a finite expected number of visits: the theorem shows that the expected total number is infinite. A value $F_i(1)<1$ instead gives the finite expectation $1/(1-F_i(1))$. The generating-function identity therefore turns a probability of eventual return into a total-visit calculation without requiring the individual return-time probabilities to be summed by hand.

Check Your Understanding

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

For a state $i$, explain why $u_0=1$ but the first-return generating function has no constant term.
If $f_1=\tfrac14$, $f_2=\tfrac12$, and all later $f_n=0$, compute $F_i(s)$, $F_i(1)$, and the expected total number of visits when starting at $i$.
Suppose $f_1=\tfrac12$, $f_2=\tfrac14$, and all later first-return probabilities are zero. Use the coefficient equation to find $u_1$ and $u_2$.
In the deterministic three-state cycle, why is $p_{11}^{(2)}=0$ even though the eventual return probability is $1$?
State the difference between $F_i(1)$ and $\sum_{n\ge0}p_{ii}^{(n)}$, and explain what each quantity measures.

Generating Functions for Return-Time Laws

What You'll Learn