Expected Visits from the Fundamental Matrix

What Does an Entry of the Fundamental Matrix Count?

In an absorbing Markov chain, the fundamental matrix records more than a matrix inverse: each of its entries has a direct counting interpretation. Starting from one transient state, an entry tells us the expected number of visits to another transient state before absorption. The convention about time zero matters. If the chain starts in the state being counted, that initial visit is included.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), and let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), with transition matrix \(P=(p_{ij})\). Its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). A state \(i\) is absorbing if \(p_{ii}=1\). A state \(i\) is transient if its probability of ever returning after time zero is less than one: \(\mathbb{P}_i(T_i^+<\infty)<1\), where \(T_i^+=\inf\{n\ge1:X_n=i\}\). In particular, merely leaving a state with probability one on the next step does not make it transient.

Suppose the states have been ordered so that the transient states come first and the absorbing states last, and write the transition matrix in canonical form as

Here \(Q\) gives transitions between transient states, and \(R\) gives transitions from transient to absorbing states. Every row of \(P\) sums to one. Assume absorption occurs almost surely from each transient starting state. The fundamental-matrix result for finite absorbing chains gives convergence of \(\sum_{n=0}^{\infty}Q^n\) and the identity \(N=(I-Q)^{-1}=\sum_{n=0}^{\infty}Q^n\). This tutorial focuses on what the entries of \(N\) count.

Because the chain starts in a transient state, \(T_A\ge1\). Thus the visit at time zero is counted if and only if the starting state is \(j\). Visits after the chain enters an absorbing state are not counted. Under the almost-sure absorption assumption, the count \(V_j\) is finite almost surely.

Why the Entry Gives an Expected Visit Count

The key connection is between powers of \(Q\) and visits at a fixed time. For transient states \(i,j\), the entry \(Q^n(i,j)\) is the probability that the chain is at \(j\) at time \(n\) without having entered an absorbing state. In particular, for \(n=0\), \(Q^0=I\), so \(Q^0(i,j)\) is one when \(i=j\) and zero otherwise. This identity at time zero is precisely where the initial visit enters.

Proof. Fix transient states \(i\) and \(j\), and start the chain at \(i\). For each \(n\ge0\), the event \(\{n<T_A,\ X_n=j\}\) says that the chain is in \(j\) at time \(n\) before absorption. Since every state visited before \(T_A\) is transient, the Markov property and multiplication of transition probabilities give \(\mathbb{P}_i(n<T_A,\ X_n=j)=Q^n(i,j)\). This also holds for \(n=0\), because \(Q^0(i,j)=\mathbf{1}_{\{i=j\}}\). The visit count can therefore be written as \(V_j=\sum_{n\ge0}\mathbf{1}_{\{n<T_A,\ X_n=j\}}\). Its partial sums increase to \(V_j\), so the monotone convergence theorem gives \(\mathbb{E}_i[V_j]=\sum_{n\ge0}\mathbb{P}_i(n<T_A,\ X_n=j)=\sum_{n\ge0}Q^n(i,j)=N(i,j)\). The last equality is the fundamental-matrix identity under the stated absorption assumption. \(\square\)

The same interpretation gives a useful recursion. From state \(i\), there is an immediate visit to \(j\) exactly when \(i=j\). After one step, if the chain moves to transient state \(k\), its expected number of subsequent visits to \(j\) is \(N(k,j)\); if it moves to an absorbing state, there are no further visits before absorption. Thus the expected count consists of the time-zero contribution plus the expected count after the first step.

Proof. Start at transient state \(i\). Separate the count \(V_j\) into its time-zero contribution \(\mathbf{1}_{\{i=j\}}\) and the visits after the first transition. Conditional on \(X_1=k\) for a transient state \(k\), the Markov property says that the expected number of later visits to \(j\) is \(N(k,j)\). The probability of this transition is \(q_{ik}\). A transition to an absorbing state contributes zero later visits. Taking expectations gives \(N(i,j)=\mathbf{1}_{\{i=j\}}+\sum_k q_{ik}N(k,j)\). Applying this identity to every pair of transient states yields \(N=I+QN\). \(\square\)

Taking \(i=j\) in the definition, the chain is already at \(j\) at time zero, so \(V_j\ge1\) for every path started at \(j\). Consequently \(N(j,j)\ge1\). For \(i\ne j\), no such initial visit is present, and \(N(i,j)\) counts only visits after the chain has moved away from its starting state.

Worked Visit Counts

Common Pitfall: Subtracting the Initial Visit

A frequent off-by-one error is to omit the \(n=0\) term and interpret \(N(i,j)\) as the expected number of visits strictly after time zero. The deterministic example makes the error visible. Starting at state \(1\), the chain is at state \(1\) once before absorption: at time zero. Thus \(N(1,1)=1\). The incorrect calculation \(\sum_{n=1}^{\infty}Q^n(1,1)=0\) counts only visits after time zero and misses that starting visit. The correct count is \(\sum_{n=0}^{\infty}Q^n(1,1)=1\).

More generally, if one specifically wants to count visits after time zero, the expected number is \(N(i,j)-\mathbf{1}_{\{i=j\}}\), because the only possible visit at time zero is present when the chain starts at \(j\). This adjustment changes the count convention, not the fundamental matrix itself.

The diagonal has a particularly useful interpretation: \(N(i,i)\) is the expected total number of visits to \(i\) before absorption when starting at \(i\), with the initial visit included. It is not the expected number of returns after time zero. In contrast, for \(i\ne j\), \(N(i,j)\) counts visits to \(j\) reached after starting from \(i\). Keeping those meanings distinct prevents confusion between a visit count and a return count.