Tutorials › Stochastic Processes › Competing Absorption Outcomes

Home  /  Tutorials  /  Absorption, Hitting Times and First-Step Analysis

Absorption, Hitting Times and First-Step Analysis · Tutorial 235 of 994

Competing Absorption Outcomes

Set one boundary value for each absorbing outcome, solve the resulting probability equations, and interpret them for specified starting states or distributions.

Intermediate 9 min read

What You'll Learn

  • Define the absorption time and the event corresponding to each absorbing outcome.
  • Set distinct boundary values for the separate outcomes.
  • Derive and solve first-step equations for multiple absorption probabilities.
  • Check solutions by substitution and by summing the outcome probabilities.
  • Combine state-specific probabilities under a specified initial distribution.
  • Recognize when failure of eventual absorption can make the equations non-unique.

Several Possible Absorption Outcomes

A chain may stop in one of several absorbing states, and the question is then not only whether absorption occurs but which outcome occurs. Examples include a patient reaching one of several mutually exclusive clinical endpoints, a gambler being ruined at either boundary, or a system entering one of several terminal configurations. The calculation is a first-step analysis with a separate probability function for each outcome: the boundary values are different for different absorbing states.

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})\). Thus \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\), and each row sums to \(1\). Let \(A=\{a_1,\ldots,a_r\}\) be a set of distinct absorbing states, so \(p_{a_\ell a_\ell}=1\) for each \(\ell\). Define the absorption time \(T_A=\inf\{n\ge0:X_n\in A\}\), where \(\inf\varnothing=\infty\). Assume that \(\mathbb{P}_i(T_A<\infty)=1\) for every \(i\in S\setminus A\). This assumption ensures that exactly one of the absorbing outcomes is eventually reached.

Definition: For each outcome \(a_\ell\), its absorption-probability function is \(h_i^{(\ell)}=\mathbb{P}_i(X_{T_A}=a_\ell)\). At an absorbing state \(a_j\), the boundary value is \(h_{a_j}^{(\ell)}=1\) if \(j=\ell\), and \(h_{a_j}^{(\ell)}=0\) if \(j\ne\ell\). For a nonabsorbing state \(i\), the first-step equation is \(h_i^{(\ell)}=\sum_{j\in S}p_{ij}h_j^{(\ell)}\).

The boundary values encode which outcome is being counted. For the probability of absorption at \(a_\ell\), reaching \(a_\ell\) contributes \(1\), while reaching any other absorbing state contributes \(0\). The first-step equation follows by conditioning on the state after one transition. It applies to each outcome separately; solving only one of these equations does not by itself give the probabilities of the other outcomes.

Why the Equations Give the Outcome Probabilities

Theorem: Suppose \(S\) is finite, \(A=\{a_1,\ldots,a_r\}\) consists of distinct absorbing states, and \(\mathbb{P}_i(T_A<\infty)=1\) for every \(i\notin A\). For each \(\ell\), the absorption probabilities \(h_i^{(\ell)}\) are the unique functions on \(S\) satisfying the stated boundary values and the first-step equations on \(S\setminus A\). Moreover, for every starting state \(i\), \(\sum_{\ell=1}^r h_i^{(\ell)}=1\).

Proof. Fix an outcome index \(\ell\). First, if the chain starts at \(a_j\), then \(T_A=0\) and \(X_{T_A}=a_j\), so the stated boundary values follow. If \(i\notin A\), condition on \(X_1\). Given \(X_1=j\), the Markov property says that the probability of eventually being absorbed at \(a_\ell\) is \(h_j^{(\ell)}\). Summing over the possible next states gives \(h_i^{(\ell)}=\sum_{j\in S}p_{ij}h_j^{(\ell)}\).

To prove uniqueness, let \(u:S\to\mathbb{R}\) be any other solution with the same boundary values and first-step equations. Let \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) be the natural filtration. For a chain started at \(i\), the stopped sequence \(u(X_{n\wedge T_A})\) has constant expectation. Indeed, on \(\{T_A\le n\}\) its value does not change at the next step. On \(\{T_A>n\}\), the current state is outside \(A\), and conditioning on \(\mathcal{F}_n\) gives \(\mathbb{E}_i[u(X_{n+1})\mid\mathcal{F}_n]=\sum_jp_{X_nj}u(j)=u(X_n)\). Thus \(\mathbb{E}_i[u(X_{(n+1)\wedge T_A})]=\mathbb{E}_i[u(X_{n\wedge T_A})]\), and iteration gives \(\mathbb{E}_i[u(X_{n\wedge T_A})]=u(i)\).

Because \(S\) is finite, \(u\) is bounded. By the assumption \(T_A<\infty\) almost surely, \(X_{n\wedge T_A}\) eventually equals \(X_{T_A}\) almost surely. Bounded convergence therefore gives \(u(i)=\mathbb{E}_i[u(X_{T_A})]\). The boundary values imply that this expectation is \(\mathbb{P}_i(X_{T_A}=a_\ell)=h_i^{(\ell)}\), proving uniqueness. Finally, \(T_A<\infty\) almost surely and the states \(a_1,\ldots,a_r\) are distinct, so exactly one event \(\{X_{T_A}=a_\ell\}\) occurs. Adding their probabilities gives \(\sum_{\ell=1}^r h_i^{(\ell)}=1\). \(\square\)

This result gives two useful checks. First, every computed function must satisfy its own boundary values and equations. Second, for each starting state, the outcome probabilities must be nonnegative and sum to \(1\). The sum check is not a substitute for solving the separate equations: it confirms that the outcomes have been accounted for, but does not identify their individual probabilities.

Solving for Competing Outcomes

Worked Example: Two Absorbing Outcomes

Consider states \(0,1,A,B\), where \(A\) and \(B\) are absorbing. Find the probabilities of eventual absorption at \(A\) and \(B\) from each of states \(0\) and \(1\).

In the state order \((0,1,A,B)\), let the transition matrix be

$$ P= \begin{bmatrix} 0&\tfrac12&\tfrac13&\tfrac16\\ \tfrac14&0&\tfrac14&\tfrac12\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}. $$

The row sums are \(0+\tfrac12+\tfrac13+\tfrac16=1\), \(\tfrac14+0+\tfrac14+\tfrac12=1\), \(0+0+1+0=1\), and \(0+0+0+1=1\). From state \(0\), the probability of entering an absorbing state in one step is \(\tfrac13+\tfrac16=\tfrac12\); from state \(1\), it is \(\tfrac14+\tfrac12=\tfrac34\). Thus at each step before absorption, the conditional probability of absorption is at least \(\tfrac12\). The probability of still being unabsorbed after \(n\) steps is at most \((\tfrac12)^n\), which tends to zero. The theorem applies.

Write \(x_i=h_i^{(A)}\). The boundary values are \(x_A=1\) and \(x_B=0\), so the equations for the two other states are

$$ x_0=\tfrac12x_1+\tfrac13,\qquad x_1=\tfrac14x_0+\tfrac14. $$

Substitute the second equation into the first: \(x_0=\tfrac12(\tfrac14x_0+\tfrac14)+\tfrac13=\tfrac18x_0+\tfrac18+\tfrac13=\tfrac18x_0+\tfrac{11}{24}\). Hence \(\tfrac78x_0=\tfrac{11}{24}\), giving \(x_0=\tfrac{11}{21}\). Then \(x_1=\tfrac14(\tfrac{11}{21})+\tfrac14=\tfrac{11}{84}+\tfrac{21}{84}=\tfrac{8}{21}\).

There are only two absorbing outcomes, and absorption occurs almost surely, so the probabilities of absorption at \(B\) are \(1-x_0=\tfrac{10}{21}\) from state \(0\) and \(1-x_1=\tfrac{13}{21}\) from state \(1\).

Check: The \(A\)-equations give \(\tfrac12(\tfrac{8}{21})+\tfrac13=\tfrac{4}{21}+\tfrac{7}{21}=\tfrac{11}{21}\) and \(\tfrac14(\tfrac{11}{21})+\tfrac14=\tfrac{11}{84}+\tfrac{21}{84}=\tfrac{8}{21}\). The \(B\)-probabilities satisfy \(\tfrac12(\tfrac{13}{21})+\tfrac16=\tfrac{13}{42}+\tfrac{7}{42}=\tfrac{10}{21}\) from state \(0\), and \(\tfrac14(\tfrac{10}{21})+\tfrac12=\tfrac{10}{84}+\tfrac{42}{84}=\tfrac{13}{21}\) from state \(1\). Each pair sums to \(1\).

With three or more outcomes, the same rule applies: solve one boundary-value problem for each outcome. It is often convenient to check the answers both by substituting into the equations and by adding the outcome probabilities state by state.

Worked Example: Three Competing Outcomes

Let the state space be \(\{x,y,R,S,T\}\), with absorbing states \(R,S,T\). Find all three absorption probabilities from \(x\) and \(y\).

In the order \((x,y,R,S,T)\), take

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

The row sums are \(\tfrac14+\tfrac14+\tfrac14+\tfrac14+0=1\), \(\tfrac14+0+0+\tfrac12+\tfrac14=1\), and \(1\) for each of the last three rows. From either \(x\) or \(y\), the probability of entering an absorbing state on the next step is at least \(\tfrac12\). Therefore the probability of avoiding absorption for \(n\) steps is at most \((\tfrac12)^n\), so absorption occurs almost surely.

For outcome \(R\), write \(r_x,r_y\). The boundary values are \(r_R=1,r_S=0,r_T=0\), and the equations are \(r_x=\tfrac14r_x+\tfrac14r_y+\tfrac14\) and \(r_y=\tfrac14r_x\). Substitution gives \(r_x=\tfrac14r_x+\tfrac1{16}r_x+\tfrac14=\tfrac5{16}r_x+\tfrac14\), so \(\tfrac{11}{16}r_x=\tfrac14\), \(r_x=\tfrac4{11}\), and \(r_y=\tfrac1{11}\).

For outcome \(S\), the equations with boundary values \(s_R=0,s_S=1,s_T=0\) are \(s_x=\tfrac14s_x+\tfrac14s_y+\tfrac14\) and \(s_y=\tfrac14s_x+\tfrac12\). Thus \(s_x=\tfrac14s_x+\tfrac1{16}s_x+\tfrac18+\tfrac14=\tfrac5{16}s_x+\tfrac38\), giving \(s_x=\tfrac6{11}\). Then \(s_y=\tfrac14(\tfrac6{11})+\tfrac12=\tfrac3{22}+\tfrac{11}{22}=\tfrac7{11}\).

For outcome \(T\), the boundary values are \(t_R=0,t_S=0,t_T=1\). The equations are \(t_x=\tfrac14t_x+\tfrac14t_y\) and \(t_y=\tfrac14t_x+\tfrac14\). Substitution gives \(t_x=\tfrac14t_x+\tfrac1{16}t_x+\tfrac1{16}=\tfrac5{16}t_x+\tfrac1{16}\), so \(t_x=\tfrac1{11}\). Then \(t_y=\tfrac1{44}+\tfrac14=\tfrac{12}{44}=\tfrac3{11}\).

Check: At \(x\), the three probabilities sum to \(\tfrac4{11}+\tfrac6{11}+\tfrac1{11}=1\); at \(y\), they sum to \(\tfrac1{11}+\tfrac7{11}+\tfrac3{11}=1\). Substitution into the \(R\)-equations gives \(\tfrac14(\tfrac4{11})+\tfrac14(\tfrac1{11})+\tfrac14=\tfrac{11}{44}=\tfrac4{11}\) and \(\tfrac14(\tfrac4{11})=\tfrac1{11}\). The \(S\)-equations give \(\tfrac14(\tfrac6{11})+\tfrac14(\tfrac7{11})+\tfrac14=\tfrac{22}{44}=\tfrac6{11}\) and \(\tfrac14(\tfrac6{11})+\tfrac12=\tfrac7{11}\). The \(T\)-equations give \(\tfrac14(\tfrac1{11})+\tfrac14(\tfrac3{11})=\tfrac1{11}\) and \(\tfrac14(\tfrac1{11})+\tfrac14=\tfrac3{11}\).

Specified Initial Distributions

Result: Let \(\mu\) be an initial distribution, written as a row vector on \(S\). The probability that the chain is eventually absorbed at \(a_\ell\) is \(\sum_{i\in S}\mu_i h_i^{(\ell)}\).

Proof. Condition on the initial state \(X_0=i\). Its probability is \(\mu_i\), and conditional on that state the probability of absorption at \(a_\ell\) is \(h_i^{(\ell)}\). The disjoint cases \(X_0=i\) cover the state space, so adding their contributions gives \(\sum_{i\in S}\mu_i h_i^{(\ell)}\). \(\square\)

Worked Example: Combining Starting States and Immediate Absorption

Use the two-outcome chain in the first worked example. Suppose the initial distribution, in state order \((0,1,A,B)\), is \(\mu=(\tfrac13,\tfrac12,\tfrac1{12},\tfrac1{12})\). Its entries sum to \(\tfrac4{12}+\tfrac6{12}+\tfrac1{12}+\tfrac1{12}=1\). Find the eventual outcome probabilities.

Starting in \(A\) means absorption at \(A\) immediately, and starting in \(B\) means absorption at \(B\) immediately. Therefore the probability of outcome \(A\) is \(\mu_A+\mu_0h_0^{(A)}+\mu_1h_1^{(A)}+\mu_Bh_B^{(A)}\). Substituting the initial masses and the already checked state-specific probabilities gives

$$ \mathbb{P}_\mu(X_{T_A}=A) =\tfrac1{12}+\tfrac13\cdot\tfrac{11}{21} +\tfrac12\cdot\tfrac8{21}+\tfrac1{12}\cdot0 =\tfrac{21}{252}+\tfrac{44}{252}+\tfrac{48}{252} =\tfrac{113}{252}. $$

The probability of outcome \(B\) is \(\mu_B+\mu_0h_0^{(B)}+\mu_1h_1^{(B)}+\mu_Ah_A^{(B)}\), so

$$ \mathbb{P}_\mu(X_{T_A}=B) =\tfrac1{12}+\tfrac13\cdot\tfrac{10}{21} +\tfrac12\cdot\tfrac{13}{21}+\tfrac1{12}\cdot0 =\tfrac{21}{252}+\tfrac{40}{252}+\tfrac{78}{252} =\tfrac{139}{252}. $$

Check: \(\tfrac{113}{252}+\tfrac{139}{252}=\tfrac{252}{252}=1\). The terms \(\tfrac1{12}\) in the two calculations are the initial probabilities of already being in the corresponding absorbing state.

When the Equations Need Care

Eventual absorption is an important hypothesis, not a formality. For example, add a nonabsorbing state \(C\) with \(p_{CC}=1\), alongside absorbing states \(A\) and \(B\). From \(C\), neither outcome is ever reached, so the actual probabilities of absorption at \(A\) and \(B\) are both zero. But the equation for the probability \(u_C\) of absorption at \(A\) is \(u_C=u_C\), which does not determine a unique value. The equation alone cannot replace the assumption that absorption occurs almost surely.

Common mistake: assigning boundary value \(1\) to every absorbing state. In the first example, that mistake would count absorption at either \(A\) or \(B\) as success when solving for outcome \(A\). The resulting equations would be \(g_0=\tfrac12g_1+\tfrac13+\tfrac16=\tfrac12g_1+\tfrac12\) and \(g_1=\tfrac14g_0+\tfrac14+\tfrac12=\tfrac14g_0+\tfrac34\). Solving gives \(g_0=1\) and \(g_1=1\): the probability of absorption somewhere, not the probability of absorption specifically at \(A\). For the \(A\)-outcome equation, the correct boundary values are \(h_A^{(A)}=1\) and \(h_B^{(A)}=0\). Separate outcomes require separate boundary assignments.

Check Your Understanding

For each question, state the outcome boundary values before solving or interpreting the equations.

  1. A chain has absorbing states \(L\) and \(R\). What boundary values should be used to calculate the probability of absorption at \(L\)?
  2. Why does the sum of the outcome probabilities equal \(1\) when absorption occurs almost surely?
  3. For the three-outcome example, verify the first-step equation for \(s_y\) by substituting \(s_y=\tfrac7{11}\) and \(s_x=\tfrac6{11}\).
  4. If the initial distribution assigns mass to an absorbing state, how does that mass contribute to the outcome probability?
  5. Give a reason that the equation \(u_C=u_C\) does not determine an absorption probability from \(C\).

Previous

Next

Back to Tutorials