Turning a Target Set into Absorbing States

Freeze the Chain at Its First Visit to a Target

Suppose a Markov chain has a target set $A$, and the question is whether it will ever reach that set. Its transitions after reaching $A$ do not affect the answer. We can therefore make each state in $A$ absorbing: once the modified chain enters one of them, it stays there. The important point is that this change leaves all transitions before the first visit exactly as they were. Thus the chance that the modified chain is eventually absorbed in $A$ is the original chain’s chance of ever hitting $A$.

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 transition matrix $P=(p_{ij})$. Its rows sum to $1$. Use the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$, and define $T_A=\inf\{n\ge0:X_n\in A\}$, where $\inf\varnothing=\infty$. The target set $A\subseteq S$ is assumed nonempty.

Definition: The transition matrix $P^A=(p^A_{ij})$ is obtained by keeping the original rows outside $A$ and replacing each row in $A$ with a row that stays at its own state: $$ p^A_{ij}= \begin{cases} p_{ij},&i\notin A,\\ 1,&i\in A,\ j=i,\\ 0,&i\in A,\ j\ne i. \end{cases} $$ A chain with transition matrix $P^A$ is called the chain modified to make $A$ absorbing.

Each row of $P^A$ sums to $1$: for $i\notin A$ it is the original row of $P$, and for $i\in A$ its only nonzero entry is $p^A_{ii}=1$. Thus the modification defines a transition matrix. Notice that this construction makes every state in $A$ absorbing individually. It does not combine them into one state; which state is reached can still record the first target hit.

Why the Modification Preserves the First Visit

Theorem: Start the original and modified chains from the same state, or from the same initial distribution. They can be coupled so that their paths agree through the first visit to $A$. In particular, for every $a\in A$, the probability that the modified chain is eventually absorbed at $a$ equals the probability that the original chain first enters $A$ at $a$. Summing over $a\in A$, the probability of eventual absorption in $A$ equals $\mathbb{P}(T_A<\infty)$.

Proof. Fix an ordering of the finite state space. At each step, use a shared random variable, uniform on $[0,1]$ and independent of the past, to select the next state from the transition row for the current state. For each state, divide $[0,1]$ into consecutive intervals whose lengths are the entries in that row. This gives the required transition probabilities for both chains. Give the chains the same initial state. If that state is random, draw it once from their common initial distribution and use it for both.

As long as their common current state $i$ is outside $A$, the two transition rows are identical by definition of $P^A$. Using the same random variable therefore gives the same next state. Induction shows that their paths agree at every time up to and including the first time they enter $A$. This includes the case $X_0\in A$, when both chains start at the same target state and the first visit is at time $0$. If the original chain never enters $A$, the paths continue to agree at every finite time because they remain outside $A$. If it first enters $A$ at $a$, the modified chain enters $a$ at that same time and stays there, so it is eventually absorbed at $a$. These pathwise statements give the claimed event equalities and hence the probability equalities. $\square$

The theorem is about first entry, not about preserving the whole chain. After a target is reached, the original chain may leave it, while the modified chain stays there. That difference is intentional: for a hitting question, the first entry is the outcome to record.

Result (first-step equations for target outcomes): For $a\in A$, let $g_i^a$ be the probability that the modified chain is eventually absorbed at $a$, when it starts at $i$. Then $$ g_i^a= \begin{cases} 1,&i=a,\\ 0,&i\in A,\ i\ne a,\\ \displaystyle\sum_{j\in S}p_{ij}g_j^a,&i\notin A. \end{cases} $$ For $i\notin A$, the same $g_i^a$ is the original chain’s probability of first entering $A$ at $a$.

Proof. If the modified chain starts at $a$, it is already absorbed at $a$, so $g_a^a=1$. If it starts at a different target state, that state is absorbing, so the probability of absorption at $a$ is $0$. For $i\notin A$, condition on the first transition. It moves to $j$ with probability $p_{ij}$, since the row at $i$ was not changed. Given that move, the probability of eventual absorption at $a$ is $g_j^a$, by the Markov property. Summing over all possible $j$ gives the equation. The coupling theorem identifies this absorption event with first entry at $a$ for the original chain. $\square$

For the probability of hitting any state in $A$, set $h_i=\sum_{a\in A}g_i^a$. Then $h_i=1$ for $i\in A$, and for $i\notin A$, $h_i=\sum_{j\in S}p_{ij}h_j$. These equations describe the probabilities, but they need not have a unique solution if some states can avoid every target indefinitely. In that situation, use the probability interpretation rather than assuming that any solution of the equations is the desired one. The examples below either solve the equations directly with a unique solution or make the outcome probabilities transparent.

Worked Calculations

Worked Example: One Target and a Possible Escape

Consider $S=\{1,2,3,4\}$, target $A=\{3\}$, and the original transition matrix $$ P= \begin{bmatrix} \tfrac12&\tfrac14&\tfrac14&0\\ 0&\tfrac12&0&\tfrac12\\ \tfrac12&0&0&\tfrac12\\ 0&0&0&1 \end{bmatrix}. $$ The row sums are $1$: for rows $1,2,3,4$, respectively, they are $\tfrac12+\tfrac14+\tfrac14=1$, $\tfrac12+\tfrac12=1$, $\tfrac12+\tfrac12=1$, and $1$. State $4$ is an escape state from which the target cannot be reached.

Replace row $3$ by $(0,0,1,0)$. The modified matrix is $$ P^A= \begin{bmatrix} \tfrac12&\tfrac14&\tfrac14&0\\ 0&\tfrac12&0&\tfrac12\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}. $$ Its row sums are again $1$: the first two are unchanged and sum to $1$, the third sums to $1$, and the fourth sums to $1$. Let $h_i$ be the probability of ever hitting $3$ from state $i$. The boundary values are $h_3=1$ and $h_4=0$. First-step conditioning gives $$ h_1=\tfrac12h_1+\tfrac14h_2+\tfrac14,\qquad h_2=\tfrac12h_2+\tfrac12h_4. $$ The second equation and $h_4=0$ give $\tfrac12h_2=0$, hence $h_2=0$. Substituting into the first gives $h_1=\tfrac12h_1+\tfrac14$, so $\tfrac12h_1=\tfrac14$ and $h_1=\tfrac12$.

Check: Substitution gives $\tfrac12(\tfrac12)+\tfrac14(0)+\tfrac14=\tfrac12=h_1$, and $\tfrac12(0)+\tfrac12(0)=0=h_2$. Thus from state $1$ the chance of eventual absorption at $3$, and equivalently the chance of ever hitting $3$ in the original chain, is $\tfrac12$. The remaining probability is accounted for by paths that reach state $4$.

Worked Example: Competing Target Outcomes

Now take $S=\{1,2,3,4\}$, with target set $A=\{3,4\}$, and original matrix $$ P= \begin{bmatrix} \tfrac12&\tfrac14&\tfrac14&0\\ \tfrac14&\tfrac14&\tfrac14&\tfrac14\\ \tfrac12&0&0&\tfrac12\\ 0&\tfrac12&0&\tfrac12 \end{bmatrix}. $$ The row sums are $1$: row $1$ sums to $\tfrac12+\tfrac14+\tfrac14=1$, row $2$ to four terms of $\tfrac14$, row $3$ to $\tfrac12+\tfrac12$, and row $4$ to $\tfrac12+\tfrac12$. Make states $3$ and $4$ absorbing, replacing their rows by $(0,0,1,0)$ and $(0,0,0,1)$. Both replacement rows sum to $1$; the other two rows are unchanged and sum to $1$.

Let $g_i$ be the probability that the first target reached is $3$. The boundary values are $g_3=1$ and $g_4=0$. From states $1$ and $2$, the equations are $$ g_1=\tfrac12g_1+\tfrac14g_2+\tfrac14,\qquad g_2=\tfrac14g_1+\tfrac14g_2+\tfrac14. $$ Rearranging gives $2g_1-g_2=1$ and $-g_1+3g_2=1$. The first equation gives $g_2=2g_1-1$. Substituting into the second gives $-g_1+3(2g_1-1)=1$, so $5g_1=4$, $g_1=\tfrac45$, and $g_2=2(\tfrac45)-1=\tfrac35$.

Check: At state $1$, the right side is $\tfrac12(\tfrac45)+\tfrac14(\tfrac35)+\tfrac14=\tfrac25+\tfrac3{20}+\tfrac5{20}=\tfrac45$. At state $2$, it is $\tfrac14(\tfrac45)+\tfrac14(\tfrac35)+\tfrac14=\tfrac15+\tfrac3{20}+\tfrac5{20}=\tfrac35$. The probabilities of first reaching $4$ are therefore $\tfrac15$ from state $1$ and $\tfrac25$ from state $2$: in this chain the two targets are reached eventually with probability $1$, so these are $1-g_1$ and $1-g_2$, respectively.

Worked Example: Keeping Track of Which Target Was Hit

Let $S=\{1,2,3\}$, $A=\{2,3\}$, and $$ P= \begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\ \tfrac12&0&\tfrac12\\ 0&1&0 \end{bmatrix}. $$ The row sums are $1$: row $1$ sums to $\tfrac12+\tfrac13+\tfrac16=1$, row $2$ to $\tfrac12+\tfrac12=1$, and row $3$ to $1$. Replace rows $2$ and $3$ by $(0,1,0)$ and $(0,0,1)$. Each replacement row sums to $1$, and the first row remains unchanged.

Starting from state $1$, let $g_1^2$ be the probability that the first target reached is $2$, and $g_1^3$ the probability that it is $3$. A transition from $1$ back to $1$ leaves the same question, while transitions directly to $2$ and $3$ settle it. Thus $$ g_1^2=\tfrac12g_1^2+\tfrac13,\qquad g_1^3=\tfrac12g_1^3+\tfrac16. $$ The first equation gives $\tfrac12g_1^2=\tfrac13$, so $g_1^2=\tfrac23$. The second gives $\tfrac12g_1^3=\tfrac16$, so $g_1^3=\tfrac13$.

Check: Substitution gives $\tfrac12(\tfrac23)+\tfrac13=\tfrac13+\tfrac13=\tfrac23$, and $\tfrac12(\tfrac13)+\tfrac16=\tfrac16+\tfrac16=\tfrac13$. The outcomes sum to $\tfrac23+\tfrac13=1$, as expected: from state $1$, each step has probability $\tfrac12$ of reaching a target, so the probability of staying at $1$ for $n$ consecutive steps is $(\tfrac12)^n$, which tends to $0$.

What the Transformation Does Not Guarantee

Making $A$ absorbing guarantees that each state in $A$ is absorbing. It does not guarantee that the modified chain eventually reaches $A$ from every other state. In the first example, state $4$ remains absorbing and lies outside $A$. The modified chain therefore has an absorbing state outside the chosen target set. In particular, one should not automatically treat every modified chain as a chain in which all non-target states are transient. The probability of hitting $A$ is still well-defined, but it can be less than $1$.

When the aim is to compute the probability of hitting any target, the boundary condition is $h_i=1$ for every $i\in A$. When the aim is to identify which target is hit first, keep the target states separate and impose $g_a^a=1$ and $g_b^a=0$ for distinct $a,b\in A$. The modified chain preserves that identity because it freezes at the particular state first reached.

Common mistake. In the first example, a tempting but incorrect equation is $h_3=\tfrac12h_1+\tfrac12h_4$, copied from the original transition row at state $3$. That equation asks what happens after leaving $3$, even though a visit to $3$ has already counted as a hit. The correct boundary value is $h_3=1$. Using it gives $h_2=0$ and $h_1=\tfrac12$, as verified above. The practical rule is to replace target rows before writing equations, or equivalently to impose the target boundary values explicitly.

Check Your Understanding

For each question, distinguish carefully between a first visit and what happens after that visit.

For a target set $A$, which rows of $P$ are changed to form $P^A$, and what are their entries?
Why does the modified chain’s probability of eventual absorption in $A$ equal the original chain’s probability of ever hitting $A$, even if the original chain leaves $A$ afterward?
If $A=\{a,b\}$, what boundary values should be used to compute the probability that the first target reached is $a$?
Give a reason the modified chain might fail to reach $A$ with probability $1$.
In the third worked example, why do the probabilities of first reaching states $2$ and $3$ sum to $1$?

Turning a Target Set into Absorbing States

What You'll Learn