Absorption Problems

Absorbing States

An absorbing state is a state that, once entered, cannot be left:

$$p_{ii} = 1 \quad \text{(if state } i \text{ is absorbing)}$$

Examples

• Gambler’s ruin: “Broke” and “wealthy” are absorbing states
• Game completion: “Win” and “lose” are absorbing states
• System failure: “Failed” is an absorbing state

Absorption Probability

Key question: Starting from state $i$, what’s the probability of eventually being absorbed in state $j$?

Let $a_i$ = probability of absorption in a target state, starting from state $i$.

Recursion

$$a_i = \sum_k p_{ik} \cdot a_k$$

We either:

1. Transition to an absorbing state (absorbed!)
2. Transition to a transient state (recurse)

Expected Time to Absorption

Key question: Starting from state $i$, what’s the expected number of steps until absorption?

Let $t_i$ = expected time to absorption, starting from state $i$.

Recursion

$$t_i = 1 + \sum_{k \text{ transient}} p_{ik} \cdot t_k$$

We take one step, then add expected time from the new state (if not yet absorbed).

Example: Gambler’s Ruin

A gambler starts with $i and makes $1 bets. Game ends when broke ($0) or wealthy ($N).

States

• 0: Broke (absorbing)
• 1, 2, …, N-1: Playing (transient)
• N: Wealthy (absorbing)

Absorption Probabilities

Let $a_i$ = probability of reaching $N$ before $0$, starting with $i$.

For fair game (p = 0.5):

$$a_i = \frac{i}{N}$$

For biased game (p ≠ 0.5):

$$a_i = \frac{1 - (q/p)^i}{1 - (q/p)^N}$$

where $q = 1 - p$.

Expected Duration

For fair game:

$$t_i = i(N - i)$$

Solving Absorption Problems

Method

1. Identify absorbing and transient states
2. Set up equations for absorption probability or expected time
3. Use boundary conditions (absorbing states have known values)
4. Solve the system of equations

Boundary Conditions

• For absorption probability: $a_j = 1$ if $j$ is the target absorbing state, $a_j = 0$ for other absorbing states
• For expected time: $t_j = 0$ if $j$ is any absorbing state

Applications

Reliability

• System starts working
• Components fail with certain probabilities
• Absorbing state = system failure
• Question: Expected time to failure?

Games

• Player starts at some level
• Win/lose conditions are absorbing
• Question: Probability of winning?

Population Models

• Population starts at size $i$
• Extinction is absorbing
• Question: Probability of extinction?