Path Enumeration for First Returns

First Returns as Weighted Path Sums

A return to a state can happen along many different routes. To find the probability of returning for the first time at step $n$, it is not enough to count how many routes exist: each route has its own probability, and every route that visits the target state earlier must be excluded. Path enumeration makes both requirements explicit. It is particularly useful in small chains, where the admissible routes can be listed and their weights calculated directly.

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})$, with transition matrix $P=(p_{jk})$. The matrix is row-stochastic: $p_{jk}\ge0$ and $\sum_{k\in S}p_{jk}=1$ for every $j\in S$. For a state $i$, let $T_i^+=\inf\{n\ge1:X_n=i\}$ be its first return time. When the chain starts at $i$, write $f_i(n)=\mathbb{P}_i(T_i^+=n)$. This is the probability of a first return exactly at step $n$, not the probability of merely being at $i$ at step $n$.

Definition: For $n\ge2$, an admissible path of length $n$ from $i$ back to $i$ is a sequence $(i,x_1,\ldots,x_{n-1},i)$ with every $x_r\in S\setminus\{i\}$. Its weight is $p_{i x_1}p_{x_1x_2}\cdots p_{x_{n-1}i}$. For $n=1$, the only path is the one-step move $i\to i$, with weight $p_{ii}$.

The restriction $x_r\ne i$ is what makes the path a first-return path. A sequence with a zero-probability transition has weight zero and contributes nothing. If $S\setminus\{i\}$ is infinite, the sum below is a countable sum of nonnegative terms; for finite $S$, only finitely many paths occur at each fixed $n$.

Theorem (First-return path enumeration): For $n=1$, $f_i(1)=p_{ii}$. For each $n\ge2$, $$ f_i(n)= \sum_{(x_1,\ldots,x_{n-1})\in(S\setminus\{i\})^{n-1}} p_{i x_1}p_{x_1x_2}\cdots p_{x_{n-2}x_{n-1}}p_{x_{n-1}i}. $$

Proof. Fix $n\ge2$. For each sequence $(x_1,\ldots,x_{n-1})$ whose entries are not $i$, consider the event that $X_1=x_1,\ldots,X_{n-1}=x_{n-1},X_n=i$, given $X_0=i$. The Markov property gives this event probability $p_{i x_1}p_{x_1x_2}\cdots p_{x_{n-2}x_{n-1}}p_{x_{n-1}i}$. Since all the intermediate states differ from $i$, this event is contained in $\{T_i^+=n\}$. Conversely, on $\{T_i^+=n\}$, the states $X_1,\ldots,X_{n-1}$ all differ from $i$, so the outcome belongs to exactly one such path event. These path events are disjoint because two different state sequences cannot both describe the same values of $X_1,\ldots,X_{n-1}$. Adding their probabilities therefore gives $f_i(n)$. For $n=1$, a first return at step 1 is exactly the transition $i\to i$, which has probability $p_{ii}$. $\square$

This formula gives a direct procedure: choose the number of steps, list the intermediate states excluding $i$, discard paths with impossible transitions, multiply the transition probabilities on each remaining path, and add the weights. The order of the states matters: two different sequences are different paths, even if they use the same transitions in a different order. Self-loops at intermediate states are allowed as long as they are at states other than $i$.

Worked Path Enumerations

Worked Example: Returns in Two and Three Steps

Consider $S=\{a,b,c\}$, in that state order, with transition matrix $$ P= \begin{bmatrix} \tfrac14&\tfrac12&\tfrac14\\ \tfrac12&\tfrac12&0\\ \tfrac14&\tfrac14&\tfrac12 \end{bmatrix}. $$ Each row sums to $1$: $\tfrac14+\tfrac12+\tfrac14=1$, $\tfrac12+\tfrac12+0=1$, and $\tfrac14+\tfrac14+\tfrac12=1$. Starting at $a$, calculate the first-return probabilities at steps $1,2,3$.

At step $1$, the only first-return path is $a\to a$, so $f_a(1)=\tfrac14$. At step $2$, the intermediate state must be $b$ or $c$. The two admissible paths have weights $$ a\to b\to a:\ \tfrac12\cdot\tfrac12=\tfrac14,\qquad a\to c\to a:\ \tfrac14\cdot\tfrac14=\tfrac1{16}. $$ Thus $f_a(2)=\tfrac14+\tfrac1{16}=\tfrac5{16}$.

At step $3$, list the four ordered pairs of intermediate states in $\{b,c\}^2$. Their path weights are $$ \begin{aligned} a\to b\to b\to a &: \tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18,\\ a\to b\to c\to a &: \tfrac12\cdot0\cdot\tfrac14=0,\\ a\to c\to b\to a &: \tfrac14\cdot\tfrac14\cdot\tfrac12=\tfrac1{32},\\ a\to c\to c\to a &: \tfrac14\cdot\tfrac12\cdot\tfrac14=\tfrac1{32}. \end{aligned} $$ Adding the four values gives $f_a(3)=\tfrac18+0+\tfrac1{32}+\tfrac1{32}=\tfrac3{16}$.

Check: The three probabilities sum to $\tfrac14+\tfrac5{16}+\tfrac3{16}=\tfrac{12}{16}=\tfrac34$. This is the probability of a first return by step $3$; it need not equal $1$, because some paths have not returned by then.

Worked Example: A Loop Before the Return

Let $S=\{r,u,v\}$, with transitions $r\to u$ with probability $1$; from $u$, move to $u$ or $v$ with probability $\tfrac12$ each; and from $v$, move to $r$ with probability $1$. In the order $r,u,v$, $$ P= \begin{bmatrix} 0&1&0\\ 0&\tfrac12&\tfrac12\\ 1&0&0 \end{bmatrix}. $$ The row sums are $0+1+0=1$, $0+\tfrac12+\tfrac12=1$, and $1+0+0=1$. Find the first-return distribution to $r$.

There is no one-step return, so $f_r(1)=p_{rr}=0$. A return in two steps is also impossible: after the forced step $r\to u$, state $u$ cannot move directly to $r$, so $f_r(2)=0$. For any $n\ge3$, a first-return path must go from $r$ to $u$, make $k=n-3$ loops $u\to u$, then take $u\to v$ and $v\to r$. There is exactly one such state sequence for each $k\ge0$. Its weight is $$ 1\cdot\left(\tfrac12\right)^k\cdot\tfrac12\cdot1 =\left(\tfrac12\right)^{k+1}. $$ Consequently $f_r(n)=\left(\tfrac12\right)^{n-2}$ for $n\ge3$. In particular, $f_r(3)=\tfrac12$, from $r\to u\to v\to r$, and $f_r(4)=\tfrac14$, from $r\to u\to u\to v\to r$.

Check: The total probability of a first return at some finite step is $\sum_{n=3}^{\infty}f_r(n)=\sum_{k=0}^{\infty}(\tfrac12)^{k+1}=1$, by the geometric series formula. This also agrees with the path description: from $u$, the probability of making at least $m$ consecutive self-loops is $(\tfrac12)^m$, which tends to $0$, so the chain eventually takes the transition to $v$ with probability $1$.

Worked Example: Several Routes and a Direct Return

Let $S=\{0,1,2,3\}$ and use the matrix $$ P= \begin{bmatrix} \tfrac13&\tfrac13&\tfrac13&0\\ \tfrac12&0&\tfrac12&0\\ \tfrac14&\tfrac14&\tfrac14&\tfrac14\\ 1&0&0&0 \end{bmatrix}. $$ The row sums are $\tfrac13+\tfrac13+\tfrac13+0=1$, $\tfrac12+0+\tfrac12+0=1$, $\tfrac14+\tfrac14+\tfrac14+\tfrac14=1$, and $1+0+0+0=1$. Starting at $0$, enumerate the first-return probabilities at steps $1,2,3$.

The direct path $0\to0$ gives $f_0(1)=\tfrac13$. For a first return at step $2$, the intermediate state must be $1,2,$ or $3$. The path through $1$ has weight $\tfrac13\cdot\tfrac12=\tfrac16$; the path through $2$ has weight $\tfrac13\cdot\tfrac14=\tfrac1{12}$; and the path through $3$ has weight $0\cdot1=0$. Hence $f_0(2)=\tfrac16+\tfrac1{12}+0=\tfrac14$.

For a first return at step $3$, the first intermediate state cannot be $0$. The admissible paths with nonzero weight are $$ \begin{aligned} 0\to1\to2\to0 &: \tfrac13\cdot\tfrac12\cdot\tfrac14=\tfrac1{24},\\ 0\to2\to1\to0 &: \tfrac13\cdot\tfrac14\cdot\tfrac12=\tfrac1{24},\\ 0\to2\to2\to0 &: \tfrac13\cdot\tfrac14\cdot\tfrac14=\tfrac1{48},\\ 0\to2\to3\to0 &: \tfrac13\cdot\tfrac14\cdot1=\tfrac1{12}. \end{aligned} $$ The other possible intermediate pairs have zero weight: from $1$, the only nonzero transition that avoids $0$ goes to $2$; from $2$, its remaining transition to $0$ would return too early if taken at step $2$. Thus $f_0(3)=\tfrac1{24}+\tfrac1{24}+\tfrac1{48}+\tfrac1{12}=\tfrac9{48}=\tfrac3{16}$.

Check: The probability of a first return by step $3$ is $\tfrac13+\tfrac14+\tfrac3{16}=\tfrac{16}{48}+\tfrac{12}{48}+\tfrac9{48}=\tfrac{37}{48}$, which is at most $1$. The remaining probability $\tfrac{11}{48}$ consists of paths that have not yet returned by step $3$.

Why the Avoidance Condition Matters

A frequent error is to use the probability of being back at $i$ at time $n$, $\mathbb{P}_i(X_n=i)$, in place of $f_i(n)$. The former includes paths that returned earlier and then visited $i$ again. For the first example, at step $2$, the paths contributing to $\mathbb{P}_a(X_2=a)$ are $a\to a\to a$, $a\to b\to a$, and $a\to c\to a$. Their weights are $\tfrac14\cdot\tfrac14=\tfrac1{16}$, $\tfrac12\cdot\tfrac12=\tfrac14$, and $\tfrac14\cdot\tfrac14=\tfrac1{16}$. Therefore $\mathbb{P}_a(X_2=a)=\tfrac38$, not $f_a(2)$. The path $a\to a\to a$ has already returned at step $1$, so it is excluded from the first-return event; the correct value is $\tfrac14+\tfrac1{16}=\tfrac5{16}$.

For a fixed $n$, path enumeration is finite whenever $S$ is finite, but the number of candidate paths can grow rapidly with $n$. It is efficient to list only states outside the target between the start and end, and to remove paths as soon as they contain a zero-probability transition. Grouping paths with the same initial or final segment can also reduce arithmetic, provided each distinct path weight is still included exactly once. For a finite horizon $N$, the probability of a return by that time is $\mathbb{P}_i(T_i^+\le N)=\sum_{n=1}^{N}f_i(n)$: the events $\{T_i^+=n\}$ are disjoint, so their probabilities add. To obtain the probability of ever returning, take the increasing limit of these finite-horizon probabilities, equivalently the sum $\sum_{n\ge1}f_i(n)$.

Takeaway: A first-return probability is a sum of path weights, where every intermediate state must avoid the starting state. The transition probabilities along each admissible path are multiplied, and the resulting path weights are added.

Check Your Understanding

For each question, specify which intermediate states are allowed before calculating a first-return probability.

If $p_{ii}=\tfrac25$, what is the one-step first-return probability $f_i(1)$?
In a chain where $i\to a$ has probability $\tfrac13$ and $a\to i$ has probability $\tfrac12$, what contribution does the path $i\to a\to i$ make to $f_i(2)$?
Why is a path $i\to i\to a\to i$ excluded when calculating $f_i(3)$?
In the second worked example, what is the first-return probability at step $5$, and how many self-loops at $u$ does its path contain?
Explain why the sum of first-return probabilities through step $N$ cannot exceed $1$.

Path Enumeration for First Returns

What You'll Learn