Return Times and First-Return Events

Return Versus First Passage

A chain can visit a state many times, so the phrase “reach state $i$” needs care when the chain already starts at $i$. The first time the chain is in $i$, counting time zero, is then zero. A first return instead asks when the chain is in $i$ again after taking at least one step. The distinction determines which paths count and is essential when calculating the probability of a return at a specified time.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and let $(X_n)_{n\ge0}$ be a discrete-time Markov chain with countable state space $S$, transition matrix $P=(p_{jk})$, and filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. The matrix is row-stochastic: $p_{jk}=\mathbb{P}(X_{n+1}=k\mid X_n=j)$, and each row sums to $1$. Write $\mathbb{P}_j$ for probabilities when $X_0=j$.

Definition: For a state $i\in S$, the first return time to $i$ is $T_i^+=\inf\{n\ge1:X_n=i\}$, with $\inf\varnothing=\infty$. The first-return event at step $n\ge1$ is $\{T_i^+=n\}$. For a different starting state $j\ne i$, the first-passage time to $i$ is $T_{\{i\}}=\inf\{n\ge0:X_n=i\}$. It counts the first visit to $i$, not a return to the starting state.

Since $X_0=j\ne i$, a first-passage time to $i$ from $j$ cannot be zero. By contrast, if the chain starts at $i$, then $T_{\{i\}}=0$, whereas $T_i^+$ is at least $1$. A first-return event at time $n$ also excludes paths that visit $i$ at any intermediate time $1,\ldots,n-1$. The endpoint must be $i$, but every intermediate state must be in $S\setminus\{i\}$.

The Transition-Path Formula

For a specified sequence of states, the Markov property gives its path probability as the product of its one-step transition probabilities. A first return at time $n$ is made up of exactly those paths that start at $i$, end at $i$ after $n$ transitions, and have no intermediate state equal to $i$. Summing the path probabilities gives the following formula.

Theorem (First-return path formula): For a discrete-time Markov chain on a countable state space $S$, a state $i\in S$, and $n\ge1$, $$ \mathbb{P}_i(T_i^+=n)= \begin{cases} p_{ii}, & n=1,\\[4pt] \displaystyle\sum_{i_1,\ldots,i_{n-1}\in S\setminus\{i\}} p_{i i_1}p_{i_1 i_2}\cdots p_{i_{n-2}i_{n-1}}p_{i_{n-1}i}, & n\ge2. \end{cases} $$ The sum is over all ordered choices of intermediate states, including choices whose path probability is zero.

Proof. Fix $n\ge2$. For each sequence $i_1,\ldots,i_{n-1}\in S\setminus\{i\}$, consider the event $\{X_1=i_1,\ldots,X_{n-1}=i_{n-1},X_n=i\}$ under $\mathbb{P}_i$. These events are disjoint for distinct sequences, and their union is exactly $\{T_i^+=n\}$: the endpoint is $i$, and the restriction $i_r\ne i$ for every intermediate time $r$ rules out any earlier return. Repeated conditioning using the Markov property gives the probability of each such path as $p_{i i_1}p_{i_1 i_2}\cdots p_{i_{n-2}i_{n-1}}p_{i_{n-1}i}$. Countable additivity over the disjoint paths proves the formula for $n\ge2$. For $n=1$, the event is exactly $\{X_1=i\}$ when $X_0=i$, which has probability $p_{ii}$. $\square$

The sum is finite when $S$ is finite. For countable $S$, it is a countable sum of nonnegative terms, so it is well-defined. The intermediate-state restriction is the defining feature: paths that arrive at $i$ early and then leave do not contribute to a first return at their final time.

Proposition: For any $n\ge1$, $\mathbb{P}_i(T_i^+=n)>0$ if and only if there is at least one length-$n$ path from $i$ back to $i$ whose intermediate states all lie in $S\setminus\{i\}$ and whose transition probabilities are all positive.

Proof. For $n=1$, the assertion follows from $\mathbb{P}_i(T_i^+=1)=p_{ii}$. For $n\ge2$, the path formula expresses the probability as a sum of nonnegative path products. If one eligible path has all its transition probabilities positive, its product is positive, so the sum is positive. Conversely, if every eligible path has a zero transition probability, every product in the sum is zero and the sum is zero. Thus a positive first-return probability is equivalent to the existence of an eligible positive-probability path. $\square$

Worked Path Calculations

Worked Example: Return to State 1 in Two Steps

Consider a chain on $S=\{1,2,3\}$ with transition matrix $$ P=\begin{bmatrix} \tfrac14&\tfrac12&\tfrac14\\ \tfrac12&0&\tfrac12\\ \tfrac13&\tfrac13&\tfrac13 \end{bmatrix}. $$ Every row sums to $1$: row 1 has $\tfrac14+\tfrac12+\tfrac14=1$, row 2 has $\tfrac12+0+\tfrac12=1$, and row 3 has $\tfrac13+\tfrac13+\tfrac13=1$. Find the probabilities of a first return to state $1$ at steps $1$ and $2$.

At step $1$, the chain must move directly from $1$ to $1$, so $\mathbb{P}_1(T_1^+=1)=p_{11}=\tfrac14$. At step $2$, the only allowed intermediate states are $2$ and $3$. The two paths are $1\to2\to1$ and $1\to3\to1$. Their probabilities are $\tfrac12\cdot\tfrac12=\tfrac14$ and $\tfrac14\cdot\tfrac13=\tfrac1{12}$, respectively. Therefore $\mathbb{P}_1(T_1^+=2)=\tfrac14+\tfrac1{12}=\tfrac13$.

Check: The two length-2 paths have total probability $\tfrac13$. The other possible intermediate state at time 1 is state $1$, but paths that visit $1$ at time 1 cannot be first returns at time 2. For example, $1\to1\to1$ has probability $\tfrac14\cdot\tfrac14=\tfrac1{16}$, and is excluded from the first-return event at step 2.

Worked Example: A Deterministic Three-State Cycle

Let $S=\{1,2,3\}$, and let the chain move from $1$ to $2$, from $2$ to $3$, and from $3$ to $1$, each with probability $1$. Thus $$ P=\begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix}. $$ Each row sums to $1$: the row sums are $0+1+0=1$, $0+0+1=1$, and $1+0+0=1$. Starting at state $1$, calculate the first-return probabilities at steps $1,2,3$, and compare with first passage to $1$ from state $2$.

There is no transition from $1$ directly to $1$, so $\mathbb{P}_1(T_1^+=1)=p_{11}=0$. At step $2$, the only possible path is $1\to2\to3$, which ends at $3$, not $1$; hence $\mathbb{P}_1(T_1^+=2)=0$. At step $3$, the only path is $1\to2\to3\to1$. Its probability is $1\cdot1\cdot1=1$, so $\mathbb{P}_1(T_1^+=3)=1$.

Starting instead from state $2$, the first passage to state $1$ takes two steps along $2\to3\to1$, so its probability of occurring at step $2$ is $1$. This is not a first return to $2$: the chain starts at $2$ and returns to $2$ only after the additional transition $1\to2$, at step $3$.

Check: The path from $1$ returns to $1$ at step $3$, and the path from $2$ first reaches $1$ at step $2$. The different starting states and target conditions give different events, even though both calculations follow the same sequence of deterministic transitions.

Worked Example: Several First-Return Paths at Step 3

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

There is no self-transition from $0$, so $\mathbb{P}_0(T_0^+=1)=0$. At step $2$, the allowed intermediate states are $1$ and $2$. The path $0\to1\to0$ has probability $\tfrac12\cdot\tfrac13=\tfrac16$, and $0\to2\to0$ has probability $\tfrac12\cdot\tfrac12=\tfrac14$. Thus $\mathbb{P}_0(T_0^+=2)=\tfrac16+\tfrac14=\tfrac5{12}$.

For step $3$, both intermediate states must again avoid $0$. The possible ordered pairs are $(1,1),(1,2),(2,1),(2,2)$. The pair $(1,1)$ gives the path $0\to1\to1\to0$, with probability $\tfrac12\cdot\tfrac23\cdot\tfrac13=\tfrac19$. The pair $(1,2)$ contributes zero because $p_{12}=0$. The pair $(2,1)$ contributes zero because $p_{21}=0$. The pair $(2,2)$ gives $0\to2\to2\to0$, with probability $\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18$. Therefore $\mathbb{P}_0(T_0^+=3)=\tfrac19+\tfrac18=\tfrac{17}{72}$.

Check: The two nonzero step-3 path probabilities sum to $\tfrac19+\tfrac18=\tfrac8{72}+\tfrac9{72}=\tfrac{17}{72}$. The two other eligible paths have zero probability, so they do not change the total.

A Common Miscalculation

A diagonal entry $p_{ii}^{(n)}$ of $P^n$ gives the probability of being at $i$ at time $n$ when starting at $i$. It does not generally give the probability of a first return at time $n$, because the chain may have visited $i$ earlier and then left. The following calculation shows the difference concretely.

Common mistake: In the first example, one might identify $\mathbb{P}_1(T_1^+=2)$ with $p_{11}^{(2)}$. The two-step paths contributing to $p_{11}^{(2)}$ have intermediate state $1$, $2$, or $3$, so $p_{11}^{(2)}=\tfrac14\cdot\tfrac14+\tfrac12\cdot\tfrac12+\tfrac14\cdot\tfrac13=\tfrac1{16}+\tfrac14+\tfrac1{12}=\tfrac{19}{48}$. The first term counts the path $1\to1\to1$, which already returned at step $1$, so it is not a first return at step $2$. The correct first-return probability is only the contribution from intermediate states $2$ and $3$: $\tfrac14+\tfrac1{12}=\tfrac13$. Thus $p_{11}^{(2)}=\tfrac{19}{48}$ and $\mathbb{P}_1(T_1^+=2)=\tfrac13=\tfrac{16}{48}$ differ by the probability $\tfrac3{48}=\tfrac1{16}$ of the excluded path.

The practical rule is to write the event before summing paths: the chain starts at $i$, avoids $i$ at every intermediate time, and is at $i$ at the specified endpoint. For a first passage from $j\ne i$, the chain instead starts at $j$ and avoids the target $i$ until its first visit. Distinguishing the starting state, target, and intermediate-time restriction prevents the two questions from being conflated.

Check Your Understanding

For each question, specify the starting state and the intermediate-state restriction before calculating.

In the three-state chain with matrix $\begin{bmatrix}\tfrac14&\tfrac12&\tfrac14\\\tfrac12&0&\tfrac12\\\tfrac13&\tfrac13&\tfrac13\end{bmatrix}$, what is $\mathbb{P}_1(T_1^+=1)$?
In that same chain, list the paths contributing to $\mathbb{P}_1(T_1^+=2)$, and explain why $1\to1\to1$ is excluded.
For a chain started at $j\ne i$, why is the first-passage time to $i$ not a return time to $i$?
In the deterministic cycle $1\to2\to3\to1$, at which step does the first return to $1$ occur? At which step is $1$ first reached from $2$?
State the condition on intermediate states in the path formula for $\mathbb{P}_i(T_i^+=n)$, and explain what goes wrong if it is omitted.

Return Times and First-Return Events

What You'll Learn