When Reaching a Target Is Not Certain
In an absorbing-chain problem, it is tempting to assume that every path eventually reaches one of the designated target states. A finite state space alone does not guarantee this. A chain may enter a closed class of non-target states and then remain there forever. The right calculation separates those classes from the states that can still lead to a target.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with row-stochastic transition matrix \(P=(p_{ij})\). For \(A\subseteq S\), the hitting time is \(T_A=\inf\{n\ge0:X_n\in A\}\), with \(\inf\varnothing=\infty\). The quantity of interest is \(h_i=\mathbb{P}_i(T_A<\infty)\), the probability of ever reaching \(A\) when the chain starts at \(i\).
For the classification below, regard each state in \(A\) as absorbing: replace its transition row by a row with probability \(1\) of staying at that state. This change does not affect the probability of the first hit of \(A\). A set \(C\) is a communicating class if its states communicate with one another and it is maximal with that property. A class is closed if no transition from a state in the class leads outside it. A closed class disjoint from \(A\) is a non-target class: once the chain enters it, it can never reach \(A\).
Proof. First consider the finite directed graph whose vertices are the states and whose directed edges are the positive-probability transitions. Collapse each communicating class to one vertex. The resulting graph has no directed cycles: a cycle among distinct collapsed vertices would mean those classes communicate, contradicting their being distinct communicating classes. From any vertex in a finite directed graph with no cycles, following outgoing edges must eventually reach a vertex with no outgoing edge. That vertex corresponds to a closed communicating class. Thus from every state there is a path to a closed class. If the state is not already in one, a path with no repeated states can be chosen, so its length is at most \(|S|-1\).
For each state outside the closed classes, choose one such path. Every edge on each chosen path has positive probability, so the probability of following that path is positive. Since there are finitely many states, there is a positive lower bound \(\varepsilon\) on these chosen path probabilities. Set \(N=|S|\). From any state not yet in a closed class, the conditional probability of entering one within the next \(N\) steps is at least \(\varepsilon\); a state already in a closed class has already entered one. By the Markov property, the probability of avoiding all closed classes for \(kN\) steps is at most \((1-\varepsilon)^k\). This tends to zero as \(k\to\infty\), proving eventual entry with probability \(1\).
Now let \(C\) be the states outside all closed classes. For \(i\in C\), conditioning on the first step gives \(h_i=r_i+\sum_{j\in C}p_{ij}h_j\): a step into \(A\) succeeds, a step into a non-target closed class fails, and a step into \(C\) leaves the same hitting-probability problem from the new state. In vector form, \(\mathbf{h}_C=\mathbf{r}+Q\mathbf{h}_C\).
To justify solving this equation, the sum of row \(i\) of \(Q^n\) is the probability, starting from \(i\in C\), of remaining in \(C\) for the next \(n\) steps. The geometric bound just proved implies that these row sums decay geometrically in blocks of \(N\) steps. Therefore the matrix series \(\sum_{n\ge0}Q^n\) converges entry by entry. For every \(m\ge0\), $$(\mathbf{I}-Q)\sum_{n=0}^{m}Q^n=\mathbf{I}-Q^{m+1}.$$ The row sums of \(Q^{m+1}\) tend to zero, so taking the limit gives \((\mathbf{I}-Q)\sum_{n\ge0}Q^n=\mathbf{I}\). The same multiplication in the other order gives the identity as well; hence \(\mathbf{I}-Q\) is invertible and its inverse is the series. Applying it to \(\mathbf{r}\) yields the stated formula. \(\square\)
The formula has a direct interpretation: \(Q^n\mathbf{r}\) gives the probability of spending \(n\) transitions within \(C\) and then stepping into \(A\). Adding over \(n\) counts every possible first entrance into the target. The mass not counted is the probability of eventually entering a non-target closed class.
Calculating Target-Hitting Probabilities
Worked Example: Two Transient States and Two Absorbing Outcomes
Consider \(S=\{0,1,2,3\}\), with target \(A=\{2\}\). States \(2\) and \(3\) are absorbing, but state \(3\) is not a target. Find the probability of reaching \(2\) from every starting state. In the state order \(0,1,2,3\), the transition matrix is $$ P=\begin{bmatrix} 0&\tfrac12&\tfrac14&\tfrac14\\ \tfrac12&0&\tfrac14&\tfrac14\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}. $$ The row sums are \(0+\tfrac12+\tfrac14+\tfrac14=1\), \(\tfrac12+0+\tfrac14+\tfrac14=1\), \(0+0+1+0=1\), and \(0+0+0+1=1\).
The transient set is \(C=\{0,1\}\). The part of the matrix for transitions within \(C\) and the one-step probabilities of entering the target are $$ Q=\begin{bmatrix}0&\tfrac12\\\tfrac12&0\end{bmatrix}, \qquad \mathbf{r}=\begin{bmatrix}\tfrac14\\\tfrac14\end{bmatrix}. $$ Writing the unknown probabilities as \(h_0,h_1\), the first-step equations are \(h_0=\tfrac14+\tfrac12h_1\) and \(h_1=\tfrac14+\tfrac12h_0\). Substitute the second equation into the first: \(h_0=\tfrac14+\tfrac18+\tfrac14h_0\), so \(\tfrac34h_0=\tfrac38\) and \(h_0=\tfrac12\). Then \(h_1=\tfrac14+\tfrac14=\tfrac12\). The boundary probabilities are \(h_2=1\) and \(h_3=0\).
Check: The equations give \(\tfrac14+\tfrac12(\tfrac12)=\tfrac12\) for each transient state. From either transient state, the remaining probability \(\tfrac12\) is the probability of being absorbed at the non-target state \(3\).
Worked Example: A Closed Class That Is Not Absorbing State by State
Let \(S=\{0,1,2,3,4\}\), with target \(A=\{2\}\). States \(3\) and \(4\) form a closed class: the chain alternates between them. In the state order \(0,1,2,3,4\), take $$ P=\begin{bmatrix} 0&\tfrac12&\tfrac14&\tfrac14&0\\ \tfrac14&0&\tfrac12&\tfrac14&0\\ 0&0&1&0&0\\ 0&0&0&0&1\\ 0&0&0&1&0 \end{bmatrix}. $$ The row sums are \(0+\tfrac12+\tfrac14+\tfrac14+0=1\), \(\tfrac14+0+\tfrac12+\tfrac14+0=1\), \(0+0+1+0+0=1\), \(0+0+0+0+1=1\), and \(0+0+0+1+0=1\).
The transient states are again \(0,1\); the closed non-target class is \(\{3,4\}\). The equations are \(h_0=\tfrac14+\tfrac12h_1\) and \(h_1=\tfrac12+\tfrac14h_0\). Substituting gives \(h_0=\tfrac14+\tfrac14+\tfrac18h_0\), hence \(\tfrac78h_0=\tfrac12\) and \(h_0=\tfrac47\). Then \(h_1=\tfrac12+\tfrac17=\tfrac9{14}\). States \(3\) and \(4\) have hitting probability \(0\), and state \(2\) has hitting probability \(1\).
Check: For state \(0\), \(\tfrac14+\tfrac12(\tfrac9{14})=\tfrac7{28}+\tfrac9{28}=\tfrac47\). For state \(1\), \(\tfrac12+\tfrac14(\tfrac47)=\tfrac7{14}+\tfrac2{14}=\tfrac9{14}\). Entering \(\{3,4\}\) prevents any later visit to the target, even though neither state in that class is individually absorbing.
Worked Example: Probabilities of Two Target Outcomes
Use the matrix in the first example, but now let \(A=\{2,3\}\): either absorbing state counts as a target. First calculate the probability of reaching state \(2\) specifically. For states \(0,1\), the one-step probabilities of entering \(2\) are both \(\tfrac14\), so the equations give \(g_0=\tfrac14+\tfrac12g_1\) and \(g_1=\tfrac14+\tfrac12g_0\). Solving as before gives \(g_0=g_1=\tfrac12\).
To calculate the probability of reaching state \(3\) specifically, the one-step probabilities of entering \(3\) are again both \(\tfrac14\). Thus \(f_0=\tfrac14+\tfrac12f_1\) and \(f_1=\tfrac14+\tfrac12f_0\), giving \(f_0=f_1=\tfrac12\). The two outcomes are disjoint, so the probability of reaching either target is \(g_i+f_i=1\) for \(i=0,1\). Starting in state \(2\) or \(3\), the probability of reaching the target set is also \(1\).
Check: From state \(0\), the first step enters \(2\) or \(3\) with total probability \(\tfrac14+\tfrac14=\tfrac12\), and goes to state \(1\) with probability \(\tfrac12\). The calculated total probability is \(\tfrac12+\tfrac12(1)=1\). The same check from state \(1\) gives \(\tfrac14+\tfrac14+\tfrac12(1)=1\).
Common Mistake: Assuming the Target Is Eventually Reached
A common error is to treat the probabilities of target outcomes as if they must sum to \(1\). In the first example, the probability of absorption at target state \(2\) is \(\tfrac12\) from state \(0\); the probability of absorption at non-target state \(3\) is also \(\tfrac12\). A mistaken normalization might divide the target probability by the total probability of target outcomes and report \(1\). That is a conditional probability given that a target is reached, not the unconditional probability of ever reaching the target. Here the unconditional probability is \(\tfrac12\).
Another warning sign is attempting to include a closed non-target class in \(Q\). For the alternating class \(\{3,4\}\), its transition block is \(\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Subtracting this block from the identity gives \(\begin{bmatrix}1&-1\\-1&1\end{bmatrix}\), which is singular. Those states should be assigned boundary value \(0\), not included among the transient states in the inverse formula.
The distinction is useful in applications where “failure to reach the target” is itself meaningful: an epidemic process may enter a persistent regime, a reliability system may become trapped in a non-target operating class, or a population process may avoid a specified state forever. The target probability describes the chance of success, not merely the distribution of outcomes conditional on eventual success.
Check Your Understanding
For each question, distinguish target absorption from entry into a non-target closed class.
- In the first worked example, what is the probability of reaching state \(2\) from state \(1\), and what is the probability of instead reaching state \(3\)?
- Why does the class \(\{3,4\}\) in the second example have hitting probability \(0\), even though transitions within that class continue forever?
- For a finite chain, why can the probability of avoiding every closed class for \(kN\) steps be bounded by a geometric sequence?
- In the first worked example, write the two first-step equations for the probability of hitting state \(3\), and solve them.
- What does normalizing target-outcome probabilities to sum to \(1\) calculate when there is a positive probability of entering a non-target closed class?