Second Moments of the Absorption Time

From Expected Time to Its Second Moment

The expected time to absorption describes the average duration of a transient episode, but it does not reveal how variable that duration is. A chain can have a moderate mean while still allowing some much longer-than-usual paths. The second moment records this variability and, together with the mean, gives the variance.

Consider a discrete-time Markov chain \((X_n)_{n\ge0}\) on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P\). Let \(A\subseteq S\) be a nonempty set of absorbing states, and let \(B=S\setminus A\) be the transient states. In the canonical ordering, write the transition matrix in blocks as

Here \(Q\) gives transitions among the transient states, and \(R\) gives transitions from transient to absorbing states. Each row of the full matrix \(P\) sums to \(1\). Let \(T_A=\inf\{n\ge0:X_n\in A\}\). We consider the chain started at a transient state, so \(T_A\) counts the steps up to and including the transition into \(A\). Write \(\mathbb{P}_i\) and \(\mathbb{E}_i\) for probability and expectation when \(X_0=i\).

Throughout the main result, assume absorption occurs almost surely from every transient state: \(\mathbb{P}_i(T_A<\infty)=1\) for each \(i\in B\). This condition matters: if the chain can avoid \(A\) with positive probability, then \(T_A=\infty\) on an event of positive probability, and its second moment is infinite.

The Second-Moment Equations

Order the transient states in \(B\), let \(\mathbf{1}\) be the column vector of ones of the appropriate dimension, and let \(t\) and \(s\) be the columns with entries \(t_i\) and \(s_i\). The fundamental matrix is \(N=(I-Q)^{-1}\). Under the stated finite-state, almost-sure absorption assumption, it exists; equivalently, \(N=\sum_{n\ge0}Q^n\). The expected-time formula is \(t=N\mathbf{1}\).

Proof. We first justify finiteness and the use of \(N\). For every transient state \(i\), almost-sure absorption implies that there is an integer \(n_i\) such that \(\mathbb{P}_i(T_A\le n_i)>0\). There are finitely many transient states, so choose \(L=\max_i n_i\) and \(\delta=\min_i\mathbb{P}_i(T_A\le L)>0\). By the Markov property, from any transient state the probability of avoiding \(A\) for the next \(L\) steps is at most \(1-\delta\). Applying this bound in successive blocks gives \(\mathbb{P}_i(T_A>kL)\le(1-\delta)^k\) for every integer \(k\ge0\). Thus the tail decreases geometrically, which implies both \(\mathbb{E}_i[T_A]\) and \(\mathbb{E}_i[T_A^2]\) are finite. Also, the row sums of \(Q^n\) equal the probabilities of remaining transient through \(n\) steps, and the same geometric bound ensures \(\sum_{n\ge0}Q^n\) converges. Multiplication of its partial sums by \(I-Q\) gives \(I-Q^{m+1}\), which tends to \(I\); therefore \(N=(I-Q)^{-1}\).

Now start at a transient state \(i\). After one step, if the chain remains transient at state \(j\), its remaining absorption time has the distribution of \(T_A\) under \(\mathbb{P}_j\), by the Markov property. If it enters \(A\), the remaining time is zero. Squaring the total time, which is one plus the remaining time, gives a contribution \(1+2t_j+s_j\) when the next state is transient \(j\), and a contribution \(1\) when it enters \(A\). Summing over next states and using that the probability of entering \(A\) is \(1-\sum_jq_{ij}\), we obtain \(s_i=1+2\sum_jq_{ij}t_j+\sum_jq_{ij}s_j\). This is the vector equation \(s=\mathbf{1}+2Qt+Qs\).

Rearranging yields \((I-Q)s=\mathbf{1}+2Qt\). Since \(I-Q\) is invertible, \(s=N(\mathbf{1}+2Qt)\). The expected-time equation \(t=\mathbf{1}+Qt\) implies \(Qt=t-\mathbf{1}\), so \(\mathbf{1}+2Qt=2t-\mathbf{1}\). Finally, \(t=N\mathbf{1}\), and therefore \(s=N(2N\mathbf{1}-\mathbf{1})=2N^2\mathbf{1}-N\mathbf{1}\). For each state, the definition of variance gives \(\operatorname{Var}_i(T_A)=s_i-t_i^2\), as claimed. \(\square\)

The equation \(s=\mathbf{1}+2Qt+Qs\) is the direct first-step system. The matrix expression is often more convenient computationally: once \(N\) and \(t\) are known, the second moment requires one more matrix-vector multiplication. The variance must be computed state by state by subtracting the square of that state’s mean.

Worked Calculations

When the Equations Do Not Give Finite Moments

Almost-sure absorption is not a dispensable technicality. For example, take a transient candidate state \(1\) that stays at \(1\) with probability \(1\), with target set \(A=\{2\}\) and state \(2\) absorbing. Starting from \(1\), the target is never reached, so \(T_A=\infty\) and neither moment is finite. The purported transient block is \(Q=[1]\), so \(I-Q=[0]\) has no inverse. This is why one must check absorption before using the fundamental-matrix formulas. In finite chains, positive probability of reaching the target is not enough; absorption must occur with probability one from each state under consideration.

Common mistake: omitting the cross term. Squaring the one-step decomposition requires \((1+T')^2=1+2T'+(T')^2\). If the \(2T'\) term is dropped, the geometric example would incorrectly give \(s=N\mathbf{1}=3\), and then the incorrect variance \(3-3^2=-6\). The correction is \(s=N(\mathbf{1}+2Qt)\): here \(Qt=\tfrac23\cdot3=2\), so \(s=3(1+2\cdot2)=15\), yielding the valid variance \(15-9=6\).

For a row-vector initial distribution \(\alpha\) on transient states, the unconditional first and second moments are \(\alpha t\) and \(\alpha s\), respectively. The variance is \(\alpha s-(\alpha t)^2\), not the weighted average of the state-specific variances alone. The initial state itself varies, so variation between the conditional means also contributes, as the third example demonstrates.