Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 36 ยท Markov Chains

Absorbing Chains and Hitting Probabilities

Analyze absorbing Markov chains: canonical form, the fundamental matrix N = (I - Q)^-1, expected time to absorption and absorption probabilities, in Python.

An absorbing chain has at least one absorbing state and can reach an absorbing state from anywhere. Typical stories: a game that ends when you are broke or reach your goal, a patient who recovers or dies, a customer who converts or leaves. The questions are always the same. How long until the process stops? And in which absorbing state does it end?

Both questions are answered by one matrix, built from the transient part of the chain.

Canonical form

Number the states so that the t transient states come first and the r absorbing states last. The transition matrix then has blocks:

Text
        transient  absorbing
P  =  [     Q          R     ]   transient
      [     0          I     ]   absorbing
  • Q (size t ร— t): transitions among transient states.
  • R (size t ร— r): transitions from transient into absorbing states.
  • I: absorbing states stay put.

Then P^n has Q^n in the top-left block. Because the chain is eventually absorbed, Q^n โ†’ 0.

The fundamental matrix

The expected number of visits to transient state j, starting from transient state i, is the (i, j) entry of

Text
N = I + Q + Qยฒ + Qยณ + ... = (I - Q)^(-1)

(a matrix version of the geometric series). Two things follow.

  1. Expected time to absorption from each transient state: t = N 1, the row sums of N (add up visits to all transient states).
  2. Absorption probabilities: B = N R, where B[i, k] is the probability of ending in absorbing state k when starting in transient state i. Each row of B sums to 1.

Example: the drunkard's walk

A walker stands on positions 0, 1, 2, 3, 4. At each step it moves left or right with probability 1/2. Positions 0 and 4 are absorbing (a pit and a home). The transient states are 1, 2, 3.

flowchart LR
    a0["0 (pit)"] --- a1((1)) --- a2((2)) --- a3((3)) --- a4["4 (home)"]

The walker moves one step left or right with equal chance until reaching an end.

Python Fundamental matrix of the drunkard's walk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see expected times 3, 4, 3 and, for the home end, probabilities 1/4, 1/2, 3/4: the farther right you start, the likelier you are to reach home. These match the gambler's ruin formulas of the next lesson.

A general helper

Write the analysis once for any chain, detecting absorbing states from the diagonal.

Python A reusable absorbing-chain analyzer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Checking by simulation

A formula is only trusted when it survives a test. Run the walker many times and compare the average time and fraction of home arrivals with the matrix answers.

Python Simulate the drunkard's walk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The numbers agree with the matrix computation up to simulation error.

Hitting probabilities in general

The same idea applies to any chain and any target set A. The hitting probability h_i = P(chain ever enters A | X_0 = i) satisfies

Text
h_i = 1                      if i is in A
h_i = ฮฃ_j p_ij h_j           otherwise

When this system has several solutions, the right one is the smallest non-negative solution. For finite absorbing chains, the system has a unique solution and is the same as the rows of B that you computed.

Absorbing chains are a gentle way to get a feel for linear-equation methods on chains. The fundamental matrix gives all the answers at once; solving the first-step equations for a single target gives one answer at a time.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the canonical form of an absorbing chain, Q describes...

    Q is the transient-to-transient block; R is transient-to-absorbing.
  2. 2. The fundamental matrix is defined as...

    N = I + Q + Qยฒ + ... = (I - Q)^(-1), the expected visits to transient states.
  3. 3. How do you get the expected number of steps until absorption from each transient state?

    Row i of N counts expected visits to every transient state, so its sum is the expected time spent before absorption.
  4. 4. The matrix of absorption probabilities is...

    B = N R: expected visits to each transient state times the chance of jumping to each absorbing state from there.

Summary

  • Write an absorbing chain in canonical form with blocks Q (transient to transient) and R (transient to absorbing).
  • N = (I - Q)^(-1) counts expected visits to transient states.
  • t = N 1 gives expected steps to absorption; B = N R gives absorption probabilities.
  • Hitting probabilities solve linear equations; take the smallest non-negative solution.

Next: First-Step Analysis and Gambler's Ruin