Simulating Markov Chain Occupation Times and Rewards

From a Simulated Path to Occupation and Reward

A simulated Markov chain path contains more information than its final state. It records how often the chain visited each state, and therefore how much time it spent in different parts of the state space. If each state has a cost, benefit, or other numerical value attached to it, the same path also gives a cumulative reward. These summaries turn a sequence of simulated transitions into estimates of long-run behavior.

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 entries are nonnegative and each row sums to \(1\). For simulation, one can generate the next state from the current row of \(P\) using a fresh uniform random variable. For a trajectory with \(N\ge1\) observed states, we use \(X_0,\ldots,X_{N-1}\): this convention counts the initial state and gives \(N\) observations.

Every observed state contributes exactly once, so \(\sum_{i\in S}C_i(N)=N\) and \(\sum_{i\in S}\widehat{\pi}_i(N)=1\). Also, the accumulated reward can be computed either along the path or from the occupation counts: \(R_N=\sum_{i\in S}r(i)C_i(N)\). Thus \(\overline{r}_N=\sum_{i\in S}r(i)\widehat{\pi}_i(N)\). The empirical occupation proportions and the average reward are two summaries of the same finite path.

Simulating and Summarizing a Path

To simulate a transition from state \(i\), list the destinations in a fixed order and form cumulative row probabilities. A uniform random variable \(U\) on \([0,1)\) selects the first destination whose cumulative probability is strictly greater than \(U\). Equivalently, intervals can be taken half-open: a destination with cumulative interval \([a,b)\) is selected when \(a\le U<b\). This convention assigns each possible \(U\) to one destination, including values at interval boundaries.

For a formal description of the simulation, let \(U_1,U_2,\ldots\) be independent uniform random variables on \([0,1)\), independent of \(X_0\). The state \(X_{k+1}\) is selected from row \(X_k\) using \(U_{k+1}\). With the filtration \(\mathcal{F}_k=\sigma(X_0,U_1,\ldots,U_k)\), this construction makes the conditional transition probabilities satisfy \(\mathbb{P}(X_{k+1}=j\mid\mathcal{F}_k)=p_{X_kj}\). The counts and rewards are then computed from the generated path, not from additional assumptions about the future.

What the Finite-Trajectory Averages Estimate

Let the initial distribution be the row vector \(\mu_0\), so that \(\mu_k=\mu_0P^k\) is the distribution of \(X_k\). The expected occupation count and expected accumulated reward have exact finite-horizon expressions. They describe averages over repeated simulations, while an individual trajectory gives one realized estimate.

Proof. By definition, \(C_i(N)=\sum_{k=0}^{N-1}\mathbf{1}_{\{X_k=i\}}\). Taking expectations and using linearity for this finite sum gives \(\mathbb{E}[C_i(N)]=\sum_{k=0}^{N-1}\mathbb{E}[\mathbf{1}_{\{X_k=i\}}]=\sum_{k=0}^{N-1}\mathbb{P}(X_k=i)\). The distribution of \(X_k\) is \(\mu_0P^k\), so the first identity follows. Also \(R_N=\sum_{k=0}^{N-1}r(X_k)=\sum_{k=0}^{N-1}\sum_{i\in S}r(i)\mathbf{1}_{\{X_k=i\}}\), since exactly one indicator is \(1\) at each time. Taking expectations and applying the first identity state by state gives the stated reward formula. \(\square\)

If \(X_0\) has a stationary distribution \(\pi\), meaning \(\pi P=\pi\), then \(\mu_k=\pi\) at every \(k\). The proposition implies \(\mathbb{E}[\widehat{\pi}_i(N)]=\pi_i\) and \(\mathbb{E}[\overline{r}_N]=\sum_i\pi_i r(i)\). For a nonstationary initial distribution, these equalities need not hold at a finite \(N\). In particular, dividing an expected total by \(N\) does not make every finite-trajectory estimate equal to its long-run target.

Long-Run Interpretation and Its Limits

For a finite irreducible Markov chain, there is a precise long-run interpretation of occupation and reward averages. The finite-state Markov chain ergodic theorem states that for any initial state, \(\widehat{\pi}_i(N)\to\pi_i\) almost surely for every state \(i\), where \(\pi\) is the unique stationary distribution. Consequently, \(\overline{r}_N\to\sum_i\pi_i r(i)\) almost surely for every real-valued state reward \(r\). This standard theorem is proved in the later course material on long-run Markov chain behavior; the conditions here are finite state space and irreducibility. Aperiodicity is not required for these time averages, although it is relevant to some other types of convergence.

The reward conclusion follows directly from the occupation conclusion: \(\overline{r}_N=\sum_i r(i)\widehat{\pi}_i(N)\), and this is a finite sum. If each \(\widehat{\pi}_i(N)\) converges to \(\pi_i\), then each term converges to \(r(i)\pi_i\), and the finite sum converges to \(\sum_i r(i)\pi_i\). This tells us what a sufficiently long trajectory estimates; it does not guarantee that a short trajectory is close to the target.

Common mistake. If rewards are attached to observed states, divide their sum by the number of observed states, not automatically by the number of transitions. In the first example there are five observed states and four transitions. The reward total is \(7\), so the defined average is \(7/5\). Dividing by four gives \(7/4\), which is the wrong quantity for this convention. A different definition based on rewards attached to transitions would use a transition-indexed reward and a denominator matching the number of transitions; it should not be mixed with the state-reward definition.

When reporting a simulation summary, state the observation convention, the initial state or distribution, the transition matrix, the reward function, and the trajectory length. These specify what the counts and average mean. The finite-horizon formulas give useful exact checks on expected totals, while the ergodic theorem explains the target of long runs when the chain is finite and irreducible.