Markov Chain Regeneration at Return Times

Returns as Regeneration Times

A Markov chain may revisit a state many times, and each return can provide a natural boundary between cycles. Starting at a particular state, the chain has the same transition law after each return. This makes return cycles useful for organizing path calculations: their lengths and the numbers of visits to states in a cycle can often be found by enumerating a small set of paths. A return to a set is more delicate, because the chain may return at different states, with different future laws.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite or countable state space $S$, defined on $(\Omega,\mathcal{F},\mathbb{P})$, with transition matrix $P=(p_{ij})$. The rows of $P$ sum to $1$. Use the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. For a state $i$, under $\mathbb{P}_i$ the chain starts at $i$; define its first return time by $T_i^+=\inf\{n\ge1:X_n=i\}$.

Definition: Suppose $X_0=i$ and the chain returns to $i$ almost surely. Set $T_0=0$ and recursively $T_{r+1}=\inf\{n>T_r:X_n=i\}$, for $r\ge0$. The $r$th return cycle has length $L_r=T_{r+1}-T_r$. Its state-visit count for $j\in S$ is $C_r(j)=\sum_{n=T_r}^{T_{r+1}-1}\mathbf{1}_{\{X_n=j\}}$. The terminal state $X_{T_{r+1}}=i$ belongs to the next cycle, not the current one. Thus $\sum_{j\in S}C_r(j)=L_r$.

The endpoint convention matters. A cycle starts at $i$, but its return endpoint is excluded, so that the shared return state is not counted twice. For a single-state return, every cycle has exactly one visit to $i$, and its other visits are to states encountered strictly between the two returns.

The Markov Property at a Return Time

The ordinary Markov property conditions at a fixed time. To justify regeneration, we need its discrete-time stopping-time version. A random time $T$ is a stopping time for $(\mathcal{F}_n)$ if $\{T\le n\}\in\mathcal{F}_n$ for every $n$. Write $\mathcal{F}_T$ for the information available at $T$: an event $A$ belongs to $\mathcal{F}_T$ when $A\cap\{T=n\}\in\mathcal{F}_n$ for each $n$.

Proposition (Markov property at an almost surely finite stopping time): Let $T$ be a stopping time with $\mathbb{P}(T<\infty)=1$. For any $A\in\mathcal{F}_T$, any $m\ge1$, and any states $x_1,\ldots,x_m\in S$, $$ \mathbb{P}\bigl(A,\ X_{T+1}=x_1,\ldots,X_{T+m}=x_m\bigr) =\sum_{n\ge0}\sum_{x\in S}\mathbb{P}(A,T=n,X_n=x)\, \mathbb{P}_x(X_1=x_1,\ldots,X_m=x_m). $$ In particular, if $X_T=i$ almost surely, the conditional future after $T$, given $\mathcal{F}_T$, has the law of a chain started at $i$.

Proof. Since $T$ is finite almost surely, the event on the left is the disjoint union over $n\ge0$ and $x\in S$ of the events where $A$, $T=n$, and $X_n=x$ hold, together with the specified future path. On $\{T=n\}$, $A\cap\{T=n\}\in\mathcal{F}_n$. The ordinary Markov property at the deterministic time $n$ therefore gives $\mathbb{P}(A,T=n,X_n=x,X_{n+1}=x_1,\ldots,X_{n+m}=x_m) =\mathbb{P}(A,T=n,X_n=x)\mathbb{P}_x(X_1=x_1,\ldots,X_m=x_m)$. Summing these disjoint probabilities proves the identity. If $X_T=i$ almost surely, all terms with $x\ne i$ vanish, and the remaining factor for the future path is the fixed number $\mathbb{P}_i(X_1=x_1,\ldots,X_m=x_m)$. This is the claimed conditional law. $\square$

Theorem (Return cycles are iid): Suppose $\mathbb{P}_i(T_i^+<\infty)=1$. For the chain started at $i$, the successive cycle lengths $L_0,L_1,\ldots$ and the corresponding within-cycle paths $(X_{T_r},\ldots,X_{T_{r+1}-1})$ are independent and identically distributed. In particular, the cycle visit-count vectors $(C_r(j))_{j\in S}$ are iid across $r$.

Proof. Each $T_r$ is a stopping time: $T_0=0$, and after a stopping time $T_r$, the event that the next return has occurred by time $n$ is determined by the states up to $n$. Inductively, the stopping-time proposition applies at every $T_r$, once $T_r$ is finite. The first return is finite almost surely by assumption. If $T_r$ is finite, the stopping-time proposition says that the chain after $T_r$, given $\mathcal{F}_{T_r}$, has the law of a chain started at $i$, because $X_{T_r}=i$. Its next return is therefore finite almost surely, proving inductively that all $T_r$ are finite almost surely. The same conditional-law statement shows that the next cycle path has a fixed distribution, independent of $\mathcal{F}_{T_r}$. Applying this successively to any finite list of cycle paths factors their joint probabilities into the product of their common one-cycle probabilities. Hence the cycle paths are iid; their lengths and visit-count vectors, being functions of those paths, are iid as well. $\square$

Almost-sure return is an essential condition for an infinite sequence of finite cycles. The theorem does not assert that every return time has a finite mean: an almost-surely finite positive integer-valued return time can still have infinite expectation. The examples below have finite, explicitly computed cycle lengths in expectation.

Computing Cycle Lengths and Visit Counts

Worked Example: A Two-State Return Cycle

Let $S=\{0,1\}$, with transition matrix $$ P=\begin{bmatrix}\tfrac12&\tfrac12\\1&0\end{bmatrix}. $$ The first row sums to $\tfrac12+\tfrac12=1$, and the second sums to $1+0=1$. Start at $0$, and find the cycle-length distribution and the expected visit counts before the next return to $0$.

At every step from $0$, the chain returns immediately to $0$ with probability $\tfrac12$, giving $L_0=1$. Otherwise it goes to $1$ with probability $\tfrac12$, and the next step goes to $0$ with probability $1$, giving $L_0=2$. Thus $\mathbb{P}_0(L_0=1)=\tfrac12$ and $\mathbb{P}_0(L_0=2)=\tfrac12$. The mean length is $\mathbb{E}_0[L_0]=1\cdot\tfrac12+2\cdot\tfrac12=\tfrac32$.

The cycle always includes its starting visit to $0$, so $C_0(0)=1$. It visits $1$ exactly on the length-two path, so $\mathbb{E}_0[C_0(1)]=1\cdot\tfrac12+0\cdot\tfrac12=\tfrac12$. Check: $\mathbb{E}_0[C_0(0)]+\mathbb{E}_0[C_0(1)]=1+\tfrac12=\tfrac32=\mathbb{E}_0[L_0]$, as required by the pathwise identity $\sum_j C_0(j)=L_0$.

For finite chains, a return-cycle calculation can often be reduced to a short path enumeration or a system of first-step equations. The return state is the boundary: once it is reached, the current cycle ends, and the next cycle has the same law when the chain started at that state.

Worked Example: A Three-State Cycle with Two Possible Excursions

Let $S=\{a,b,c\}$, and take $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac12&0&\tfrac12\\ 1&0&0 \end{bmatrix}, $$ with rows and columns ordered $a,b,c$. The row sums are $\tfrac12+\tfrac12+0=1$, $\tfrac12+0+\tfrac12=1$, and $1+0+0=1$. Starting at $a$, compute the return-cycle length distribution and expected visit counts.

From $a$, the chain returns to $a$ in one step with probability $\tfrac12$. Otherwise it moves to $b$. From $b$, it returns directly to $a$ with probability $\tfrac12$, producing the path $a,b$ and length $2$; with probability $\tfrac12$, it goes to $c$, which moves to $a$ with probability $1$, producing $a,b,c$ and length $3$. The full path probabilities are therefore $\mathbb{P}_a(L_0=1)=\tfrac12$, $\mathbb{P}_a(L_0=2)=\tfrac12\cdot\tfrac12=\tfrac14$, and $\mathbb{P}_a(L_0=3)=\tfrac12\cdot\tfrac12=\tfrac14$. They sum to $\tfrac12+\tfrac14+\tfrac14=1$, and $\mathbb{E}_a[L_0]=1\cdot\tfrac12+2\cdot\tfrac14+3\cdot\tfrac14=\tfrac74$.

Each cycle contains exactly one $a$. State $b$ is visited on both non-immediate-return paths, whose total probability is $\tfrac14+\tfrac14=\tfrac12$. State $c$ is visited only on the length-three path, of probability $\tfrac14$. Hence $\mathbb{E}_a[C_0(a)]=1$, $\mathbb{E}_a[C_0(b)]=\tfrac12$, and $\mathbb{E}_a[C_0(c)]=\tfrac14$. Check: $1+\tfrac12+\tfrac14=\tfrac74=\mathbb{E}_a[L_0]$. The three path probabilities also reproduce the expected length directly, so both calculations agree.

Why a Return to a Set May Not Regenerate

For a nonempty set $A\subseteq S$, define the first return time $T_A^+=\inf\{n\ge1:X_n\in A\}$ when $X_0\in A$. This time marks a return to the set, but the state $X_{T_A^+}$ may differ from the starting state. Conditional on the past, the future law depends on that return state. Thus the Markov property alone does not make successive set-return cycles iid. A set-return construction is regenerative only when the relevant cycle law is the same at each boundary and independent of the preceding cycles; this must be justified from the transition structure, not inferred merely from membership in $A$.

Worked Example: A Set Return with Alternating Visit Counts

Let $S=A=\{a,b\}$, with transition matrix $$ P=\begin{bmatrix}0&1\\1&0\end{bmatrix}. $$ Each row sums to $1$. Start at $a$. Every return to $A$ occurs one step later, so each interval between successive set returns has length $1$. However, the states alternate deterministically: $a,b,a,b,\ldots$.

With cycles defined from $T_r$ through $T_{r+1}-1$, the first cycle contains $a$, so its count vector in the order $(a,b)$ is $(1,0)$. The next contains $b$, with count vector $(0,1)$; the third again has $(1,0)$. In particular, the state-count vectors are not identically distributed: the first has probability $1$ of being $(1,0)$, while the second has probability $1$ of being $(0,1)$. Although the cycle lengths are all $1$, the set-return cycles do not provide iid state-count rewards. This example shows why a return to a set cannot automatically be treated like a return to one fixed state.

Common mistake. One might write the future-path probability at a stopping time as though $X_T$ were a fixed state, or replace a random starting state by $\mathbb{P}_{X_n}(\cdot)$ without averaging over its possible values. The correct deterministic-time decomposition conditions on each state explicitly: $\sum_{n\ge0}\sum_{x\in S}\mathbb{P}(A,T=n,X_n=x)\mathbb{P}_x(\text{specified future path})$. For a return to a fixed state $i$, the terms with $x\ne i$ vanish, which is precisely why the future cycle law is fixed. For a return to a set, several values of $x$ may remain, and their future laws need not agree.

Return-cycle computations are useful because they replace an unrestricted path by a sequence of excursions with a common boundary state. For each cycle, record its length and the states visited before the endpoint. In finite examples, listing possible paths gives exact distributions and expectations; in larger problems, first-step equations can organize the same calculation. Keep the endpoint convention consistent, verify that path probabilities sum to one, and check that the expected visit counts sum to the expected cycle length.

Check Your Understanding

Use the definition that a cycle includes its starting time and excludes its return endpoint.

For the two-state example, what is the probability that a cycle has length $2$, and what is its expected number of visits to state $1$?
In the three-state example, which path has length $3$, and what is its probability?
Why does the stopping-time proof sum over both $n$ and $x$?
In the alternating two-state set example, what are the first two cycle visit-count vectors?
What additional point must be checked before treating successive returns to a set as iid regenerative cycles?

Markov Chain Regeneration at Return Times

What You'll Learn