Mathwords logoMathwords

Absorbing Markov Chain — Definition, Formula & Example

An absorbing Markov chain is a Markov chain with finitely many states and at least one trap state that, once entered, is never left, and from every other state it is possible to reach a trap eventually. Over time the process is certain to end up stuck in one of these trap states.

A state ii is absorbing if pii=1p_{ii} = 1. A finite Markov chain is absorbing if it has at least one absorbing state and every state can reach some absorbing state in a finite number of steps. Non-absorbing states are called transient. Listing transient states first puts the transition matrix in canonical form P=(QR0I)P = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}. Here QQ holds transient-to-transient probabilities and RR holds transient-to-absorbing probabilities.

Key Formula

N=(I−Q)−1,t=N1,B=NRN = (I - Q)^{-1}, \qquad \mathbf{t} = N\mathbf{1}, \qquad B = NR
Where:
  • QQ = Square matrix of transition probabilities between transient states
  • RR = Matrix of probabilities of moving from a transient state directly into an absorbing state
  • NN = Fundamental matrix; entry nijn_{ij} is the expected number of visits to transient state jj when starting from transient state ii
  • t\mathbf{t} = Column vector of expected number of steps before absorption from each transient state
  • 1\mathbf{1} = Column vector of all ones
  • BB = Absorption probability matrix; entry bijb_{ij} is the probability of ending in absorbing state jj when starting from transient state ii

Worked Example

Problem: You start with $1 and bet $1 on each flip of a fair coin, winning or losing $1 each round. You stop as soon as you have $0 (broke) or $3 (your goal). What is the probability you reach $3, and how many rounds does the game last on average?
Step 1: The states are $0, $1, $2, $3. States $0 and $3 are absorbing. List the transient states ($1, $2) first. Then read off Q (rows and columns ordered $1, $2) and R (rows $1, $2; columns $0, $3).
Q=(012120),R=(120012)Q = \begin{pmatrix} 0 & \tfrac12 \\ \tfrac12 & 0 \end{pmatrix}, \qquad R = \begin{pmatrix} \tfrac12 & 0 \\ 0 & \tfrac12 \end{pmatrix}
Step 2: Compute the fundamental matrix. The determinant of I − Q is 1 − 1/4 = 3/4.
N=(I−Q)−1=(1−12−121)−1=43(112121)=(43232343)N = (I-Q)^{-1} = \begin{pmatrix} 1 & -\tfrac12 \\ -\tfrac12 & 1 \end{pmatrix}^{-1} = \frac{4}{3}\begin{pmatrix} 1 & \tfrac12 \\ \tfrac12 & 1 \end{pmatrix} = \begin{pmatrix} \tfrac43 & \tfrac23 \\ \tfrac23 & \tfrac43 \end{pmatrix}
Step 3: Row sums of N give the expected number of rounds. The product NR gives the absorption probabilities. The first row of each result corresponds to starting with $1.
t=N1=(22),B=NR=(23131323)\mathbf{t} = N\mathbf{1} = \begin{pmatrix} 2 \\ 2 \end{pmatrix}, \qquad B = NR = \begin{pmatrix} \tfrac23 & \tfrac13 \\ \tfrac13 & \tfrac23 \end{pmatrix}
Answer: Starting with $1, you reach $3 with probability 1/3 and go broke with probability 2/3. The game lasts 2 rounds on average.

Why It Matters

Absorbing chains answer "where does it end, and how long does it take" questions in a stochastic processes or finite math course. Examples include gambler's ruin, whether a gene becomes fixed in a population, and how long a loan stays current before it is paid off or defaults.

Common Mistakes

Mistake: Calling a chain absorbing just because it has one absorbing state.
Correction: Every transient state must also be able to reach an absorbing state. If some group of states loops among itself with no path to a trap, the chain is not absorbing, and I − Q may fail to be invertible.

Related Terms

  • Markov Chain — General model that absorbing chains specialize with trap states
  • Markov Process — Broader memoryless process family that includes absorbing chains
  • Conditional Probability — Each transition probability is conditional on the current state
  • Transition Matrix — Matrix of state-to-state probabilities describing the chain
  • Stochastic — Broader class of random processes this chain belongs to