From Return Cycles to a Stationary Law
For a finite chain, stationary distributions can often be found by solving balance equations. On a countable state space, those equations may have invariant solutions whose total mass is infinite, so existence of an invariant measure does not by itself give a stationary probability distribution. Positive recurrence supplies the key extra fact: returns to a fixed state have finite mean. That lets us normalize the expected number of visits made during a return cycle.
Let \((X_n)_{n\ge0}\) be a Markov chain on a countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). Its rows sum to \(1\). Use the natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). The chain is irreducible if every state can be reached from every other state with positive probability in some finite number of steps. Its return time to \(a\) is \(T_a^+=\inf\{n\ge1:X_n=a\}\). An irreducible chain is positive recurrent if \(\mathbb{E}_a[T_a^+]<\infty\) for each state \(a\). A stationary distribution is a probability row vector \(\pi\) satisfying \(\pi P=\pi\).
The sum counts visits to \(j\) in the cycle that starts at \(a\) and ends just before the next visit to \(a\). The endpoint convention matters: the initial visit at time \(0\) is included, while the returning visit at time \(T_a^+\) is not. We prove both existence and uniqueness below.
Proof. Fix \(a\). Positive recurrence gives \(m_a<\infty\), and \(m_a\ge1\). Write \(C_j=\sum_{n=0}^{T_a^+-1}\mathbf{1}_{\{X_n=j\}}\). Since exactly one state is occupied at each time before return, \(\sum_{j\in S}C_j=T_a^+\). Summing nonnegative terms and taking expectations gives \(\sum_j\mathbb{E}_a[C_j]=m_a\). Thus the displayed definition gives a probability distribution.
To verify invariance, use the Markov property at each deterministic time \(n\). The event \(\{n<T_a^+\}\) is determined by \(X_0,\ldots,X_n\), so conditioning on \(\mathcal{F}_n\) gives $$ \sum_{i\in S}\mathbb{E}_a[C_i]p_{ij} =\mathbb{E}_a\!\left[\sum_{n=0}^{T_a^+-1}p_{X_nj}\right] =\mathbb{E}_a\!\left[\sum_{n=0}^{T_a^+-1}\mathbf{1}_{\{X_{n+1}=j\}}\right]. $$ The sums and expectations can be interchanged because their terms are nonnegative. On every return cycle, the last sum counts visits at times \(1,\ldots,T_a^+\); the defining sum for \(\mathbb{E}_a[C_j]\) counts visits at times \(0,\ldots,T_a^+-1\). Their difference is \(\mathbf{1}_{\{X_{T_a^+}=j\}}-\mathbf{1}_{\{X_0=j\}}=0\), since both endpoints are \(a\). Hence \(\sum_i\mathbb{E}_a[C_i]p_{ij}=\mathbb{E}_a[C_j]\). Dividing by \(m_a\) proves \(\pi P=\pi\).
Every \(\pi_j\) is positive. For \(j=a\), the cycle counts the initial visit, so \(C_a=1\). For \(j\ne a\), irreducibility gives a positive-probability path from \(a\) to \(j\). Choose a shortest such path; it cannot revisit \(a\) before reaching \(j\), since removing that initial segment would give a shorter path from \(a\) to \(j\). On the event that the chain follows this path, \(C_j\ge1\). Therefore \(\mathbb{E}_a[C_j]>0\).
It remains to prove uniqueness. First, from every \(i\ne a\), the chain hits \(a\) almost surely. Otherwise, there would be positive probability of avoiding \(a\) forever starting from \(i\). Irreducibility supplies a finite path from \(a\) to \(i\) with no intermediate visit to \(a\) (take a shortest path). Following that path and then avoiding \(a\) would have positive probability from \(a\), contradicting the almost-sure return implied by \(\mathbb{E}_a[T_a^+]<\infty\).
Let \(\eta\) be any stationary distribution and put \(B=S\setminus\{a\}\). Its mass at \(a\) is positive: some \(\eta_i>0\), and irreducibility gives an \(n\) with \(p_{ia}^{(n)}>0\), so \(\eta_a=(\eta P^n)_a\ge\eta_i p_{ia}^{(n)}>0\). Let \(R=(p_{ij})_{i,j\in B}\), the substochastic matrix of transitions that remain in \(B\), and let \(r=(p_{aj})_{j\in B}\). The stationary equations restricted to \(B\) are \(\eta_B=\eta_a r+\eta_B R\). Iterating this identity \(N\) times gives $$ \eta_B=\eta_a r\sum_{k=0}^{N-1}R^k+\eta_B R^N. $$ For \(i\in B\), the sum of row \(i\) of \(R^N\) is \(\mathbb{P}_i(T_a>N)\), which tends to \(0\) by almost-sure hitting of \(a\). Consequently, the total mass of the residual term is \(\sum_{i\in B}\eta_i\mathbb{P}_i(T_a>N)\), which tends to \(0\) by dominated convergence: each probability tends to \(0\), and it is bounded by \(1\), while \(\sum_i\eta_i=1\).
For \(j\in B\), the \(j\)-th entry of \(rR^k\) is the probability, starting at \(a\), of being at \(j\) at time \(k+1\) without returning to \(a\) in between. Summing over \(k\ge0\) therefore gives \(\mathbb{E}_a[C_j]\). Taking \(N\) to infinity in the iterated equations yields \(\eta_j=\eta_a\mathbb{E}_a[C_j]\) for each \(j\in B\). The same identity holds at \(a\), because \(\mathbb{E}_a[C_a]=1\). Thus \(\eta\) is a constant multiple of the return-cycle occupation measure. Since both \(\eta\) and \(\pi\) have total mass \(1\), that constant is fixed, and \(\eta=\pi\). This proves uniqueness. \(\square\)
Computing the Cycle Occupation
Worked Example: A Chain on the Nonnegative Integers
Take \(S=\{0,1,2,\ldots\}\). From every state \(i\), the chain moves to \(0\) with probability \(\tfrac23\) and to \(i+1\) with probability \(\tfrac13\). Each row sums to \(\tfrac23+\tfrac13=1\). The chain is irreducible: repeated reset steps can reach \(0\), and repeated advance steps can reach any larger state.
Starting from \(0\), each step returns to \(0\) with probability \(\tfrac23\). Thus \(\mathbb{P}_0(T_0^+>n)=(\tfrac13)^n\) for \(n\ge0\), and \(\mathbb{E}_0[T_0^+]=\sum_{n\ge0}\mathbb{P}_0(T_0^+>n)=\sum_{n\ge0}(\tfrac13)^n=\tfrac32\). Before returning, the chain visits state \(j\ge1\) exactly once if its first \(j\) moves are advances, an event of probability \((\tfrac13)^j\). It visits \(0\) exactly once before return. Hence the cycle occupation values are \(g_0=1\) and \(g_j=(\tfrac13)^j\) for \(j\ge1\). Their sum is \(1+\sum_{j\ge1}(\tfrac13)^j=1+\tfrac12=\tfrac32\).
Normalizing gives \(\pi_0=\tfrac23\) and \(\pi_j=\tfrac23(\tfrac13)^j\) for \(j\ge1\). Check the total mass: \(\sum_{j\ge0}\pi_j=\tfrac23\sum_{j\ge0}(\tfrac13)^j=\tfrac23\cdot\tfrac32=1\). For stationarity at \(0\), the incoming mass is \(\sum_i\pi_i\tfrac23=\tfrac23=\pi_0\). For \(j\ge1\), the only incoming transition is from \(j-1\), so the incoming mass is \(\pi_{j-1}\tfrac13=\tfrac23(\tfrac13)^{j-1}\tfrac13=\pi_j\). Thus the cycle calculation satisfies the stationary equations.
Worked Example: A Three-State Return Cycle
Let \(S=\{0,1,2\}\) and $$ P=\begin{bmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ 1&0&0 \end{bmatrix}. $$ The row sums are \(1\), \(\tfrac12+\tfrac12=1\), and \(1\). All states communicate. Starting at \(0\), the chain goes to \(1\); from \(1\), it returns to \(0\) with probability \(\tfrac12\), or visits \(2\) and then returns to \(0\) with probability \(\tfrac12\). Thus \(T_0^+=2\) or \(3\), each with probability \(\tfrac12\), and \(\mathbb{E}_0[T_0^+]=\tfrac12(2)+\tfrac12(3)=\tfrac52\).
The cycle occupation values are \(g_0=1\), \(g_1=1\), and \(g_2=\tfrac12\), because the chain visits \(1\) every cycle and visits \(2\) precisely on the longer cycle. Their sum is \(1+1+\tfrac12=\tfrac52\), so the stationary distribution is \(\pi=(\tfrac25,\tfrac25,\tfrac15)\). Check each incoming mass: \(\pi_1\tfrac12+\pi_2=\tfrac15+\tfrac15=\tfrac25=\pi_0\); \(\pi_0=\tfrac25=\pi_1\); and \(\pi_1\tfrac12=\tfrac15=\pi_2\). The entries also sum to \(\tfrac25+\tfrac25+\tfrac15=1\).
Why Positive Recurrence Matters
Irreducibility alone does not ensure a stationary probability distribution. For a concrete example, let \(S=\mathbb{Z}\) and let the chain move from \(i\) to \(i+1\) with probability \(\tfrac23\), and to \(i-1\) with probability \(\tfrac13\). Every row sums to \(\tfrac23+\tfrac13=1\), and the chain is irreducible.
Worked Example: Irreducibility Without a Stationary Probability
Suppose a stationary probability \(\eta\) existed. Stationarity at state \(j\) would give \(\eta_j=\tfrac23\eta_{j-1}+\tfrac13\eta_{j+1}\). Define the flow across the edge from \(j\) to \(j+1\) by \(J_j=\tfrac23\eta_j-\tfrac13\eta_{j+1}\). The stationary equation rearranges to \(J_{j-1}=J_j\), so \(J_j\) is constant over all integers. Since \(\eta\) is summable, \(\eta_j\to0\) as \(j\to+\infty\); hence \(J_j\to0\) there, and the constant must be zero. Therefore \(\eta_{j+1}=2\eta_j\) for every \(j\). If any \(\eta_j>0\), then \(\eta_{j+k}=2^k\eta_j\) for every \(k\ge0\), contradicting summability. If no entry is positive, the total mass is \(0\), not \(1\). So no stationary probability exists.
This example shows why the finite-mean return condition cannot simply be omitted from the existence theorem. In applications, an invariant measure with infinite total mass is not enough: normalization requires finite expected occupation per return cycle.
A Common Normalization Error
A frequent mistake is to identify the expected cycle counts \(g_j\) themselves as the stationary probabilities. In the three-state example, that would give \((1,1,\tfrac12)\), whose entries sum to \(\tfrac52\), not \(1\). The correction is to divide each cycle occupation by the total expected cycle length: \((1,1,\tfrac12)/(\tfrac52)=(\tfrac25,\tfrac25,\tfrac15)\). A related endpoint error is to count both \(X_0=a\) and \(X_{T_a^+}=a\) as part of one cycle. That adds an extra visit to \(a\), even though the returning state is the start of the next cycle, not part of the current one.
The construction gives existence by producing an invariant probability directly, and the uniqueness argument explains why any other stationary law must use the same relative occupation weights between returns to \(a\). No aperiodicity assumption is needed: a periodic chain can still have a unique stationary distribution, even when its distributions from particular initial states do not converge at every time.
Check Your Understanding
Use the return-cycle definition and verify your answers against the relevant equations.
- Why does the sum of the expected cycle occupation counts equal \(\mathbb{E}_a[T_a^+]\), including for a countably infinite state space?
- For the chain on the nonnegative integers, compute \(\pi_2\) and check its incoming stationary mass.
- In the three-state example, what changes in the cycle occupation if the returning visit at time \(T_0^+\) is incorrectly included?
- In the uniqueness proof, why does the residual mass \(\sum_{i\in B}\eta_i\mathbb{P}_i(T_a>N)\) tend to zero?
- Which part of the existence argument fails if the expected return time to \(a\) is infinite?