Expected Rewards Accumulated Before Absorption

From Visits to Rewards

In an absorbing Markov chain, the fundamental matrix records how often each transient state is visited before absorption. That information answers more than questions about time spent in the chain: if different states carry different costs, gains, or risks, the expected total is obtained by weighting each expected visit by the reward earned there. A similar calculation handles rewards attached to transitions, including a reward earned on the step that enters an absorbing state.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Suppose \(S=T\cup A\), where \(T\) is the set of transient states and \(A\) is a nonempty set of absorbing states. For each \(a\in A\), assume \(p_{aa}=1\). Write \(Q=(p_{ij})_{i,j\in T}\) for the transient-to-transient block of the transition matrix \(P\). Assume absorption has finite expected time from every state in \(T\). Equivalently, the series \(\sum_{n\ge0}Q^n\) converges entry by entry. The fundamental matrix is \(N=(I-Q)^{-1}=\sum_{n\ge0}Q^n\); its entry \(N_{ij}\) is the expected number of visits to \(j\) before absorption, starting from \(i\), counting time \(0\).

Because \(T\) is finite, any real-valued state reward vector \(r=(r_i)_{i\in T}\) is bounded. Finite expected absorption time therefore ensures that the expected absolute cumulative reward is finite. The reward may be positive, zero, or negative; the formula does not require every reward to be nonnegative.

Proof. Let \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Starting from \(i\in T\), the probability of being in transient state \(j\) at time \(n\) is \((Q^n)_{ij}\): the chain must make \(n\) transitions that all remain in \(T\). In particular, \(T_A>n\) precisely when the chain is still transient at time \(n\). The reward can be written as a sum over all times, with terms after absorption excluded: \[ Y=\sum_{n\ge0}\mathbf{1}_{\{T_A>n\}}r_{X_n}. \] If \(C=\max_{j\in T}|r_j|\), then \(\mathbb{E}_i[|Y|]\le C\mathbb{E}_i[T_A]<\infty\), so expectations and the sum can be interchanged. Grouping terms by state gives \[ \mathbb{E}_i[Y] =\sum_{n\ge0}\sum_{j\in T}(Q^n)_{ij}r_j =\sum_{j\in T}N_{ij}r_j =(Nr)_i. \] The fundamental matrix satisfies \((I-Q)N=I\), so \(v=Nr\) satisfies \((I-Q)v=r\), or \(v=r+Qv\). If \(w\) is any other solution, then \((I-Q)(w-v)=0\). Since \(I-Q\) is invertible, \(w-v=0\), proving uniqueness. For initial distribution \(\alpha\), averaging the state-specific expectations gives \(\sum_i\alpha_i v_i=\alpha Nr\). \(\square\)

The equation \(v=r+Qv\) is also a first-step check: earn the reward in the current transient state, then add the expected reward from the next state if that state is still transient. The matrix formula packages all the repeated visits into \(N\).

Indicator Rewards and Initial Distributions

A useful special case assigns reward \(1\) to one transient state and \(0\) to every other transient state. The cumulative reward then counts visits to that state before absorption. This also clarifies the convention about time \(0\): if the chain starts in the rewarded state, that initial visit is counted. More generally, if \(\alpha\) is a row distribution over transient states, then \(\alpha N\) gives the expected visit counts by destination state, and \(\alpha Nr\) weights those counts by the state rewards.

Rewards Earned on Transitions

Sometimes the reward depends not just on the current state, but on the move made. For example, a transition may represent a treatment, a production step, or entry into a costly absorbing condition. Let \(g(i,j)\) be the reward on a transition from \(i\) to \(j\). Only rewards on transitions taken before or at absorption are included: the transition from a transient state into \(A\) is included, but no transitions after arrival in \(A\) are counted.

Proof. Define the natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\), and let \(Z=\sum_{n=0}^{T_A-1}g(X_n,X_{n+1})\). Since \(S\) is finite, the transition rewards on possible transitions have a finite maximum absolute value, say \(C\); therefore \(\mathbb{E}_i[|Z|]\le C\mathbb{E}_i[T_A]<\infty\). Given \(\mathcal{F}_n\) and \(X_n=k\in T\), the Markov property gives \(\mathbb{E}[g(X_n,X_{n+1})\mid\mathcal{F}_n]=\sum_{j\in S}p_{kj}g(k,j)=c_k\). Consequently, the expected reward at time \(n\), counted only if \(n<T_A\), is \(\sum_{k\in T}(Q^n)_{ik}c_k\). Summing over \(n\ge0\), justified by the absolute-integrability bound, gives \(\mathbb{E}_i[Z]=\sum_{n\ge0}(Q^nc)_i=(Nc)_i\). Averaging over \(\alpha\) gives \(\alpha Nc\). \(\square\)

The transition-reward calculation has two stages: first average the reward on the next transition to obtain \(c\), then use \(N\) to account for all visits to each transient state. The transition reward on the final step into absorption is already included in \(c\), because its sum ranges over all destination states in \(S\).

Checks and a Common Mistake

A reliable calculation keeps the reward convention explicit. State rewards are earned at transient times \(0,\ldots,T_A-1\); transition rewards are earned on the \(T_A\) moves up to and including the move into an absorbing state. In both cases, absorption ends accumulation. The fundamental matrix does not itself represent a reward: it supplies expected visit counts, which must be weighted by the appropriate state reward vector or expected one-step transition reward vector.

Common mistake: counting only the reward at the initial state. In the first example, starting from state \(1\) gives immediate state reward \(r_1=2\). Reporting \(2\) as the expected total ignores all later visits before absorption. The correction is to use all expected visits: \((Nr)_1=3(2)+2(5)=6+10=16\). The value also checks in the first-step equation \(2+\tfrac12(16)+\tfrac13(18)=16\). A related error is to include a reward for every time spent in an absorbing state; that would count rewards after the specified stopping point and is not a reward accumulated before absorption.

These formulas require finite expected absorption time. If a chain can remain transient forever with positive probability, the fundamental matrix may not be finite and the expected cumulative reward need not be finite. Even when absorption occurs almost surely, an infinite expected absorption time can prevent a finite expected total for a positive reward earned at every transient step. The assumptions are therefore part of the method, not merely technical notation.