Stationary Mass from a Return Cycle
For a countable-state chain, the stationary equations may be an infinite system. A useful alternative is to choose a state that the chain returns to and examine one trip from that state back to itself. The expected number of visits to each state during the trip gives its stationary weight; dividing by the expected trip length makes those weights sum to one. This method is especially effective when the excursions away from the chosen state have a simple structure.
Let \((X_n)_{n\geq 0}\) be a discrete-time Markov chain on a countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). Each row of \(P\) sums to \(1\). Write \(\mathbb{P}_a\) and \(\mathbb{E}_a\) when the chain starts at \(a\), and take its natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). For a specified state \(a\), the first return time is \(T_a^+=\inf\{n\geq 1:X_n=a\}\). The cycle consists of the states \(X_0,\ldots,X_{T_a^+-1}\): it includes its starting visit to \(a\), but not the terminal visit that begins the next cycle.
The finite-mean assumption makes the denominator finite, and \(T_a^+\geq 1\) makes it positive. It also implies that the return occurs almost surely. The formula asks for two quantities: the expected cycle length and the expected number of visits to each state in the cycle. Both include visits at discrete time \(0\) and exclude the terminal return at time \(T_a^+\).
Proof. Put \(T=T_a^+\) and \(m=\mathbb{E}_a[T]\). Since each cycle has exactly \(T\) time indices, \(\sum_{j\in S}Y_j=T\). All terms are nonnegative, so summing expectations over the countable state space gives \(\sum_j\mathbb{E}_a[Y_j]=\mathbb{E}_a[T]=m\). Thus the displayed \(\pi\) is nonnegative and sums to one.
To prove invariance, fix \(j\in S\). Using nonnegative sums and the Markov property at each deterministic time \(n\), with \(\{n<T\}\in\mathcal{F}_n\), gives
The second equality follows by conditioning each indicator on \(\mathcal{F}_n\): its conditional expectation is \(p_{X_nj}\). The last sum counts visits to \(j\) at times \(1,\ldots,T\), whereas \(Y_j\) counts visits at times \(0,\ldots,T-1\). Their difference is \(\mathbf{1}_{\{X_T=j\}}-\mathbf{1}_{\{X_0=j\}}=0\), because \(X_0=X_T=a\). Therefore the displayed expression equals \(\mathbb{E}_a[Y_j]\). Dividing by \(m\) proves \(\sum_i\pi_i p_{ij}=\pi_j\), for every \(j\), so \(\pi P=\pi\). \(\square\)
Excursions Along Countably Many Arms
First consider a chain whose excursions have deterministic lengths once selected. The state \(0\) is the regeneration state; from it, the chain selects an arm \(k\), visits each state on that arm in order, and returns to \(0\). The cycle formula can be applied directly because both the excursion length and the states visited are explicit.
Worked Example: Deterministic Excursions of Random Length
Take \(S=\{0\}\cup\{(k,r):k\geq1,\ 1\leq r\leq k\}\). From \(0\), choose arm \(k\) with probability \(p_k=2^{-k}\). Then move deterministically from \((k,r)\) to \((k,r+1)\) if \(r<k\), and from \((k,k)\) to \(0\). Find the stationary distribution.
The row at \(0\) sums to \(\sum_{k=1}^{\infty}2^{-k}=1\). Every other row has one transition of probability \(1\), so also sums to \(1\). Every state can reach \(0\), and \(0\) can reach every arm with positive probability; hence the chain is irreducible. If arm \(k\) is selected, the return time is \(k+1\). The expected number of visits to \(0\) in a cycle is \(1\), and to each particular \((k,r)\) it is \(p_k=2^{-k}\).
The mean return time is
Here \(\sum_{k\geq1}k2^{-k}=2\), as follows by writing \(k=\sum_{r=1}^k1\) and summing the geometric tails. Therefore
Check normalization. Summing over all states gives \(\frac13+\frac13\sum_{k\geq1}k2^{-k}=\frac13+\frac23=1\).
Check the stationary equations. For \(r=1\), the only incoming transition to \((k,1)\) is from \(0\), so its incoming mass is \(\pi_0 2^{-k}=2^{-k}/3=\pi_{(k,1)}\). For \(2\leq r\leq k\), the only incoming transition is from \((k,r-1)\), whose mass is also \(2^{-k}/3\). The incoming mass to \(0\) is the sum of the masses at all terminal states \((k,k)\), namely \(\sum_{k\geq1}2^{-k}/3=1/3=\pi_0\). Thus every stationary equation holds.
Repeated Visits Within an Excursion
An excursion need not move through distinct states. If the chain can remain at a state before returning to the regeneration state, its expected number of visits there must account for all repetitions. In the examples below, those visit counts are geometric sums.
Worked Example: A Geometric Hold at the Selected State
Let \(S=\{0,1,2,\ldots\}\). From \(0\), choose \(k\geq1\) with probability \(2^{-k}\). From \(k\), remain at \(k\) with probability \(\tfrac12\), and move to \(0\) with probability \(\tfrac12\). Find the stationary distribution.
The row at \(0\) sums to \(\sum_{k\geq1}2^{-k}=1\); row \(k\) sums to \(\tfrac12+\tfrac12=1\). The chain is irreducible because every \(k\) can return to \(0\), and \(0\) can select every \(k\) with positive probability. On a cycle, the expected visits to \(k\), conditional on selecting it, are \(\sum_{r\geq1}(\tfrac12)^{r-1}=2\): the \(r\)th visit occurs exactly when the first \(r-1\) self-transitions occur. Thus the unconditional expected visits to \(k\) are \(2\cdot2^{-k}\). The cycle contains its initial visit to \(0\), followed by those visits to the selected state, so
The cycle formula gives \(\pi_0=\tfrac13\) and \(\pi_k=2^{1-k}/3\) for \(k\geq1\). The normalization check is \(\tfrac13+\tfrac13\sum_{k\geq1}2^{1-k}=\tfrac13+\tfrac23=1\).
For each \(k\), the incoming mass is \(\pi_0 2^{-k}+\pi_k\tfrac12=2^{-k}/3+2^{-k}/3=2^{1-k}/3=\pi_k\). The incoming mass to \(0\) is \(\sum_{k\geq1}\pi_k\tfrac12=\sum_{k\geq1}2^{-k}/3=1/3=\pi_0\). These checks confirm the stationary equations as well as normalization.
The same calculation works when the holding probability depends on the state. The condition that each state eventually returns to \(0\) is not, by itself, enough to ensure a finite expected cycle length: the expected visits accumulated across all possible excursions must also be summable.
Worked Example: State-Dependent Holding Probabilities
Again let \(S=\{0,1,2,\ldots\}\), with transitions from \(0\) to \(k\) of probability \(2^{-k}\). From \(k\), stay at \(k\) with probability \(k/(k+1)\) and return to \(0\) with probability \(1/(k+1)\). Compute the stationary distribution.
The row at \(0\) sums to \(1\), and row \(k\) sums to \(k/(k+1)+1/(k+1)=1\). All states communicate through \(0\). Conditional on selecting \(k\), the probability of at least \(r\) visits to \(k\) is \((k/(k+1))^{r-1}\), so the expected number of visits is the geometric sum \(\sum_{r\geq1}(k/(k+1))^{r-1}=k+1\). The unconditional expected visits to \(k\) are therefore \(2^{-k}(k+1)\). Since \(\sum_{k\geq1}2^{-k}=1\) and \(\sum_{k\geq1}k2^{-k}=2\),
Consequently, \(\pi_0=\tfrac14\) and \(\pi_k=(k+1)2^{-k}/4\) for \(k\geq1\). The probabilities sum to \(\tfrac14+\tfrac14\sum_{k\geq1}(k+1)2^{-k} =\tfrac14+\tfrac34=1\).
For state \(k\), the incoming mass is \(\pi_0 2^{-k}+\pi_k k/(k+1) =2^{-k}/4+k2^{-k}/4 =(k+1)2^{-k}/4=\pi_k\). For state \(0\), the incoming mass is \(\sum_{k\geq1}\pi_k/(k+1) =\tfrac14\sum_{k\geq1}2^{-k} =\tfrac14=\pi_0\). Thus direct substitution confirms the cycle calculation.
Why the Cycle Convention Matters
A stationary distribution describes invariant mass, not necessarily the distribution approached from every starting state. No convergence claim is needed for the return-cycle formula: periodicity, for example, can prevent convergence of \(\mu P^n\) while leaving \(\pi P=\pi\) valid. The practical advantage here is different: when excursions can be described explicitly, one can compute an invariant distribution without solving an infinite stationary system all at once.
Common mistake: counting the return twice. In the deterministic-excursion example, the cycle has one visit to \(0\) at time \(0\) and returns to \(0\) at time \(T_0^+\). If both are included as visits in the same cycle, the expected count of \(0\) is incorrectly taken as \(2\). The resulting denominator is \(\mathbb{E}_0[T_0^++1]=4\), so this incorrect calculation assigns mass \(1/2\) to \(0\) and mass \(2^{-k}/4\) to each \((k,r)\). But the incoming mass to \((k,1)\) would then be \((1/2)2^{-k}=2^{-k}/2\), not the proposed \(2^{-k}/4\). Excluding the terminal return gives the correct denominator \(3\), mass \(1/3\) at \(0\), and the stationary equations verified above.
For a new countable-chain calculation, identify the return state, define the cycle with its initial and terminal times unambiguously, compute the expected cycle length, and count visits state by state. Then check that the cycle length is finite, normalize the occupation weights, and substitute them into the incoming stationary equations. The formula is only useful as a probability distribution when the expected cycle length is finite.
Check Your Understanding
Use the return-cycle definition with the terminal return excluded, and verify each proposed stationary distribution by normalization and the stationary equations.
- In the deterministic-arm chain, what is the expected number of visits to a fixed state \((k,r)\) in one cycle?
- For the geometric-hold chain with self-transition probability \(\tfrac12\), compute the expected number of visits to \(k\) conditional on selecting \(k\).
- In the state-dependent holding example, explain why the expected visits conditional on selecting \(k\) equal \(k+1\).
- Why does the cycle-occupation proof compare visits at times \(0,\ldots,T_0^+-1\) with visits at times \(1,\ldots,T_0^+\)?
- In the deterministic-arm example, identify the specific stationary equation violated by the calculation that counts the terminal return as an extra visit to \(0\).