Computing Stationary Probabilities from Return Cycles

From a Return Cycle to Stationary Probabilities

A stationary distribution describes the long-run balance of a Markov chain, but it can also be calculated from the chain’s repeated returns to one chosen state. Start at that state, record the visits made before the next return, and average those counts. Their normalized values give the stationary probabilities. This approach is especially useful when the cycle visits can be found more directly than by solving the stationary equations all at once.

Let \((X_n)_{n\ge0}\) be a Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). Use the natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Fix a state \(r\), start the chain at \(r\), and define its first return time by \(T_r^+=\inf\{n\ge1:X_n=r\}\). The cycle consists of the states \(X_0,\ldots,X_{T_r^+-1}\): the return state at time \(T_r^+\) begins the next cycle and is not counted in this one.

For a finite irreducible chain, the return time to every state has finite expectation; this is the positive-recurrence result established earlier in the course. Irreducibility means every state can be reached from every other state with positive probability in some number of steps. The cycle calculation below uses this finite-mean condition. A stationary distribution is a row vector \(\pi\) with nonnegative entries summing to one and satisfying \(\pi P=\pi\). For a finite irreducible chain, that distribution is unique, and the return-cycle construction gives it.

Proof. The return time has finite expectation by positive recurrence, so the expected occupation counts are finite. For a fixed state \(j\), shift each cycle’s count forward by one time step. Pathwise, the shifted count differs from the original count by \(\mathbf{1}_{\{X_{T_r^+}=j\}}-\mathbf{1}_{\{X_0=j\}}\). Both \(X_{T_r^+}\) and \(X_0\) equal \(r\), so this difference is zero for every \(j\). Therefore, the expected number of visits to \(j\) at times \(1,\ldots,T_r^+\) equals \(a_j\).

To compute the shifted expectation another way, for each \(n\ge0\), the event \(\{n<T_r^+,X_n=i\}\) is in \(\mathcal{F}_n\). On that event the Markov property gives conditional probability \(p_{ij}\) that \(X_{n+1}=j\). Summing these conditional expectations over \(n\) and \(i\) gives the expected shifted count \(\sum_i a_i p_{ij}\). The sums involve nonnegative indicators, so their expectations may be summed, and the total is finite. Equating the shifted and original expected counts yields \(a_j=\sum_i a_i p_{ij}\). Also, on every path, \(\sum_j C_j=T_r^+\), since exactly one state is visited at each time \(0,\ldots,T_r^+-1\). Taking expectations gives \(L=\sum_j a_j\). Thus \(a/L\) is a probability row vector, and the count equations imply \((a/L)P=a/L\). It is stationary, so uniqueness for a finite irreducible chain identifies it as the unique stationary distribution. \(\square\)

The equations \(a_r=1\) and \(a_j=\sum_i a_i p_{ij}\) are a practical way to calculate cycle occupations. They are balance equations for expected counts, with the count at the chosen return state fixed by the cycle definition. Once the counts are found, sum them to get the expected return time, then divide every count by that same total.

What the Cycle Calculation Does—and Does Not—Say

The return-cycle method yields a stationary distribution, not necessarily a limiting distribution for \(\mu P^n\). Stationarity means that if the initial distribution is \(\pi\), it remains \(\pi\) after one or more steps. Convergence from other initial distributions requires additional conditions; in particular, periodicity can prevent convergence even for a finite irreducible chain. No aperiodicity condition is needed for the cycle occupation formula itself.

The choice of return state affects the bookkeeping but not the final stationary distribution. Each choice produces its own cycle and expected counts, and normalizing those counts gives the same unique stationary law. The mean cycle length is also a useful check: the counts must sum to \(\mathbb{E}_r[T_r^+]\), and the reciprocal mean return-time formula gives \(\pi_r=1/\mathbb{E}_r[T_r^+]\).

Common mistake: counting the return endpoint twice. In the first example, the correct cycle counts are \((1,\tfrac34,\tfrac34)\), with total \(\tfrac52\). If the endpoint \(X_{T_0^+}=0\) is added to that cycle, the incorrect counts become \((2,\tfrac34,\tfrac34)\), with total \(\tfrac72\). Normalizing them gives the wrong vector \((\tfrac47,\tfrac3{14},\tfrac3{14})\). It is not stationary: its coordinate for state \(1\) after multiplying by \(P\) would be \(\tfrac47\cdot\tfrac12+\tfrac3{14}\cdot\tfrac13=\tfrac5{14}\), not \(\tfrac3{14}\). Excluding the return endpoint gives counts \((1,\tfrac34,\tfrac34)\), and normalizing by their sum gives the verified stationary vector \((\tfrac25,\tfrac3{10},\tfrac3{10})\).