Long-Run State Occupancy from Regenerative Cycles

From Cycle Occupation to State Probabilities

A regenerative cycle packages a complicated path into a unit that can be repeated. If the cycles are independent and identically distributed, long-run proportions can be calculated from the average contribution of one cycle. For state occupancy, the contribution of a cycle is the amount of time spent in each state. In a discrete-time Markov chain, this leads to a stationary distribution by dividing expected visits to a state during one cycle by the expected cycle length.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite state space $S$, with row-stochastic transition matrix $P=(p_{ij})$. Thus $p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$, and every row sums to $1$. For a state $a\in S$, define the first return time $T_a^+=\inf\{n\ge1:X_n=a\}$. A cycle starting at $a$ includes the states $X_0,\ldots,X_{T_a^+-1}$: the return state $X_{T_a^+}=a$ begins the next cycle and is not counted in the current one.

Definition: For a cycle from $a$ to its first return, the occupation count of state $i$ is $C_i=\sum_{n=0}^{T_a^+-1}\mathbf{1}_{\{X_n=i\}}$. If $0<\mathbb{E}_a[T_a^+]<\infty$, the cycle occupation probabilities are $\pi_i=\mathbb{E}_a[C_i]/\mathbb{E}_a[T_a^+]$, for $i\in S$.

The denominator counts the expected number of time steps in a cycle. The numerator counts the expected number of those steps spent in state $i$. Because exactly one state is occupied at each step, summing the occupation counts over states gives the cycle length. This makes the ratios sum to $1$. More importantly, when cycles are return cycles of a Markov chain, the ratios satisfy the stationary balance equations.

Theorem (Cycle occupation formula): Let $(X_n)_{n\ge0}$ be a Markov chain on a finite state space $S$, with transition matrix $P$. Fix $a\in S$ and suppose $0<\mathbb{E}_a[T_a^+]<\infty$. Then $$ \pi_i=\frac{\mathbb{E}_a\!\left[\sum_{n=0}^{T_a^+-1}\mathbf{1}_{\{X_n=i\}}\right]}{\mathbb{E}_a[T_a^+]}, \qquad i\in S, $$ defines a probability distribution satisfying $\pi P=\pi$.

Proof. Write $T=T_a^+$ and $v_i=\mathbb{E}_a[C_i]$. Each $C_i$ is nonnegative and at most $T$, so $v_i$ is finite. Also, at every step $n<T$ the chain occupies exactly one state. Summing the indicators over $i$ and then taking expectations gives $\sum_{i\in S}v_i=\mathbb{E}_a[T]$. Therefore $\pi_i=v_i/\mathbb{E}_a[T]$ is nonnegative and $\sum_i\pi_i=1$.

To prove invariance, fix $j\in S$. For each $n\ge0$, the event $\{n<T\}$ is determined by $X_0,\ldots,X_n$. The Markov property therefore gives $\mathbb{E}_a[\mathbf{1}_{\{n<T\}}p_{X_nj}] =\mathbb{E}_a[\mathbf{1}_{\{n<T\}}\mathbf{1}_{\{X_{n+1}=j\}}]$. Summing over $n$ is valid because the terms are nonnegative and the total number of terms with $n<T$ has finite expectation. Hence $$ \sum_{i\in S}v_i p_{ij} =\mathbb{E}_a\!\left[\sum_{n=0}^{T-1}\mathbf{1}_{\{X_{n+1}=j\}}\right]. $$ The sum on the right counts visits to $j$ at times $1,\ldots,T$, while $C_j$ counts visits at times $0,\ldots,T-1$. Their difference is $\mathbf{1}_{\{X_T=j\}}-\mathbf{1}_{\{X_0=j\}}$. Since $X_0=X_T=a$, this difference is zero for every $j$. Thus $\sum_i v_i p_{ij}=v_j$. Dividing by $\mathbb{E}_a[T]$ gives $\sum_i\pi_i p_{ij}=\pi_j$, which is $\pi P=\pi$. $\square$

The theorem establishes an invariant distribution, meaning a probability row vector left unchanged by one transition. If the chain is finite and irreducible, every state has positive cycle occupation and this distribution is the unique stationary distribution, by the standard finite-state uniqueness result. The cycle formula itself does not assert that $\mu P^n$ converges to $\pi$ from every initial distribution; periodic chains show why that distinction matters.

Proposition: If the finite chain in the theorem is irreducible, then its cycle occupation probability satisfies $\pi_i>0$ for every $i\in S$.

Proof. For $i=a$, the cycle includes $X_0=a$, so $C_a\ge1$ and $v_a>0$. For $i\ne a$, irreducibility gives a path from $a$ to $i$ with positive probability. Choose such a path of shortest length. It cannot visit $a$ between its initial state and its endpoint, since removing the portion up to that visit would give a shorter path from $a$ to $i$. Following the path therefore visits $i$ before $T_a^+$, on an event of positive probability. Consequently $v_i>0$, and division by the positive finite mean cycle length gives $\pi_i>0$. $\square$

Computing Occupation Probabilities

Worked Example: A Three-State Return Cycle

Consider a chain on $S=\{0,1,2\}$ with transition matrix $$ P=\begin{bmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ 1&0&0 \end{bmatrix}. $$ Each row sums to $1$: $0+1+0=1$, $\tfrac12+0+\tfrac12=1$, and $1+0+0=1$. Start at $0$ and use the first return to $0$ to define a cycle.

The first step is $0\to1$. From state $1$, the chain goes to $0$ with probability $\tfrac12$, ending a cycle of length $2$ with visits $C_0=1,C_1=1,C_2=0$. It goes to $2$ with probability $\tfrac12$, then $2\to0$ with probability $1$, making a cycle of length $3$ with visits $C_0=1,C_1=1,C_2=1$. Thus $\mathbb{E}_0[T_0^+]=\tfrac12(2)+\tfrac12(3)=\tfrac52$, and $\mathbb{E}_0[C_0]=1$, $\mathbb{E}_0[C_1]=1$, $\mathbb{E}_0[C_2]=\tfrac12(0)+\tfrac12(1)=\tfrac12$.

The cycle ratios are $\pi=(\tfrac25,\tfrac25,\tfrac15)$; their sum is $\tfrac25+\tfrac25+\tfrac15=1$. To check invariance, multiply by $P$: $\pi P=(\tfrac25\cdot0+\tfrac25\cdot\tfrac12+\tfrac15\cdot1,\ \tfrac25\cdot1+\tfrac25\cdot0+\tfrac15\cdot0,\ \tfrac25\cdot0+\tfrac25\cdot\tfrac12+\tfrac15\cdot0)=(\tfrac25,\tfrac25,\tfrac15)=\pi$. Both normalization and the stationary equations hold.

Worked Example: Self-Loops Within a Cycle

Let $S=\{0,1\}$ and $$ P=\begin{bmatrix} \tfrac23&\tfrac13\\ \tfrac14&\tfrac34 \end{bmatrix}. $$ The row sums are $\tfrac23+\tfrac13=1$ and $\tfrac14+\tfrac34=1$, so this is a transition matrix. Start a cycle at $0$, ending at $T_0^+$.

The cycle begins with one visit to $0$, counted at time $0$. If the next transition is $0\to0$, the cycle ends immediately. If it is $0\to1$, an event of probability $\tfrac13$, the chain visits state $1$ repeatedly until it moves to $0$. At each visit to $1$, the probability of moving to $0$ is $\tfrac14$, so the expected number of visits to $1$ in that run is $1/(\tfrac14)=4$. Therefore $\mathbb{E}_0[C_0]=1$ and $\mathbb{E}_0[C_1]=\tfrac13\cdot4=\tfrac43$. Since $T_0^+=C_0+C_1$, its expectation is $1+\tfrac43=\tfrac73$. The cycle formula gives $\pi=(\tfrac37,\tfrac47)$.

For a direct check, $\sum_i\pi_i=\tfrac37+\tfrac47=1$, and $\pi P=(\tfrac37\cdot\tfrac23+\tfrac47\cdot\tfrac14,\ \tfrac37\cdot\tfrac13+\tfrac47\cdot\tfrac34)=(\tfrac27+\tfrac17,\tfrac17+\tfrac37)=(\tfrac37,\tfrac47)$. The self-loop at $0$ ends the cycle; it must not be counted as an extra visit to $0$ in the same cycle.

Cycle Averages and Long-Run Occupancy

The same ratio has a time-average interpretation. For a regenerative process with iid cycles, let $L_k$ be the length of cycle $k$, and let $R_k(i)$ be the time spent in state $i$ during that cycle. The renewal-reward theorem states that if $0<\mathbb{E}[L_1]<\infty$ and $\mathbb{E}[|R_1(i)|]<\infty$, then the long-run reward per unit time is $\mathbb{E}[R_1(i)]/\mathbb{E}[L_1]$, almost surely. This standard result from renewal-reward theory applies to state occupancy because $0\le R_1(i)\le L_1$. For discrete-time return cycles, it gives the long-run fraction of steps spent in $i$ as $\mathbb{E}_a[C_i]/\mathbb{E}_a[T_a^+]$, under the finite-mean return assumption.

This time-average statement and the invariant-distribution calculation are related but not identical claims. The first concerns the fraction of time along a path; the second is the balance equation $\pi P=\pi$. In a finite irreducible chain the cycle formula supplies the stationary distribution, and the renewal-reward theorem supplies its time-average interpretation. Neither statement alone guarantees convergence of the one-time distribution $\mathbb{P}(X_n\in\cdot)$ as $n\to\infty$; aperiodicity is needed for the usual finite-chain convergence result.

Worked Example: Stationary but Not a Limiting Distribution

Consider the deterministic chain on $S=\{0,1\}$ with $$ P=\begin{bmatrix}0&1\\1&0\end{bmatrix}. $$ Each row sums to $1$. Starting at $0$, the return cycle is $0,1$, followed by a return to $0$, so $T_0^+=2$. Within the cycle, $C_0=1$ and $C_1=1$. The expected cycle length is $2$, and the cycle formula gives $\pi=(\tfrac12,\tfrac12)$. Its entries sum to $1$, and $\pi P=(\tfrac12\cdot0+\tfrac12\cdot1,\tfrac12\cdot1+\tfrac12\cdot0)=(\tfrac12,\tfrac12)$.

However, from $X_0=0$, the distribution at even times puts probability $1$ on $0$, while the distribution at odd times puts probability $1$ on $1$. It does not converge to $\pi$. The invariant probabilities describe cycle occupation, not necessarily the limit of the distribution at a fixed time.

Common Pitfall: Counting the Return State Twice

A cycle from $a$ to its first return uses the indices $0,\ldots,T_a^+-1$, not $0,\ldots,T_a^+$. The endpoint $X_{T_a^+}=a$ is the start of the next cycle. For the alternating-chain example, incorrectly including the endpoint would count two visits to $0$ and one to $1$, then divide by the incorrect length $3$ to obtain $(\tfrac23,\tfrac13)$. This is wrong: multiplying gives $(\tfrac23,\tfrac13)P=(\tfrac13,\tfrac23)\ne(\tfrac23,\tfrac13)$. Using the correct cycle $0,1$ gives one visit to each state and length $2$, hence $(\tfrac12,\tfrac12)$, which does satisfy the balance equations.

A second check is the mean cycle length: summing expected state visits must give $\sum_i\mathbb{E}_a[C_i]=\mathbb{E}_a[T_a^+]$. If this fails, either the endpoint convention or the visit counts have been applied inconsistently. Finally, finite expected return time is essential for the formula to define finite ratios. Without it, the denominator may be infinite and the argument does not produce a stationary probability distribution.

Check Your Understanding

Use cycle counts with the return state excluded, and verify proposed probabilities by substitution.

For a return cycle, explain why the sum of all state occupation counts equals $T_a^+$, not $T_a^++1$.
In the three-state example, calculate the probability that the cycle has length $3$, and list its state visits.
For the self-loop example, why is the expected number of visits to state $1$, conditional on entering it, equal to $4$?
State the two conditions in the cycle occupation theorem that ensure the denominator is finite and positive.
Give the stationary distribution of the alternating chain and explain why its one-time distributions from state $0$ do not converge.

Long-Run State Occupancy from Regenerative Cycles

What You'll Learn