Eventual Return Probability and Repeated Returns

One Return Determines Repeated Returns

A chain may return to a state after one step, after many steps, or not at all. If it does return, the Markov property says that its future, from that return onward, has the same transition law as a fresh chain started at the state. This makes the probability of repeated returns depend on a single quantity: the probability of returning at least once.

Let $(X_n)_{n\ge0}$ be a time-homogeneous discrete-time 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_{jk})$. Thus each row of $P$ sums to $1$. Use the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. Write $\mathbb{P}_i$ for probability when $X_0=i$, and define the first return time to $i$ by $T_i^+=\inf\{n\ge1:X_n=i\}$, with $\inf\varnothing=\infty$.

Definition: The eventual return probability of state $i$ is $f_i=\mathbb{P}_i(T_i^+<\infty)$. Define $R_0=0$ and, recursively, $R_{r+1}=\inf\{n>R_r:X_n=i\}$ when $R_r<\infty$; if $R_r=\infty$, set $R_{r+1}=\infty$. Thus $R_r<\infty$ means that at least $r$ returns to $i$ have occurred.

The strict inequality $n>R_r$ matters: $R_{r+1}$ is a new return, not the return at time $R_r$ counted again. When the chain starts at $i$, the eventual return probability is precisely the probability of one or more returns after time $0$.

The Markov Property at a Return Time

Return times are random, so applying the Markov property at them requires a result beyond conditioning at a fixed time. In discrete time, the needed statement follows from the ordinary Markov property and a sum over the possible values of the stopping time.

Lemma (Markov property at a stopping time): Let $\tau$ be a stopping time for $(\mathcal{F}_n)$. On the event $\tau<\infty$, conditional on the history through time $\tau$, the future chain has the law of a chain started at $X_\tau$. In particular, if $X_\tau=i$, the conditional probability of a return to $i$ at some strictly later time is $f_i$.

Proof. First fix a finite future path $x_0,x_1,\ldots,x_m$ in $S$ and an event $A\in\mathcal{F}_\tau$. For each $n$, $A\cap\{\tau=n\}\in\mathcal{F}_n$. The ordinary Markov property at deterministic time $n$ therefore gives the conditional probability of the specified path after time $n$ as $\prod_{\ell=0}^{m-1}p_{x_\ell x_{\ell+1}}$, when $X_n=x_0$. Summing over $n\ge0$ shows that the conditional probabilities of every finite future path, given the history through $\tau$ and $X_\tau=x_0$, are those of a chain started at $x_0$. For a return to $i$, the event that the first future return occurs at lag $m$ is determined by the finite path through lag $m$. These events, for $m\ge1$, are disjoint, and their union is the event of a finite future return. Summing their conditional probabilities proves the final assertion. $\square$

Each $R_r$ is a stopping time: the event that the next return has occurred by time $n$ can be determined from $X_0,\ldots,X_n$ and the earlier return time. Consequently, the lemma applies at every finite $R_r$. The next result makes the repeated-return calculation exact.

Theorem (Repeated-return formula): For every state $i$ and integer $r\ge0$, $$ \mathbb{P}_i(R_r<\infty)=f_i^r, $$ where $f_i^0=1$. Consequently, the probability of infinitely many returns to $i$ is $1$ if $f_i=1$, and $0$ if $f_i<1$.

Proof. For $r=0$, $R_0=0$, so $\mathbb{P}_i(R_0<\infty)=1=f_i^0$. Suppose $r\ge0$. On $\{R_r<\infty\}$, the chain is at $i$ at time $R_r$. By the stopping-time lemma, conditional on the history through $R_r$, the probability of at least one further return is $f_i$. Thus $$ \mathbb{P}_i(R_{r+1}<\infty)=f_i\,\mathbb{P}_i(R_r<\infty). $$ Induction gives $\mathbb{P}_i(R_r<\infty)=f_i^r$ for every $r$. The events $\{R_r<\infty\}$ decrease as $r$ increases, and their intersection is the event of infinitely many returns. Continuity of probability for decreasing events gives probability $\lim_{r\to\infty}f_i^r$, which equals $1$ when $f_i=1$ and $0$ when $0\le f_i<1$. $\square$

With the usual classification, $i$ is recurrent when $f_i=1$ and transient when $f_i<1$. The theorem says more than whether the first return occurs: it gives the probability of reaching every successive return. It does not say that returns occur at consecutive times, or that the probability of returning at the next step equals $f_i$.

Worked Examples

Worked Example: A Return Followed by Possible Absorption

Consider a chain on $S=\{0,1,2\}$ with transition matrix $$ P=\begin{bmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ 0&0&1 \end{bmatrix}. $$ Starting from $0$, find the probability of at least one return, at least two returns, and infinitely many returns to $0$.

Check the rows before using the matrix: the row sums are $0+1+0=1$, $\tfrac12+0+\tfrac12=1$, and $0+0+1=1$. From state $0$, the first step goes to $1$ with probability $1$. From state $1$, the next step returns to $0$ with probability $\tfrac12$, and goes to the absorbing state $2$ with probability $\tfrac12$. Hence $f_0=1\cdot\tfrac12=\tfrac12$.

The theorem gives $$ \mathbb{P}_0(R_1<\infty)=\tfrac12,\qquad \mathbb{P}_0(R_2<\infty)=\left(\tfrac12\right)^2=\tfrac14,\qquad \mathbb{P}_0(R_3<\infty)=\left(\tfrac12\right)^3=\tfrac18. $$ Because $\lim_{r\to\infty}(\tfrac12)^r=0$, the probability of infinitely many returns is $0$.

Check: To have two returns, the chain must make the excursion $0\to1\to0$ twice, with probability $(1\cdot\tfrac12)(1\cdot\tfrac12)=\tfrac14$. This agrees with $f_0^2$. The chain can return once, but after each return there remains probability $\tfrac12$ of being absorbed before another return.

Worked Example: Repeated Returns in a Periodic Chain

Let $S=\{0,1\}$ and $$ P=\begin{bmatrix}0&1\\1&0\end{bmatrix}. $$ Starting from $0$, find the probability of at least $r$ returns for any integer $r\ge1$, and explain when those returns occur.

Both row sums are $0+1=1$, so $P$ is a transition matrix. The path is deterministic: it alternates $0,1,0,1,\ldots$. The first return to $0$ is at time $2$, so $f_0=1$. The repeated-return formula gives $\mathbb{P}_0(R_r<\infty)=1^r=1$ for every $r\ge1$. In fact, the $r$-th return occurs at time $2r$.

Check: The path at times $0,1,2,3,4$ is $0,1,0,1,0$, so the first two returns occur at times $2$ and $4$. This verifies the timing and shows that probability one of repeated returns does not require a return at every step.

Worked Example: A Finite Number of Returns

Suppose $f_i=\tfrac23$. Find the probability of exactly two returns to $i$, and the probability of at least four returns.

The events of at least $r$ returns are nested. Thus exactly two returns means at least two but not at least three. Using the theorem, $$ \mathbb{P}_i(\text{exactly two returns}) =\mathbb{P}_i(R_2<\infty)-\mathbb{P}_i(R_3<\infty) =\left(\tfrac23\right)^2-\left(\tfrac23\right)^3 =\tfrac49-\tfrac8{27} =\tfrac4{27}. $$ At least four returns has probability $$ \mathbb{P}_i(R_4<\infty)=\left(\tfrac23\right)^4=\tfrac{16}{81}. $$ The probability of exactly two returns can also be read as $(\tfrac23)^2(1-\tfrac23)=\tfrac49\cdot\tfrac13=\tfrac4{27}$: two returns occur, followed by no further return.

Check: Subtracting the probability of at least three returns, $\tfrac8{27}$, from the probability of at least two, $\tfrac49=\tfrac{12}{27}$, gives $\tfrac4{27}$, as required. These calculations concern return probabilities only; they do not give an expected number of returns.

Why the Immediate Transition Is Not the Whole Story

A common mistake is to use $p_{ii}$ as the probability of ever returning to $i$. The entry $p_{ii}$ is only the probability of returning in one step. An eventual return can instead occur after several transitions through other states.

In the first example, $p_{00}=0$, because the chain must move from $0$ to $1$ on its first step. Nevertheless, $f_0=\tfrac12$, since the transition $1\to0$ produces a return at time $2$ with probability $\tfrac12$. The incorrect calculation $f_0=p_{00}=0$ would predict that a return is impossible; the two-step path shows why that conclusion is false.

The distinction also works in the other direction: a positive self-transition contributes to an eventual return, but it need not account for every way to return. The quantity $f_i$ summarizes all possible finite paths that return to $i$ after time $0$. Once its value is known, the repeated-return formula applies without requiring a separate path enumeration for each number of returns.

Takeaway: For a chain started at $i$, each finite return restarts the same return experiment. Therefore the probability of at least $r$ returns is $f_i^r$, and infinitely many returns occur with probability one exactly when $f_i=1$.

Check Your Understanding

Use the definitions and repeated-return formula to answer the following questions.

If $f_i=\tfrac14$, what is the probability of at least three returns to $i$?
In the two-state alternating chain, why is the eventual return probability $1$ even though $p_{00}=0$?
If $\mathbb{P}_i(R_2<\infty)=\tfrac9{25}$, what is $f_i$? Assume the repeated-return formula applies.
For $f_i=\tfrac35$, compute the probability of exactly one return by subtracting nested events.
Explain why $R_{r+1}$ must be defined using times strictly greater than $R_r$.

Eventual Return Probability and Repeated Returns

What You'll Learn