Return Times and Positive Recurrence

Return Cycles Measure Time, Not Just Jumps

For a continuous-time Markov chain, counting transitions and measuring elapsed time are different tasks. A chain may return to a state after finitely many jumps, yet spend so long at some states along the way that its expected return duration is infinite. The distinction matters whenever recurrence is used to describe long-run behavior: recurrence concerns whether return occurs, while positive recurrence also controls the expected time it takes.

Let $(X_t)_{t\ge0}$ be a nonexplosive, conservative continuous-time Markov chain on a countable state space $S$, with generator $Q=(q_{ij})$. Conservativeness means each row of $Q$ sums to zero. Write $q_i=-q_{ii}=\sum_{j\ne i}q_{ij}$ for the exit rate from $i$. For now, work in a closed communicating class $C\subseteq S$ with $0<q_i<\infty$ for every $i\in C$. Closed means that the chain cannot leave $C$; communicating means each state in $C$ can be reached from every other state in $C$ with positive probability.

Starting from $i\in C$, let $0=T_0<T_1<T_2<\cdots$ be the jump times, and let $Y_n=X_{T_n}$ be the embedded jump chain. Its transition probabilities are $r_{ij}=q_{ij}/q_i$ for $j\ne i$, and $r_{ii}=0$. The holding time $H_n=T_{n+1}-T_n$, conditional on $Y_n=j$, has an exponential distribution with rate $q_j$, and hence mean $1/q_j$. The jump destination and the holding time are conditionally independent given the current state.

Definition: The jump-chain return step to $i$ is $R_i^+=\inf\{n\ge1:Y_n=i\}$. The continuous-time return duration is $C_i=T_{R_i^+}$, with $C_i=\infty$ if $R_i^+=\infty$. This definition starts counting after the chain leaves $i$: defining a return as $\inf\{t>0:X_t=i\}$ would give zero, because the chain initially holds at $i$. The state $i$ is recurrent if $\mathbb{P}_i(C_i<\infty)=1$, and positive recurrent if it is recurrent and $\mathbb{E}_i[C_i]<\infty$. A recurrent state with infinite expected return duration is called null recurrent.

Under the assumptions above, every holding time is finite almost surely, and nonexplosion ensures that infinitely many jumps cannot occur in finite time. Thus a return after finitely many jump steps occurs at a finite time; conversely, a return at a finite time must occur at a finite jump step. The formula below makes the additional requirement for positive recurrence explicit.

Expected Duration of a Return Cycle

Theorem (Expected return-cycle duration): In the closed class described above, for each $i\in C$, $$ \mathbb{E}_i[C_i] =\mathbb{E}_i\left[\sum_{n=0}^{R_i^+-1}\frac{1}{q_{Y_n}}\right] =\sum_{n=0}^{\infty}\mathbb{E}_i\left[\frac{\mathbf{1}_{\{R_i^+>n\}}}{q_{Y_n}}\right]. $$ These equalities hold with values in $[0,\infty]$. In particular, $i$ is positive recurrent exactly when $R_i^+<\infty$ almost surely and the displayed expected sum is finite.

Proof. On the event $R_i^+<\infty$, the return duration is the sum of the holding times before the return: $C_i=\sum_{n=0}^{R_i^+-1}H_n$. If $R_i^+=\infty$, the same sum over all $n\ge0$ is infinite almost surely: each holding time is strictly positive almost surely, and nonexplosion means their sum cannot be finite. Therefore, in the extended nonnegative sense, $$ C_i=\sum_{n=0}^{\infty}\mathbf{1}_{\{R_i^+>n\}}H_n. $$ The event $\{R_i^+>n\}$ is determined by $Y_0,\ldots,Y_n$. Conditional on the jump-chain states through $Y_n$, $H_n$ has mean $1/q_{Y_n}$. It follows that $\mathbb{E}_i[\mathbf{1}_{\{R_i^+>n\}}H_n] =\mathbb{E}_i[\mathbf{1}_{\{R_i^+>n\}}/q_{Y_n}]$. Summing these nonnegative terms and applying Tonelli’s theorem gives both equalities, including when the sum diverges. By definition, positive recurrence requires an almost-sure return and finite expected duration, which is precisely the final criterion. $\square$

The formula weights each visited state by its mean holding time. It is not enough to know how many jumps occur on average, and recurrence alone does not ensure a finite expected cycle duration. The following examples separate these issues.

Worked Example: A Two-State Return Cycle

Consider states $0,1$, with generator $$ Q=\begin{bmatrix}-2&2\\[2pt]\tfrac12&-\tfrac12\end{bmatrix}. $$ The first row sums to $-2+2=0$, and the second to $\tfrac12-\tfrac12=0$; both exit rates are positive. From either state, the next jump goes deterministically to the other state, so the embedded chain returns to $0$ after exactly two jumps. Its holding rates on that cycle are $q_0=2$ and $q_1=\tfrac12$.

The cycle consists of one holding time at $0$, followed by one at $1$. Applying the formula gives $$ \mathbb{E}_0[C_0]=\frac{1}{q_0}+\frac{1}{q_1} =\frac12+2=\frac52. $$ The embedded return step is $R_0^+=2$, so the expected number of jumps before return is $2$; that count is not the expected elapsed time. Check: the first holding mean is $1/2$, the second is $2$, and their sum is $5/2$, as given by the cycle formula.

Worked Example: A Finite Three-State Cycle

On $C=\{0,1,2\}$, let the chain move $0\to1$ at rate $2$, $1\to2$ at rate $4$, and $2\to0$ at rate $1$. Its generator is $$ Q=\begin{bmatrix} -2&2&0\\ 0&-4&4\\ 1&0&-1 \end{bmatrix}. $$ The row sums are $-2+2=0$, $0-4+4=0$, and $1+0-1=0$, respectively, and the exit rates are $2,4,1$. The embedded chain follows the deterministic cycle $0,1,2,0$, so $R_0^+=3$.

The expected return duration is the sum of the three holding-time means: $$ \mathbb{E}_0[C_0]=\frac12+\frac14+1=\frac74. $$ Check: substituting the exit rates into the theorem gives $1/q_0+1/q_1+1/q_2=1/2+1/4+1=7/4$. Each state is positive recurrent: each return cycle contains exactly these three finite-mean holding times, with the cycle started at whichever state is being considered.

A tempting but incorrect calculation is to use only $1/q_0=1/2$ as the mean return duration. That is the mean of the initial holding time, not the return cycle. The chain must also hold at states $1$ and $2$ before it returns to $0$; including both gives $7/4$.

Recurrence Does Not Guarantee Positive Recurrence

When all exit rates are positive and the chain is nonexplosive, recurrence of the jump chain is equivalent to almost-sure return in continuous time. It does not, by itself, imply that the mean duration of that return is finite. The next example establishes this distinction. Its proof includes the recurrence argument because a path that avoids the target need not necessarily travel arbitrarily far; it could instead remain in a bounded set forever.

Worked Example: A Recurrent Chain with Infinite Mean Return Duration

Take $S=\mathbb{Z}$ and define a continuous-time chain that jumps from each $k$ to $k-1$ and $k+1$ at rate $1$ each. Its generator has $q_{k,k}=-2$, $q_{k,k-1}=q_{k,k+1}=1$, and all other entries zero; every row sums to $-2+1+1=0$. The exit rate is $q_k=2$ for every $k$. The embedded chain is the simple symmetric random walk on the integers, and each holding time has mean $1/2$.

First, the jump chain returns to $0$ almost surely. Starting at $1$, fix an integer $N>1$, and consider the walk until it hits $0$ or $N$. If $h_k$ is the probability of hitting $N$ before $0$ from $k$, then $h_0=0$, $h_N=1$, and for $1\le k<N$, $h_k=(h_{k-1}+h_{k+1})/2$. This equation says the successive differences $h_{k+1}-h_k$ are constant. The boundary values therefore give $h_k=k/N$, in particular $h_1=1/N$.

For this fixed $N$, the probability of staying forever in $\{1,\ldots,N-1\}$ is zero. From any state in that set, $N-1$ consecutive left steps would hit $0$; the probability of those steps is $2^{-(N-1)}$. In successive blocks of $N-1$ steps, conditional on still being in the set at the start of a block, the chance of exiting by the end is at least $2^{-(N-1)}$. Thus the probability of surviving $m$ such blocks is at most $(1-2^{-(N-1)})^m$, which tends to zero. Consequently, the probability of never hitting $0$ is at most the probability of hitting $N$ before $0$, namely $1/N$. This holds for every $N>1$; letting $N$ increase proves that the probability of never hitting $0$ is zero. Starting at $0$, the first jump is to $1$ or $-1$; by symmetry and translation, either starting point returns to $0$ almost surely. Hence the jump chain, and therefore the continuous-time chain, returns to $0$ almost surely.

Next, its expected number of return steps is infinite. Suppose instead that $\mathbb{E}_0[R_0^+]<\infty$. For $j\in\mathbb{Z}$, define the expected number of visits to $j$ before the return by $u_j=\mathbb{E}_0[\sum_{n=0}^{R_0^+-1}\mathbf{1}_{\{Y_n=j\}}]$. Then $\sum_j u_j=\mathbb{E}_0[R_0^+]<\infty$, and $\sum_j u_j\ge1$ because the cycle includes $Y_0=0$. For any $j$, conditioning on $Y_n$ at each step before return gives $$ \sum_k u_k r_{kj} =\mathbb{E}_0\left[\sum_{n=0}^{R_0^+-1}\mathbf{1}_{\{Y_{n+1}=j\}}\right] =u_j. $$ For the last equality, the visits counted on the middle expression have indices $1,\ldots,R_0^+$; the definition of $u_j$ counts indices $0,\ldots,R_0^+-1$. The endpoints agree, since $Y_0=Y_{R_0^+}=0$, so replacing one index range by the other leaves each state’s count unchanged. All sums are justified by the assumed finite expected return step count.

Thus $\pi_j=u_j/\mathbb{E}_0[R_0^+]$ would be a probability distribution satisfying $\pi_j=\sum_k\pi_k r_{kj}$. For the simple symmetric walk this says $\pi_j=(\pi_{j-1}+\pi_{j+1})/2$. The differences $\pi_j-\pi_{j-1}$ must therefore be constant over all integers. A nonnegative summable sequence can satisfy this relation only if it is identically zero: a nonzero constant difference would make the sequence fail to be nonnegative or summable in one direction, and a zero difference makes it constant, which is summable only when the constant is zero. That contradicts $\sum_j\pi_j=1$. Hence $\mathbb{E}_0[R_0^+]=\infty$.

Since every holding time has mean $1/2$, the cycle formula gives $\mathbb{E}_0[C_0]=\tfrac12\mathbb{E}_0[R_0^+]=\infty$. This chain is recurrent but not positive recurrent. The chain is nonexplosive: its holding times are independent exponential variables with rate $2$, whose sum is infinite almost surely.

Conditions and Common Pitfalls

The assumption that the class is closed and all its exit rates are positive keeps the embedded-chain formula well-defined throughout the return cycle. If a chain can enter an absorbing state, then $q_j=0$ there and $1/q_j$ is not a valid holding-time mean. For example, with $Q=\begin{bmatrix}-1&1\\0&0\end{bmatrix}$, a chain starting at state $0$ jumps to absorbing state $1$ and never returns to $0$. One must not apply the cycle sum using $1/q_1$. The theorem as stated avoids that case; a treatment that allows absorbing states must separately account for the infinite time spent there.

Keep the following distinctions in view:

Return probability asks whether the chain returns with probability one. Positive recurrence additionally requires finite expected return duration.
Jump count depends on the embedded chain. Elapsed time also depends on the holding rates encountered along the cycle.
The mean initial holding time $1/q_i$ is only one term in a return-cycle calculation; it is not generally the mean return duration.
The return must be defined after departure from $i$, not as the first positive real time at which $X_t=i$, since the chain holds at $i$ immediately after starting there.

The cycle-duration formula is useful because it separates the path of the embedded chain from the clock that runs at each state. A recurrent jump chain gives almost-sure return in real time under the stated nonexplosion and positive-rate assumptions, but the holding-time weights decide whether that return has a finite mean. This is the precise distinction between recurrence and positive recurrence for the return cycles considered here.

Check Your Understanding

Use the definitions and cycle formula to answer the following. When checking a numerical result, include every holding-time term that occurs before the return.

In a two-state chain that jumps $0\to1$ at rate $3$ and $1\to0$ at rate $2$, find the mean return duration to $0$.
Why is $\inf\{t>0:X_t=i\}$ not an appropriate return-time definition for a chain started at $i$?
State the expected return-cycle formula in terms of $R_i^+$, $Y_n$, and $q_{Y_n}$.
For the three-state cycle with rates $2,4,1$, identify the incorrect step in the claim that the mean return duration to $0$ is $1/2$.
What property of the embedded jump chain is established in the symmetric-walk example, and what separate fact shows that the state is not positive recurrent?

Return Times and Positive Recurrence

What You'll Learn