Return-Cycle Construction of a Stationary Distribution

From a Return Cycle to a Probability Vector

A stationary distribution describes the long-run balance of a Markov chain, but for a countable state space it may not be convenient to solve the balance equations directly. A different construction starts at one state, records the visits made before the chain first returns there, and averages those counts. Positive recurrence ensures that the return cycle has finite expected length, so its expected occupation counts can be normalized.

Let $(X_n)_{n\ge0}$ be a 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_{ij})$. Its natural filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. Assume the chain is irreducible, meaning every state can be reached from every other state with positive probability in some finite number of steps. Fix a state $a\in S$, and write $\mathbb{P}_a$ and $\mathbb{E}_a$ for probability and expectation when $X_0=a$.

Definition: The first return time to $a$ is $T_a^+=\inf\{n\ge1:X_n=a\}$, with $\inf\varnothing=\infty$. The return cycle consists of the states at times $0,1,\ldots,T_a^+-1$; the return at time $T_a^+$ is not included. For $j\in S$, define the cycle visit count $V_j=\sum_{n=0}^{T_a^+-1}\mathbf{1}_{\{X_n=j\}}$, and its expected value $\nu_j=\mathbb{E}_a[V_j]$.

For the construction below, assume the chain is positive recurrent: its mean return time $m_a=\mathbb{E}_a[T_a^+]$ is finite. For an irreducible chain, positive recurrence means this finite-mean-return condition holds at every state. The sum defining $V_j$ counts visits before the first return, not visits over an indefinitely continued trajectory.

Theorem (Return-cycle normalization): For an irreducible positive recurrent chain and any fixed state $a$, each $\nu_j$ is finite, $\sum_{j\in S}\nu_j=m_a$, and $$ \pi^{(a)}_j=\frac{\nu_j}{m_a},\qquad j\in S, $$ defines a probability distribution on $S$. In particular, $\nu_a=1$. The vector $\pi^{(a)}$ is the return-cycle candidate for a stationary distribution; normalization by itself is not a proof of stationarity.

Proof. For each sample path with finite $T_a^+$, every time $n$ with $0\le n<T_a^+$ contributes to exactly one state count, since $X_n$ takes exactly one value in $S$. Thus $\sum_{j\in S}V_j=T_a^+$. Positive recurrence gives $\mathbb{E}_a[T_a^+]=m_a<\infty$, so $0\le V_j\le T_a^+$ implies $\nu_j\le m_a<\infty$ for every $j$. Since all the counts are nonnegative, the theorem on exchanging expectation and a countable sum of nonnegative random variables gives $\sum_{j\in S}\nu_j=\mathbb{E}_a[\sum_{j\in S}V_j]=\mathbb{E}_a[T_a^+]=m_a$. Therefore the $\pi^{(a)}_j$ are nonnegative and sum to one. Finally, the cycle includes time $0$, when $X_0=a$, and contains no later visit to $a$ before $T_a^+$, by the definition of first return. Hence $V_a=1$ and $\nu_a=1$. $\square$

When $S$ is countably infinite, the countable-sum step matters: it shows that no mass is lost by summing expected visits state by state. The theorem also gives a useful distinction. It constructs a probability distribution from cycle occupations; to call that distribution stationary, one must additionally establish $\pi^{(a)}P=\pi^{(a)}$. That balance identity requires accounting for transitions into and out of states across the cycle, rather than merely normalizing the counts.

Worked Constructions

Worked Example: A Two-State Chain

Consider a chain on $S=\{a,b\}$ with transition matrix $$ P=\begin{bmatrix}\tfrac12&\tfrac12\\1&0\end{bmatrix}. $$ The first row sums to $\tfrac12+\tfrac12=1$, and the second to $1+0=1$. The chain is irreducible: from $a$ it can reach $b$ in one step, and from $b$ it reaches $a$ in one step.

Starting at $a$, the return cycle has two possibilities. With probability $\tfrac12$, the chain moves to $a$ immediately, so the cycle has length $1$ and has one visit to $a$, no visits to $b$. With probability $\tfrac12$, it moves to $b$, then from $b$ to $a$, so the cycle has length $2$ and has one visit to each state. Thus $$ \nu_a=1,\qquad \nu_b=\tfrac12\cdot 0+\tfrac12\cdot 1=\tfrac12,\qquad m_a=\tfrac12\cdot 1+\tfrac12\cdot 2=\tfrac32. $$

Normalizing gives $\pi^{(a)}_a=1/(\tfrac32)=\tfrac23$ and $\pi^{(a)}_b=(\tfrac12)/(\tfrac32)=\tfrac13$. Check the total: $\tfrac23+\tfrac13=1$. The expected-count total also checks: $1+\tfrac12=\tfrac32=m_a$, as required.

Worked Example: Expected Occupation in a Three-State Cycle

Let $S=\{a,b,c\}$, with transitions $a\to b$ with probability $1$; from $b$, move to $a$ or $c$, each with probability $\tfrac12$; from $c$, move to $a$ with probability $\tfrac13$ or stay at $c$ with probability $\tfrac23$. In the state order $a,b,c$, $$ P=\begin{bmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ \tfrac13&0&\tfrac23 \end{bmatrix}. $$ The row sums are $0+1+0=1$, $\tfrac12+0+\tfrac12=1$, and $\tfrac13+0+\tfrac23=1$. The chain is irreducible: $a$ reaches $b$ directly and $c$ through $b$; $b$ reaches $a$ directly; and $c$ reaches $a$ directly. From $a$, the chain returns to $a$ after leaving $b$, possibly making visits to $c$ first.

The cycle always contains one visit to $a$ at time $0$ and one visit to $b$, so $\nu_a=1$ and $\nu_b=1$. The chain enters $c$ only if its move from $b$ is to $c$, an event with probability $\tfrac12$. Conditional on entering $c$, the probability of still being at $c$ after $k$ further transitions is $(\tfrac23)^k$. The expected number of visits to $c$, including the first visit, conditional on entry, is therefore $$ \sum_{k=0}^{\infty}\left(\tfrac23\right)^k =\frac{1}{1-\tfrac23}=3. $$ So the unconditional expected count is $\nu_c=\tfrac12\cdot3=\tfrac32$.

By the pathwise identity between cycle length and total visits, $m_a=\nu_a+\nu_b+\nu_c=1+1+\tfrac32=\tfrac72$. The normalized vector is $$ \pi^{(a)}=\left(\frac{1}{\tfrac72},\frac{1}{\tfrac72},\frac{\tfrac32}{\tfrac72}\right) =\left(\tfrac27,\tfrac27,\tfrac37\right). $$ Check its total: $\tfrac27+\tfrac27+\tfrac37=\tfrac77=1$. Check the occupation total independently from the cycle description: the first two visits contribute $2$, and entry to $c$ contributes an expected $\tfrac32$, giving $2+\tfrac32=\tfrac72$.

Worked Example: A Periodic Chain

Take the deterministic cycle $a\to b\to c\to a$ on $S=\{a,b,c\}$. Its transition matrix is $$ P=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}. $$ Every row sums to $1$. Starting at $a$, the first return occurs at time $3$. The return cycle visits $a,b,c$ exactly once each, so $\nu_a=\nu_b=\nu_c=1$ and $m_a=3$. Normalization gives $\pi^{(a)}=(\tfrac13,\tfrac13,\tfrac13)$; its entries sum to $1$, and the total expected occupation $1+1+1=3$ matches the return time.

This chain has period $3$: returns to $a$ occur at times $3,6,9,\ldots$, whose greatest common divisor is $3$. The cycle construction still makes sense because it requires finite mean return time, not aperiodicity. Aperiodicity is relevant to some convergence questions, not to defining or normalizing these cycle counts.

What the Construction Does—and Does Not—Show

The cycle counts have a direct interpretation. The denominator $m_a$ is the expected number of time indices in one cycle, while $\nu_j$ is the expected number of those indices spent at $j$. Their ratio is the fraction of expected cycle occupation assigned to $j$. In particular, the reference state has exactly one visit in the half-open cycle, so its normalized mass is $1/m_a$. This identity follows directly from the construction; it does not require aperiodicity.

Irreducibility also ensures that no state is omitted from the occupation vector. To see why, fix $j\ne a$. There is a finite positive-probability path from $a$ to $j$. Truncate it at its first visit to $j$, then consider the last occurrence of $a$ before that visit. The resulting segment starts at $a$, ends at $j$, and has no intermediate visit to $a$. Following that segment has positive probability and visits $j$ before the first return to $a$. Thus $\mathbb{P}_a(V_j\ge1)>0$, which implies $\nu_j>0$. Also $\nu_a=1>0$. This argument establishes positivity of the counts, not the balance equations needed to establish stationarity.

Common pitfall: including the return endpoint. In the three-state example, the correct cycle stops at time $T_a^+-1$, so its counts are $(1,1,\tfrac32)$ and its length has mean $\tfrac72$. If the return at time $T_a^+$ is mistakenly included, one extra visit to $a$ is counted on every path. The altered expected counts become $(2,1,\tfrac32)$, with total $\tfrac92$, and normalization would give $(\tfrac49,\tfrac29,\tfrac13)$. Those are not the cycle counts defined here: the endpoint belongs to the next cycle, where it serves as the time-zero visit. Use the same half-open convention in both the visit counts and the cycle length.

A second caution is not to infer stationarity from the fact that the entries sum to one. The normalization theorem proves that $\pi^{(a)}$ is a probability distribution. Stationarity is the additional equation $\pi^{(a)}P=\pi^{(a)}$, which must be justified separately. In the return-cycle approach, that justification comes from comparing transitions leaving states during a cycle with visits arriving at states, with the return endpoint handled consistently. Keeping these two steps separate prevents a correct normalization argument from being mistaken for a complete invariance proof.

Check Your Understanding

Use the return-cycle convention in each question: count times $0$ through $T_a^+-1$, not the return time itself.

For a chain started at $a$, explain why $V_a=1$ on every path with finite $T_a^+$.
Suppose a return cycle has expected counts $\nu_a=1,\nu_b=2,\nu_c=1$. Find $m_a$ and the normalized cycle vector.
In the three-state worked example, what is the probability of entering $c$ during a cycle from $a$, and what is the expected number of visits to $c$ conditional on entering?
Why does finite mean return time imply that each individual expected visit count $\nu_j$ is finite?
Does the return-cycle construction require an aperiodic chain? Explain using the deterministic three-state cycle.

Return-Cycle Construction of a Stationary Distribution

What You'll Learn