Common Errors in Absorption and Hitting-Time Calculations

Start by Fixing the Event Being Calculated

Errors in absorption calculations often come from using the right matrix expression for the wrong event. A factor of \(Q\) can shift a distribution by one step; selecting a block from the wrong rows can make a valid transition matrix look like an absorbing-chain decomposition; and an initial visit can disappear when a sum starts at \(n=1\) instead of \(n=0\). A reliable check is to define the random event first, then match its time index and state ordering to the matrix calculation.

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 its states are ordered with the transient states first and the absorbing states second, so its row-stochastic transition matrix has the form

P=\begin{bmatrix}Q&R\\0&I\end{bmatrix}.

Here \(Q\) gives transitions among transient states, \(R\) gives transitions from transient to absorbing states, and \(I\) describes the absorbing states. Assume the transient block is transient, so \(N=\sum_{k=0}^{\infty}Q^k=(I-Q)^{-1}\) exists. The matrix \(N\) is the fundamental matrix. Write the initial distribution as \((\alpha,\beta)\), with \(\alpha\) the row vector of initial probabilities on transient states and \(\beta\) the row vector on absorbing states. These may have total mass less than one individually, but \(\alpha\mathbf{1}+\beta\mathbf{1}=1\).

Definition: The absorption time is \(T_{\mathrm{abs}}=\inf\{n\ge0:X_n\text{ is absorbing}\}\), with \(\inf\varnothing=\infty\). The time index starts at zero: if the chain starts in an absorbing state, then \(T_{\mathrm{abs}}=0\). For a specified set \(A\) of absorbing states, the hitting time is \(T_A=\inf\{n\ge0:X_n\in A\}\). These are different events when not every absorbing state belongs to \(A\).

The Time Index in the Absorption Distribution

For a chain that starts in a transient state, absorption at time \(n\ge1\) requires \(n-1\) transitions among transient states, followed by one transition into an absorbing state. That last transition is represented by \(R\). Thus the mass at time \(n\) uses \(Q^{n-1}R\), not \(Q^nR\). The exponent is determined by counting transitions before the final move into absorption.

Proposition: Under the block-matrix and transience assumptions above, for every \(n\ge1\), the row vector of probabilities of being absorbed in each absorbing state at time \(n\), from initial distribution \((\alpha,\beta)\), is \(\alpha Q^{n-1}R\). In particular, \(\mathbb{P}(T_{\mathrm{abs}}=0)=\beta\mathbf{1}\), and \(\mathbb{P}(T_{\mathrm{abs}}=n)=\alpha Q^{n-1}R\mathbf{1}\) for \(n\ge1\).

Proof. For \(n\ge1\), the event that the chain starts transient, remains transient through time \(n-1\), and enters a particular absorbing state at time \(n\) has probability row vector \(\alpha Q^{n-1}R\): multiplying by \(Q\) accounts for each of the first \(n-1\) transitions, and multiplying by \(R\) accounts for the final transition. The events of starting in an absorbing state and being absorbed at time zero have total probability \(\beta\mathbf{1}\); they are disjoint from the events of starting transient and being absorbed at \(n\ge1\). Summing the components of the row vector gives the probability of absorption at time \(n\). This proves both claims. \(\square\)

The equivalent survival formula is another useful check. For \(n\ge0\), \(\mathbb{P}(T_{\mathrm{abs}}>n)=\alpha Q^n\mathbf{1}\): survival beyond \(n\) means that the chain started transient and is still transient at time \(n\). Consequently, for \(n\ge1\), \(\mathbb{P}(T_{\mathrm{abs}}=n)=\mathbb{P}(T_{\mathrm{abs}}>n-1)-\mathbb{P}(T_{\mathrm{abs}}>n)\). This difference must agree with the mass formula.

Worked Example: Catching a One-Step Shift

Consider states \(0,1,2\), where \(0,1\) are transient and \(2\) is absorbing. The transition matrix, in that order, is

P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac23&\tfrac13\\ 0&0&1 \end{bmatrix}.

The row sums are \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac23+\tfrac13=1\), and \(0+0+1=1\). Starting from state \(0\), \(\alpha=(1,0)\), \(Q=\begin{bmatrix}\tfrac12&\tfrac12\\0&\tfrac23\end{bmatrix}\), and \(R=\begin{bmatrix}0\\\tfrac13\end{bmatrix}\). At time \(1\), absorption is impossible because \(0\) cannot move directly to \(2\): \(\alpha R=0\). At time \(2\),

\mathbb{P}_0(T_{\mathrm{abs}}=2) =\alpha QR =\begin{bmatrix}1&0\end{bmatrix} \begin{bmatrix}\tfrac12&\tfrac12\\0&\tfrac23\end{bmatrix} \begin{bmatrix}0\\\tfrac13\end{bmatrix} =\tfrac16.

At time \(3\), the second row of \(Q^2\) is \((0,\tfrac49)\), and its first row is \((\tfrac14,\tfrac7{12})\), since \(\tfrac14+\tfrac13=\tfrac7{12}\). Therefore \(\alpha Q^2R=\tfrac7{36}\). The survival probabilities give the same values: \(\mathbb{P}_0(T_{\mathrm{abs}}>1)=1\), while \(\mathbb{P}_0(T_{\mathrm{abs}}>2)=\tfrac14+\tfrac7{12}=\tfrac56\), so the mass at \(2\) is \(1-\tfrac56=\tfrac16\). Also, the first row of \(Q^3\) is \((\tfrac18,\tfrac{37}{72})\), so survival beyond \(3\) is \(\tfrac18+\tfrac{37}{72}=\tfrac{23}{36}\). The mass at \(3\) is \(\tfrac56-\tfrac{23}{36}=\tfrac7{36}\), as computed from \(Q^2R\).

Common wrong calculation: Using \(\alpha Q^nR\) for absorption at time \(n\) gives \(\alpha Q^2R=\tfrac7{36}\) at time \(2\). But that is the mass at time \(3\): two transitions occur within the transient states before the final transition into state \(2\). The correction is to use \(\alpha Q^{n-1}R\) for \(n\ge1\).

State Ordering Must Match Every Block

The displayed block form assumes the transient states come first and the absorbing states come second. It is not enough to identify the correct states; their order must be used consistently in \(P\), \(Q\), \(R\), and the initial distribution. If the states are interleaved, first permute rows and columns by the same ordering, or explicitly select the appropriate rows and columns by state name.

Worked Example: Extracting Blocks from Interleaved States

Use the order \((A,u,B,v)\), where \(A\) and \(B\) are absorbing and \(u,v\) are transient. Let \(u\) move to \(A\) or \(v\), each with probability \(\tfrac12\); let \(v\) move to \(u\) with probability \(\tfrac14\) and to \(B\) with probability \(\tfrac34\). The full matrix is

P=\begin{bmatrix} 1&0&0&0\\ \tfrac12&0&0&\tfrac12\\ 0&0&1&0\\ 0&\tfrac14&\tfrac34&0 \end{bmatrix}.

The row sums are \(1\), \(\tfrac12+\tfrac12=1\), \(1\), and \(\tfrac14+\tfrac34=1\). The transient states, in the order \((u,v)\), give \(Q=\begin{bmatrix}0&\tfrac12\\\tfrac14&0\end{bmatrix}\). The absorbing states, in the order \((A,B)\), give \(R=\begin{bmatrix}\tfrac12&0\\0&\tfrac34\end{bmatrix}\). For example, the \(\tfrac34\) transition from \(v\) to \(B\) belongs in \(R\), not \(Q\).

To check the absorption probabilities, calculate

I-Q=\begin{bmatrix}1&-\tfrac12\\-\tfrac14&1\end{bmatrix}, \qquad N=(I-Q)^{-1} =\begin{bmatrix}\tfrac87&\tfrac47\\\tfrac27&\tfrac87\end{bmatrix}.

The determinant used in the inverse is \(1-\tfrac18=\tfrac78\). Starting at \(u\), the probability of absorption in \(A\) is the first entry of \(N\)'s first row times the \(A\)-column of \(R\): \(\tfrac87\cdot\tfrac12=\tfrac47\). The probability of absorption in \(B\) is \(\tfrac47\cdot\tfrac34=\tfrac37\). These sum to \(\tfrac47+\tfrac37=1\). Starting at \(v\), the probabilities are \(\tfrac27\cdot\tfrac12=\tfrac17\) and \(\tfrac87\cdot\tfrac34=\tfrac67\), which sum to \(1\).

As a second check, the row sums of \(NR\) are \(1\): its first row sums to \(\tfrac47+\tfrac37=1\), and its second to \(\tfrac17+\tfrac67=1\). Taking the first two rows and columns of the original interleaved \(P\) as though they were \(Q\) would instead include the absorbing state \(A\) and omit the transient state \(v\). That submatrix is not the transient-to-transient block, so using its inverse as the fundamental matrix does not answer the stated problem.

Initial Visits and the Fundamental Matrix

The term \(Q^0=I\) in \(N=\sum_{k\ge0}Q^k\) counts the initial state, at time zero. More generally, \(Q^k\) describes transient-state occupancy at time \(k\) before absorption. This convention matters when interpreting expected visits, but it does not add a spurious step to the expected absorption time: a path with \(m\) transient visits before absorption makes \(m\) transitions before its final absorbing state is reached.

Worked Example: Do Not Drop the Time-Zero Visit

There is one transient state \(u\) and one absorbing state \(a\). From \(u\), the chain stays at \(u\) with probability \(\tfrac12\) and moves to \(a\) with probability \(\tfrac12\); state \(a\) stays at \(a\) with probability \(1\). The row sums are \(\tfrac12+\tfrac12=1\) and \(1\). Here \(Q=[\tfrac12]\), \(R=[\tfrac12]\), and \(N=[2]\), since \(1-\tfrac12=\tfrac12\) and its inverse is \(2\).

Starting at \(u\), the expected number of visits to \(u\), including the visit at time zero, is \(N_{uu}=2\). The expected absorption time is also \(2\): directly, \(\mathbb{P}_u(T_{\mathrm{abs}}=n)=(\tfrac12)^{n-1}\tfrac12=(\tfrac12)^n\) for \(n\ge1\), and the mean of this geometric distribution is \(2\). Equivalently, \(N\mathbf{1}=2\) gives the expected absorption time from the transient state.

If the visit sum is incorrectly started at \(k=1\), it becomes \(\sum_{k\ge1}(\tfrac12)^k=1\), omitting the initial visit. That sum is not \(N\) and does not give the expected number of transient visits. A further boundary check is useful: if the initial distribution places probability \(1\) on \(a\), then \(T_{\mathrm{abs}}=0\), not \(1\). With initial mass \(\beta\) on absorbing states, the expected absorption time is \(\alpha N\mathbf{1}\); the initial absorbing mass contributes zero.

Hitting a Target Is Not Always Absorption

A hitting probability concerns entry into a specified set. Eventual absorption concerns entry into any absorbing state. The two probabilities agree only when the target is exactly the set of absorbing states, or when other assumptions make their events equivalent. For a target \(A\) consisting of some absorbing states, let \(R_A\) be the columns of \(R\) indexed by \(A\), and let \(\beta_A\) be the initial probability row restricted to those states.

Proposition: If all states represented in \(Q\) are transient, then the probability of ever hitting the specified absorbing set \(A\) from initial distribution \((\alpha,\beta)\) is \(\beta_A\mathbf{1}+\alpha N R_A\mathbf{1}\). The probability of eventual absorption in any absorbing state is \(\beta\mathbf{1}+\alpha N R\mathbf{1}\).

Proof. If the chain starts in \(A\), it hits \(A\) at time zero, contributing \(\beta_A\mathbf{1}\). If it starts transient, the probability row of entering an absorbing state in \(A\) at time \(n\ge1\) is \(\alpha Q^{n-1}R_A\), by the absorption-time argument above. These events at different \(n\) are disjoint, so their probabilities sum to \(\sum_{n\ge1}\alpha Q^{n-1}R_A\mathbf{1}=\alpha N R_A\mathbf{1}\). Adding the time-zero contribution proves the first formula. Taking all absorbing states, so \(R_A=R\) and \(\beta_A=\beta\), proves the second. \(\square\)

Worked Example: Hitting One Absorbing State Versus Any Absorption

Consider states \(s,a,c\), with \(a\) and \(c\) absorbing. From \(s\), move to \(a\) or \(c\) with probability \(\tfrac12\) each. In the order \((s,a,c)\),

P=\begin{bmatrix} 0&\tfrac12&\tfrac12\\ 0&1&0\\ 0&0&1 \end{bmatrix}.

The row sums are \(0+\tfrac12+\tfrac12=1\), \(1\), and \(1\). Starting at \(s\), \(Q=[0]\), \(R=[\tfrac12,\tfrac12]\), and \(N=[1]\). For target \(A=\{a\}\), the hitting probability is \(NR_A\mathbf{1}=\tfrac12\). But eventual absorption in any absorbing state has probability \(NR\mathbf{1}=\tfrac12+\tfrac12=1\). Directly, \(T_{\mathrm{abs}}=1\) with probability \(1\), whereas \(T_{\{a\}}=1\) with probability \(\tfrac12\) and \(T_{\{a\}}=\infty\) with probability \(\tfrac12\). This verifies that “eventually absorbed” and “eventually hits \(A\)” need not describe the same event.

A Short Audit Before Accepting a Calculation

Before interpreting a computed absorption probability or time distribution, check the following items:

Does the time definition use \(n\ge0\) or \(n\ge1\)? If the chain starts in the target, a hitting time defined with \(n\ge0\) is zero.
For absorption at \(n\ge1\), does the expression include \(n-1\) transient transitions followed by one transition into absorption?
Are transient and absorbing states in the block order used to construct \(Q\) and \(R\)? Has the initial distribution been reordered to match?
Does the fundamental-matrix sum start at \(k=0\), thereby including the initial transient visit?
Is the requested event hitting one specified target, or eventual absorption in any absorbing state?

These checks diagnose errors without replacing the underlying calculation. In particular, a probability row should sum to one only when the events being counted exhaust all possible outcomes. Probabilities for a strict subset of absorbing states need not sum to one; the missing mass can be absorption in other states.

Check Your Understanding

For each question, specify the event and time convention before calculating.

Starting transient, what power of \(Q\) appears in the probability row for absorption at time \(4\), and what matrix follows that power?
A chain starts in an absorbing state, with \(T_{\mathrm{abs}}=\inf\{n\ge0:X_n\text{ is absorbing}\}\). What is its absorption time?
In the interleaved order \((A,u,B,v)\), which states index the rows and columns of \(Q\)?
Why does \(\sum_{k\ge0}Q^k\) include a visit at time zero, and what error can result from replacing it with \(\sum_{k\ge1}Q^k\)?
If there are two absorbing states but the target is only one of them, must the target-hitting probability equal the eventual-absorption probability? Explain using the events involved.