From State Frequencies to Reward Averages
A Markov chain can record more than which states it visits. Each state may carry a cost, payoff, measurement or other numerical reward, and the accumulated reward is often the quantity of interest. Examples include average cost per time step, long-run occupancy-weighted resource use and the average value of a measurement recorded along a trajectory. The key fact is that, under suitable recurrence and integrability conditions, the long-run sample average equals the reward's expectation under the stationary distribution.
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 and positive recurrent, so it has a stationary distribution \(\pi\), written as a row vector satisfying \(\pi P=\pi\) and \(\sum_{i\in S}\pi_i=1\). A state-reward function is a function \(f:S\to\mathbb{R}\); its stationary expectation is \(\pi(f)=\sum_{i\in S}\pi_i f(i)\), when this sum is absolutely integrable.
The condition is integrability with respect to \(\pi\), not boundedness of \(f\). In a finite state space, every real-valued reward function is integrable. On a countable state space, rewards can be unbounded, but their absolute stationary expectation must be finite. The conclusion is an almost-sure statement about the average along a trajectory; it does not assert that the reward at each individual time approaches its stationary expectation.
For a finite state space, the connection to empirical frequencies is direct. Define \(N_n(j)=\sum_{k=0}^{n-1}\mathbf{1}_{\{X_k=j\}}\), the number of visits to \(j\) among the first \(n\) observations. Then the accumulated reward can be regrouped by state:
Proof. Since \(S\) is finite, the displayed regrouping is a finite sum. On the probability-one event where every empirical frequency converges, each term \(f(j)N_n(j)/n\) converges to \(f(j)\pi_j\). Limits commute with a finite sum, so the sum converges to \(\sum_{j\in S}f(j)\pi_j\), as claimed. \(\square\)
For a countably infinite state space, that finite-sum argument alone is not enough: one cannot interchange an infinite sum and a limit without justification. The integrable-reward theorem supplies the required result under its stated hypotheses. Its role is especially important for unbounded rewards, where visits to rare states may carry large values.
Computing the Stationary Reward
Worked Example: A Three-State Reward
Consider a chain on \(S=\{1,2,3\}\) with transition matrix $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12\\ \tfrac13&0&\tfrac23 \end{bmatrix}. $$ Each row sums to \(1\): \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac12+\tfrac12=1\), and \(\tfrac13+0+\tfrac23=1\). The chain is irreducible, since from each state there is a path of positive probability to each other state. As a finite irreducible chain, it is positive recurrent. Find the long-run average of \(f(1)=2,\ f(2)=-1,\ f(3)=4\).
Write \(\pi=(\pi_1,\pi_2,\pi_3)\). The equation \(\pi P=\pi\) gives \(\pi_1=\tfrac12\pi_1+\tfrac13\pi_3\), \(\pi_2=\tfrac12\pi_1+\tfrac12\pi_2\), and \(\pi_3=\tfrac12\pi_2+\tfrac23\pi_3\). The second equation gives \(\pi_2=\pi_1\). The first gives \(\tfrac12\pi_1=\tfrac13\pi_3\), hence \(\pi_3=\tfrac32\pi_1\). Normalizing, \(\pi_1+\pi_2+\pi_3=(1+1+\tfrac32)\pi_1=\tfrac72\pi_1=1\), so \(\pi_1=\tfrac27\), \(\pi_2=\tfrac27\), and \(\pi_3=\tfrac37\).
The stationary reward is \(\pi(f)=\tfrac27(2)+\tfrac27(-1)+\tfrac37(4)=\tfrac47-\tfrac27+\tfrac{12}7=\tfrac{14}7=2\). Thus, from any initial state, \(n^{-1}\sum_{k=0}^{n-1}f(X_k)\to2\) almost surely.
Check. The stationary probabilities sum to \(\tfrac27+\tfrac27+\tfrac37=1\). Multiplying out, the first coordinate of \(\pi P\) is \(\tfrac27\cdot\tfrac12+\tfrac27\cdot0+\tfrac37\cdot\tfrac13=\tfrac17+\tfrac17=\tfrac27\); the second is \(\tfrac27\cdot\tfrac12+\tfrac27\cdot\tfrac12+\tfrac37\cdot0=\tfrac27\); and the third is \(\tfrac27\cdot0+\tfrac27\cdot\tfrac12+\tfrac37\cdot\tfrac23=\tfrac17+\tfrac27=\tfrac37\). Hence \(\pi P=\pi\), and the weighted reward calculation uses a verified stationary distribution.
The time-average conclusion does not require the distribution of \(X_n\) to converge at each time. Periodic chains provide a useful check: their state distributions can keep oscillating while their empirical frequencies, and therefore their reward averages, converge.
Worked Example: A Periodic Chain and a Reward Average
Let \(S=\{1,2,3\}\), with transitions \(1\to2\), \(2\to3\), and \(3\to1\), each with probability \(1\). Thus $$ P=\begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix}. $$ Every row sums to \(1\). The chain is finite and irreducible, and its period is \(3\). Its stationary distribution is \(\pi=(\tfrac13,\tfrac13,\tfrac13)\): each coordinate of \(\pi P\) is \(\tfrac13\), and the coordinates sum to \(1\). For the reward \(f(1)=1,\ f(2)=0,\ f(3)=0\), the stationary expectation is \(\pi(f)=\tfrac13\).
Starting at state \(1\), the reward sequence is \(1,0,0,1,0,0,\ldots\). Among the first \(n\) terms, the number of rewards equal to \(1\) is \(\lceil n/3\rceil\), where \(\lceil x\rceil\) denotes the least integer greater than or equal to \(x\). Therefore the average is \(\lceil n/3\rceil/n\). Since \(n/3\le\lceil n/3\rceil<n/3+1\), division by \(n\) shows that this average tends to \(\tfrac13\).
Check. The explicit average tends to \(\tfrac13\), agreeing with \(\pi(f)=\tfrac13\). The matrix has exactly one \(1\) in each row, so all three row sums are \(1\); direct multiplication also gives \(\pi P=(\tfrac13,\tfrac13,\tfrac13)\). This periodic example verifies that aperiodicity is not a hypothesis for the almost-sure time-average result.
Integrable Rewards on a Countable State Space
Worked Example: An Unbounded Reward with a Geometric Stationary Law
Consider the chain on \(S=\{0,1,2,\ldots\}\) that, from \(0\), stays at \(0\) with probability \(\tfrac23\) and moves to \(1\) with probability \(\tfrac13\); from each \(i\ge1\), it moves to \(i-1\) with probability \(\tfrac23\) and to \(i+1\) with probability \(\tfrac13\). At \(0\) the transition probabilities sum to \(\tfrac23+\tfrac13=1\); at every \(i\ge1\) they sum to \(\tfrac23+\tfrac13=1\). Every state communicates with \(0\), and \(0\) communicates with every state, so the chain is irreducible.
Set \(\pi_i=2^{-(i+1)}\) for \(i\ge0\). The probabilities sum to \(1\), since \(\sum_{i=0}^{\infty}2^{-(i+1)}=1\). To check stationarity at state \(0\), the incoming mass is \(\tfrac23\pi_0+\tfrac23\pi_1=\tfrac23\cdot\tfrac12+\tfrac23\cdot\tfrac14=\tfrac13+\tfrac16=\tfrac12=\pi_0\). For \(j\ge1\), incoming mass is \(\tfrac13\pi_{j-1}+\tfrac23\pi_{j+1}\). Substituting \(\pi_{j-1}=2^{-j}\) and \(\pi_{j+1}=2^{-(j+2)}\) gives \(\tfrac13\,2^{-j}+\tfrac23\,2^{-(j+2)}=2^{-j}(\tfrac13+\tfrac16)=2^{-(j+1)}=\pi_j\). Thus \(\pi\) is a stationary probability distribution. The standard irreducible-chain criterion that an invariant probability distribution implies positive recurrence now gives positive recurrence.
Take the unbounded reward \(f(i)=i\). Its stationary expectation is \(\sum_{i=0}^{\infty}i2^{-(i+1)}=1\): indeed, the geometric-series identity \(\sum_{i=0}^{\infty}i x^i=x/(1-x)^2\), valid for \(|x|<1\), gives \(\tfrac12\sum_{i=0}^{\infty}i(1/2)^i=\tfrac12\cdot2=1\). In particular, \(\sum_i\pi_i|f(i)|<\infty\), so the reward theorem applies and \(n^{-1}\sum_{k=0}^{n-1}X_k\to1\) almost surely from every initial state.
Check. The value at \(i=0\) contributes \(0\cdot\tfrac12=0\); the first two nonzero terms are \(1\cdot\tfrac14=\tfrac14\) and \(2\cdot\tfrac18=\tfrac14\). Their partial sum is \(\tfrac12\), consistent with the full positive series sum of \(1\). The stationary normalization and balance equations above verify that the weights used in the expectation are indeed the stationary probabilities.
Centering Rewards and Avoiding a Common Error
Proof. The theorem gives \(n^{-1}\sum_{k=0}^{n-1} f(X_k)\to c\) almost surely. For each \(n\), the centered average equals \(n^{-1}\sum_{k=0}^{n-1}f(X_k)-c\), because the constant \(c\) is subtracted \(n\) times and then divided by \(n\). Taking the limit gives \(c-c=0\) on the same probability-one event. \(\square\)
Common mistake: averaging over states instead of weighting by stationary frequencies. In the three-state example, the unweighted average of the reward values is \((2-1+4)/3=5/3\). That is not the long-run reward: the chain does not spend equal proportions of time in each state. The correct calculation is \(\sum_j\pi_j f(j)=\tfrac27(2)+\tfrac27(-1)+\tfrac37(4)=2\). Empirical frequencies converge to \(\pi_j\), so stationary weights—not equal weights—determine the long-run average.
The theorem is useful whenever the quantity of interest can be expressed as a reward attached to the current state. It converts a long trajectory into a stationary expectation, even for signed rewards or unbounded rewards with finite absolute stationary expectation. Before applying it, check irreducibility, positive recurrence and integrability; if any condition is absent, this theorem does not provide the claimed limit. In particular, a stationary distribution by itself is not a substitute for checking the theorem's assumptions.
Check Your Understanding
For each question, identify the relevant theorem condition or verify the calculation directly.
- In the three-state example, what is the stationary expectation of the reward \(g(1)=0,\ g(2)=3,\ g(3)=1\)?
- For the periodic three-state chain, what is the average reward from initial state \(2\) when \(f(1)=1,\ f(2)=0,\ f(3)=0\)? Explain why it has the same limit.
- Why is a boundedness assumption on \(f\) unnecessary for the countable-state example?
- State the long-run average given by the theorem for a reward \(h\) satisfying \(\sum_i\pi_i|h(i)|<\infty\).
- In the first finite-chain example, explain why \((2-1+4)/3\) does not give the long-run average.