5.5 Absorption and ergodicity

Definition of absorption

Absorption describes a situation where a Markov chain reaches a state (or set of states) it can never leave. Once the chain enters an absorbing state, it stays there permanently. Whether absorption occurs, and how quickly, depends entirely on the transition probabilities and structure of the chain.

Absorbing states

A state $i$ is absorbing if, once entered, the chain cannot leave it. Formally, this means:

• $p_{ii} = 1$
• $p_{ij} = 0$ for all $j \neq i$

Think of the final square in Chutes and Ladders: once you land there, the game is over. Similarly, in an equipment failure model, a "permanently broken" state with no possibility of repair is absorbing.

A Markov chain is called an absorbing chain if it has at least one absorbing state and every non-absorbing (transient) state can eventually reach some absorbing state.

Canonical form of the transition matrix

For an absorbing Markov chain, you can rearrange the states so that absorbing states come first and transient states come second. This gives the canonical form:

$P = \begin{bmatrix} I & 0 \\ R & Q \end{bmatrix}$

where:

• $I$ is the identity matrix (absorbing states transition only to themselves)
• $0$ is a zero matrix (absorbing states never transition to transient states)
• $R$ contains the one-step probabilities of moving from each transient state to each absorbing state
• $Q$ contains the transition probabilities among transient states

Arranging the matrix this way makes it much easier to compute absorption probabilities and expected absorption times. It also reveals the communication structure: if $R$ has multiple non-zero columns, the chain can be absorbed into more than one absorbing state.

Absorption probabilities

Absorption probabilities tell you, for a given starting state, how likely the chain is to end up in each absorbing state. Computing these requires the fundamental matrix, which encodes everything about the chain's behavior before absorption.

Fundamental matrix

The fundamental matrix $N$ is defined as:

$N = (I - Q)^{-1}$

where $Q$ is the transient-to-transient block from the canonical form. Each entry $n_{ij}$ gives the expected number of times the chain visits transient state $j$, given that it started in transient state $i$, before absorption occurs.

This matrix exists (i.e., $(I - Q)$ is invertible) whenever the chain is truly absorbing, because the eigenvalues of $Q$ all have magnitude strictly less than 1.

Computing absorption probabilities

The matrix of absorption probabilities is:

$B = NR$

Each entry $b_{ij}$ gives the probability that the chain, starting in transient state $i$, is eventually absorbed into absorbing state $j$. The rows of $B$ sum to 1, since the chain must eventually be absorbed somewhere.

Expected number of steps until absorption

To find how long absorption takes on average, compute:

$\vec{t} = N\vec{1}$

where $\vec{1}$ is a column vector of all ones. Each entry $t_i$ is the expected number of steps before the chain gets absorbed, starting from transient state $i$.

For example, in the gambler's ruin problem with a starting stake of $5 and absorbing states at $0 (broke) and $10 (target), $t_5$ tells you the average number of bets before the game ends.

Ergodicity

Ergodicity describes a completely different kind of long-term behavior: instead of getting trapped, the chain settles into a stable equilibrium. An ergodic chain converges to a unique stationary distribution no matter where it starts.

Definition of ergodicity

A Markov chain is ergodic if it satisfies two conditions:

1. Irreducibility: For every pair of states $i$ and $j$, there exists some number of steps $n > 0$ such that $p_{ij}^{(n)} > 0$. Every state can eventually be reached from every other state.
2. Aperiodicity: No state is forced into a deterministic cycle. Formally, the greatest common divisor of the set $\{n \geq 1 : p_{ii}^{(n)} > 0\}$ equals 1 for all states $i$.

Together, these guarantee that the chain "mixes" thoroughly over time and doesn't get stuck in subsets of states or oscillate between groups.

Examples of ergodic Markov chains

• A random walk on a connected, non-bipartite graph. Connectedness gives irreducibility; the non-bipartite structure prevents periodicity.
• A weather model where each day's weather depends on the previous day, with positive probability of transitioning between all weather types.

Stationary distributions

A probability vector $\vec{\pi}$ is a stationary distribution if it satisfies:

$\vec{\pi} = \vec{\pi} P$

This means that if the chain's state distribution is $\vec{\pi}$ at some time step, it remains $\vec{\pi}$ at the next step and every step after that.

For an ergodic chain, the stationary distribution has a concrete interpretation: $\pi_j$ equals the long-run fraction of time the chain spends in state $j$.

Uniqueness of the stationary distribution

A central result for ergodic chains: the stationary distribution $\vec{\pi}$ is unique, and it is also the limiting distribution. That is, for any initial distribution $\vec{\mu}$:

$\lim_{n \to \infty} \vec{\mu} P^n = \vec{\pi}$

This is powerful because it means long-run predictions don't depend on where the chain started. In a model of a chemical reaction at equilibrium, for instance, the unique stationary distribution gives the equilibrium concentrations of reactants and products.

Ergodicity vs absorption

These two properties represent fundamentally different long-term outcomes for a Markov chain, and they are mutually exclusive.

Differences in long-term behavior

• Ergodic chains keep evolving forever, converging to a unique stationary distribution. The long-term behavior is the same regardless of the starting state.
• Absorbing chains eventually stop evolving. The chain reaches an absorbing state and stays there. Which absorbing state it reaches (and how long it takes) does depend on the starting state.

Why they can't coexist

The key distinction comes down to irreducibility. An ergodic chain must be irreducible, meaning every state communicates with every other state. An absorbing chain has at least one absorbing state that, once entered, blocks transitions to all other states. This directly violates irreducibility. So a chain cannot be both ergodic and absorbing.

A chain with absorbing states can still have transient states that communicate with each other, but the overall chain fails the irreducibility requirement for ergodicity.

Classic examples

Applications of absorption and ergodicity

Queueing theory

Markov chains model waiting lines where states represent the number of customers in the system. If a queue can permanently empty or hit a hard capacity limit, those are absorbing states. If arrival and service rates balance so the queue fluctuates around a steady level, the chain is ergodic and the stationary distribution describes the long-run distribution of queue lengths. Applications include call centers, manufacturing buffers, and packet queues at network routers.

Population dynamics

Absorbing models capture extinction events: a population of size zero is absorbing because a species can't recover from extinction. Ergodic models apply when birth and death rates balance, producing a stable population distribution. Specific examples include genetic drift of alleles in finite populations (absorbing, since fixation of one allele is permanent) and endemic disease models where infection levels fluctuate around an equilibrium (ergodic).

PageRank algorithm

Google's original PageRank treats web pages as states and hyperlinks as transitions. A raw web graph isn't ergodic because of "dangling nodes" (pages with no outgoing links) and disconnected components. PageRank fixes this by adding a damping factor (typically around 0.85): at each step, the surfer follows a link with probability 0.85 and jumps to a uniformly random page with probability 0.15. This makes the chain both irreducible and aperiodic, guaranteeing a unique stationary distribution. Each page's stationary probability becomes its PageRank score, reflecting its importance in the web's link structure.