Absorbing Markov Chains

Many real-world processes, from a software bug's lifecycle to a company's journey toward default, share a common feature: they proceed through stages until reaching a final, irreversible outcome. How can we mathematically model and predict the timeline and ultimate fate of such one-way journeys? This is the central question addressed by absorbing Markov chains, a powerful framework in probability theory for analyzing systems with terminal states. They provide what can be described as a 'calculus of endings,' allowing us to quantify processes that are fated to conclude.

This article will guide you through this fascinating subject. The first chapter, ​​"Principles and Mechanisms,"​​ will demystify the core mathematical machinery. It explains concepts like the canonical form, the fundamental matrix, and absorption probabilities to show how we can precisely calculate when and where a process will end. The subsequent chapter, ​​"Applications and Interdisciplinary Connections,"​​ will then showcase the remarkable versatility of these models, demonstrating how the same principles apply to problems in biology, finance, and ecology, revealing the universal patterns that govern systems on a path to a final destination.

Imagine a game played on a board with several squares. On each turn, you roll a die and move your piece according to some rules. Some squares are normal, but others are special: if you land on one, the game instantly ends. These are one-way doors; once you pass through, there is no coming back. This simple game holds the key to understanding a vast array of real-world processes, from the life cycle of a software bug to the fate of a startup company, all through the elegant language of ​​absorbing Markov chains​​.

In the world of Markov chains, states are like the squares on our game board. The process hops from state to state with certain probabilities. Most states are merely temporary stops, junctions in a web of possibilities. But some are different. These are the ​​absorbing states​​. An absorbing state is a trap, a final destination. Once the process enters such a state, it can never leave. The probability of staying in that state is 1, forever.

Consider a model for developing a piece of software. It might start in Development, move to Testing, and perhaps get sent back to Development if a bug is found. But eventually, it will reach one of two final states: Approved or Rejected. Once a module is stamped 'Approved', it stays approved. Once it's 'Rejected', it's discarded for good. Approved and Rejected are absorbing states. They are the end of the line. All other states, like Development and Testing, where the process is just passing through, are called ​​transient states​​.

Mathematically, we can spot an absorbing state with ease by looking at the chain's ​​transition matrix​​, $P$. This matrix is a complete rulebook, where the entry $P_{ij}$ tells us the probability of moving from state $i$ to state $j$ in one step. If state $k$ is absorbing, then the probability of staying in state $k$, $P_{kk}$, must be 1. Consequently, all other entries in that row must be 0, as the process cannot move anywhere else. Looking at the row for an absorbing state is like reading a very short, decisive story: "You are here. You will stay here."

For instance, in a warehouse where an automated vehicle moves between five locations, a transition matrix might look like this:

A quick glance at the diagonal entries reveals all. For state 2, $P_{22}=1$. For state 5, $P_{55}=1$. So, locations 2 and 5 are the absorbing states—perhaps they are charging docks or final drop-off points from which the vehicle does not continue its journey.

The very existence of an absorbing state carves the world of the Markov chain into two distinct territories. On one side, you have the transient states, a bustling network of temporary locations. On the other, you have the absorbing states, a set of final destinations.

This division has a profound consequence: any chain with an absorbing state cannot be ​​irreducible​​. An irreducible chain is one where you can, eventually, get from any state to any other state. It's a completely connected world. But if you have an absorbing state, say 'IPO' in a model of a startup's life, you can't go from 'IPO' back to the 'Seed' stage. The road is closed. The definition of commute time, which involves a round trip, becomes nonsensical because the return journey is impossible.

This natural partition allows us to organize the transition matrix $P$ into a beautifully clear block structure. If we list all the transient states first, followed by all the absorbing states, the matrix takes on a special canonical form:

Let's break this down, using the example of tracking a software bug through states New, Assigned, In Progress (transient) and Resolved, Closed (absorbing).

• The top-left block, ​​$Q$​​, is a square matrix describing the probabilities of moving between the transient states. This is the matrix of the bustling, temporary world. For instance, a bug moving from Assigned to In Progress.

• The top-right block, ​​$R$​​, is a rectangular matrix that holds the keys to escape. It describes the probabilities of moving from a transient state to an absorbing state. A bug moving from In Progress to Resolved would be an entry in $R$.

• The bottom-left block, ​​$0$​​, is a matrix of zeros. This represents the impossibility of returning from the dead. You cannot go from an absorbing state back to a transient one.

• The bottom-right block, ​​$I$​​, is the identity matrix. This simply states that once you are in an absorbing state, you stay in that absorbing state.

This structure isn't just a neat organizational trick; it is the gateway to analyzing the entire process.

If you start in a transient state, are you guaranteed to eventually fall into an absorbing one? In a finite absorbing chain, the answer is a resounding yes. Intuitively, this makes sense. From every transient state, there must be some path, however long and winding, that leads to an absorbing state. If there were a group of transient states that only led to each other, they would form a closed club, not a transient waiting room. There's always a "leak" from the transient world.

But there's a deeper, more elegant reason. Let's think about the matrix $Q$, which governs life within the transient states. The entry $(Q^n)_{ij}$ gives the probability of starting at transient state $i$ and being in transient state $j$ after $n$ steps, without ever having left the transient world. Since we've established that absorption is inevitable, this probability must dwindle to zero as time goes on, for any pair of states $i$ and $j$. This means the entire matrix $Q^n$ must approach the zero matrix as $n$ goes to infinity:

This is a powerful statement. And here's the magic: a central result in linear algebra tells us that this condition is equivalent to saying that the ​​spectral radius​​ of $Q$, denoted $\rho(Q)$, is strictly less than 1. The spectral radius is the largest magnitude of all of $Q$'s eigenvalues. This single number, $\rho(Q) \lt 1$, is the fundamental mathematical guarantee that the transient world is truly transient and that the process cannot wander there forever. It also guarantees that the matrix $(I-Q)$ is invertible, a fact that will become crucially important in a moment.

Now that we know the end is certain, we can ask more detailed questions about the journey. If we start in a transient state, say New for our software bug, how many days do we expect it to spend in the In Progress state before it is finally Resolved or Closed?

To answer this, we need to construct a remarkable tool: the ​​fundamental matrix​​, $N$. The entry $N_{ij}$ of this matrix tells us the expected number of times the process will be in transient state $j$, given that it started in transient state $i$.

Where does this matrix come from? Let's build it with a beautiful piece of logic. The total number of visits to a state is the sum of visits at step 0, plus visits at step 1, plus visits at step 2, and so on, averaged over all possibilities.

• At step 0, you are in state $j$ if and only if you start there ($i=j$). This is captured by the identity matrix, $I$.
• The matrix of probabilities of being in various transient states after 1 step is $Q$.
• After 2 steps, it's $Q^2$. After $n$ steps, it's $Q^n$.

The total expected number of visits, summed over all future time steps, is therefore represented by the matrix series:

This is a geometric series for matrices! Just as the scalar series $1 + x + x^2 + \dots$ sums to $\frac{1}{1-x}$ when $|x| \lt 1$, this matrix series converges precisely because we know the "size" of $Q$ (its spectral radius) is less than 1. The sum is:

This stunningly simple formula gives us a "crystal ball" for the entire transient journey. By calculating this single matrix inverse, we can answer questions like the one about our software bug. If we start a bug in the New state, we can find the expected number of days it will spend In Progress by simply reading the corresponding entry in the matrix $N$.

The fundamental matrix $N$ tells us about the journey, but what about the destination? Starting from a transient state, what is the probability of ending up in a specific absorbing state? For example, in our Random Walk Firewall with transient servers $S_1, S_2$ and absorbing servers $S_3, S_4$, what is the probability a packet starting at $S_1$ is ultimately absorbed by the secure server $S_3$?.

Let's reason this out. For a packet to be absorbed at $S_3$, it must make a final leap from some transient state (say, $S_j$) into $S_3$. The probability of this single leap is given by the matrix $R$ (specifically, $R_{j3}$).

To find the total probability of being absorbed at $S_3$ starting from $S_1$, we must sum over all possible "last transient states" $j$ it could have been in. For each possible last stop $j$, we need to multiply two things:

1. The expected number of times the packet visited state $S_j$, having started at $S_1$.
2. The probability of making the final jump from $S_j$ to $S_3$.

We already know the first part! It's precisely the entry $N_{1j}$ from our fundamental matrix. The second part is $R_{j3}$. So, the total probability is the sum over all transient states $j$: $\sum_j N_{1j} R_{j3}$.

This calculation is exactly the entry in the first row and first column of the matrix product $NR$. It's that simple! If we let $B$ be the matrix of absorption probabilities, where $B_{ik}$ is the probability of being absorbed in state $k$ starting from transient state $i$, then we have another wonderfully elegant result:

With our two master formulas, $N = (I-Q)^{-1}$ and $B=NR$, we can predict both the duration and the outcome of any process described by an absorbing Markov chain.

We know that any absorbing system is doomed to extinction—that is, it will eventually end up in an absorbing state. The only true long-term ​​stationary distribution​​ is one where the system is in an absorbing state with 100% probability. After a long time, that's all we'd see.

But this brings up a fascinating, almost philosophical question. If we look at a large population of these systems—say, a metapopulation of a species across many patches where global extinction is an absorbing state—and we filter out all the ones that have already gone extinct, what does the distribution of the survivors look like? Does the population structure among the non-extinct patches settle into a stable pattern, even as the total number of survivors is constantly dwindling?

The answer is yes. This stable pattern of the survivors is called a ​​quasi-stationary distribution (QSD)​​. It is like a ghost of a stationary distribution that haunts the transient states. If you were to start the system with its population distributed according to the QSD, then at any later time, the surviving population would still be described by that same QSD. It is conditionally stable.

While a true stationary distribution $\pi$ satisfies the equation $\pi P = \pi$, which means it's an eigenvector with eigenvalue 1, the QSD (let's call it $q$) is a left eigenvector of the transient submatrix $Q$ with an eigenvalue $\lambda$ that is strictly less than 1:

This eigenvalue $\lambda$ has a beautiful physical meaning: it is the probability that the system, when in its quasi-stationary state, will survive for one more time step. The probability of surviving for $t$ steps is then simply $\lambda^t$. The QSD gives us the shape of life before the end, and its associated eigenvalue tells us the precise, exponential rate of the march towards inevitability. It is a final, beautiful piece of structure found within the captivating world of absorbing chains.

In the last chapter, we took apart the engine. We laid out all the pieces: the states, the transition matrix, the fundamental matrix $N$, and the matrix of absorption probabilities $B$. We saw how the math works. Now, it's time to turn the key and take this beautiful machine for a drive. We're going to see that this isn't just an abstract mathematical game; it's a powerful lens for viewing the world. An absorbing Markov chain is, in a sense, a calculus of endings. It describes any process that is on a one-way trip to a final, irreversible destination. Once a system has absorbing states, its journey is fated to end. The only questions are where and when. And as we are about to see, these are precisely the questions our framework can answer, finding the same simple patterns at work in the most unexpected places—from the careers of scholars to the fate of entire economies, from the evolution of forests to the silent, invisible competition between the cells in your own body.

Let's start with something close to home for many of us: the long, winding road of graduate school. Is it possible to quantify the journey of a Ph.D. student? We can certainly try! Imagine the main stages: 'Coursework', 'Research', and 'Writing'. These are the transient states where a student spends their time. And the final outcomes? 'Defended' (graduation!) and 'Dropped Out'. These are our absorbing states. Once you've defended your thesis, you don't go back to coursework. The journey is over. We can gather data and estimate the probability of moving from one stage to another in a given year, forming our transition matrix $P$.

So what? The real power comes when we want to change the system. Suppose a university introduces a new policy—perhaps offering more funding to students in the 'Writing' phase to reduce precarity and improve focus. This policy would change the transition probabilities out of the 'Writing' state, hopefully decreasing the chance of dropping out and increasing the chance of defending. Our absorbing chain machinery allows us to calculate, with mathematical precision, exactly how this small change will ripple through the whole system and alter the final probability of a student graduating. We don't have to guess; we can compute the impact of the policy before it's even implemented. The fundamental matrix, $N = (I-Q)^{-1}$, which tells us the expected time spent in each transient stage, is the key that unlocks this predictive power.

This 'calculating the odds' is one half of the story. The other is 'how long will it take?' Consider the academic peer-review process, another journey familiar to scientists. A paper is 'Submitted', then goes 'Under Review', and may be sent back for 'Revision'. The final absorbing states are, of course, 'Accepted' or 'Rejected'. We can ask: what is the expected time until a paper is accepted? Here, our model gives us a surprising and profound answer. If there is any non-zero probability that the paper could end up in the 'Rejected' state, then the expected time to be absorbed into the 'Accepted' state is, mathematically, infinite!

Why? It sounds strange, but the logic is unassailable. To calculate the true average time, you must include the possibility of those paths that never reach 'Accepted'—the ones that are rejected. If a process never reaches a goal, its time to get there is infinite. An infinite time, averaged with any non-zero probability, gives an infinite result. This forces us to be more precise in our questions. We can't ask "What is the average time to acceptance?" We must ask "For those papers that are eventually accepted, what is their average time to acceptance?"—a much trickier question that, as we'll see, our framework can also handle.

The same mathematics that describes a student's career path also governs the grand processes of life and death, at scales from entire ecosystems to single cells.

Consider the life of a forest. Ecologists model how landscapes change over time, moving through stages like 'Early Successional' (open fields), 'Mid-Successional' (shrubs and young trees), and 'Late Successional' (mature forest). If we model this as a regular Markov chain, we can calculate the stationary distribution—the long-term equilibrium, telling us what fraction of the landscape will be in each state hundreds of years from now. But we can also ask a different kind of question. Suppose we want to know, "Starting from a clear-cut field, how many years will it take, on average, to become a mature forest?" To answer this, we perform a clever trick: we declare the 'Late Successional' state to be absorbing. The problem is instantly transformed into one we know how to solve. The expected time to absorption gives us our answer. This shows the beautiful flexibility of the Markov framework; the same model can answer questions about "what is the eternal balance?" and "how long until we get there?"

Now, let's zoom in—from a forest to a single, microscopic crypt in the lining of your intestine. These crypts contain a small pool of stem cells that constantly divide to replenish the tissue. For a long time, biologists debated whether there was a master "queen" stem cell at the top of a hierarchy. A simple absorbing chain model suggests a more elegant and democratic reality. Imagine a fixed number, $N$, of equipotent stem cells, meaning they are all equals. When a cell divides, it creates two daughters, and to keep the population at $N$, one of the existing cells in the crypt is randomly pushed out. If we label one cell and its descendants, what happens to this 'clone'? Its size, $k$, takes a random walk. It can grow to $k+1$ if a clone member divides and a non-clone member is pushed out, or shrink to $k-1$ in the reverse scenario. The states $k=0$ (the clone has vanished) and $k=N$ (the clone has taken over the entire crypt) are absorbing. This is the classic "Gambler's Ruin" problem in disguise! And we know its fate: the random walk cannot go on forever. It must end in one of the absorbing states. Over time, purely by chance, a single clone will take over the entire crypt. This phenomenon, called monoclonal conversion, is observed in reality. Our simple model explains it perfectly, without any need for a pre-programmed hierarchy—it's simply the inevitable outcome of neutral competition in a finite space.

This competition of fates plays out everywhere. During development, cells make irreversible choices. A progenitor cell might be faced with a decision to commit to an 'Epithelial' fate or a 'Mesenchymal' fate, passing through a 'Hybrid' transient state along the way. By modeling this as an absorbing chain, we can use the matrix $B = NR$ to compute the exact probability that a cell starting in the progenitor state will end up as mesenchymal. But what if the story is even more complicated, with life and death on the line? Consider the perilous journey of a marine invertebrate larva, which must pass through several developmental stages before it can settle and become a juvenile. At every stage, it risks dying. Here, we have two absorbing outcomes: 'Settled' and 'Death'. We might ask for the expected time it takes a larva to settle. But the "infinite time" paradox from the peer-review problem returns! If there's a chance of death, the unconditional expected time is infinite. A more biologically relevant question is: "Of the larvae that succeed in settling, what was their average journey time?" Our framework is subtle enough to answer this. We can construct a new, conditional Markov chain that only includes the successful paths, reweighting the transition probabilities based on the chance of reaching the 'Settled' state. By analyzing this new chain, we can find the mean time to settlement for the lucky winners.

The calculus of endings is the bread and butter of finance and economics, where it's used to quantify risk and understand history.

A corporation's credit rating is not static. Over time, a company rated 'AA' might be upgraded to 'AAA' or downgraded to 'A', 'BBB', and so on. The final, absorbing state in this journey is 'Default'. For banks, insurers, and investors, a crucial question is: "Given a company's current rating, what is its risk of default, and what is the expected time until that might happen?" This is a perfect job for an absorbing chain. By analyzing historical data on ratings changes, financial firms build massive transition matrices. The expected time to absorption, found by computing $\mathbf{t} = N\mathbf{1}$, gives them a direct estimate of the expected time to default for every rating class, a critical input for pricing loans and bonds.

Perhaps the most profound economic insight from this framework comes from simple models of path dependence. Imagine two identical "twin" countries, starting from the same economic position. Their joint system has two absorbing outcomes: both countries become wealthy ($HH$), or both fall into a poverty trap ($LL$). Because the countries benefit from trading with a wealthy partner, there are positive feedback loops. If one country, by chance, gets a slight edge, it makes it easier for the other to follow. A simple model can show that a tiny, random initial asymmetry—a temporary fluctuation that favors one country over the other—can be amplified by these feedback loops over time, sending the two identical countries to completely different destinies. This is path dependence: where you end up depends critically on the random steps you took along the way. The absorbing chain model doesn't just describe this; it quantifies it, showing how small historical accidents can have large and irreversible consequences.

The power of this framework extends far beyond these examples. The underlying principles can be generalized to situations that are vastly more complex. For instance, instead of discrete time steps (years, days, cell cycles), we can analyze systems that evolve in continuous time. We can also model systems with an astronomical number of states, such as the spread of an SIR (Susceptible-Infected-Recovered) epidemic across a social network. Each configuration of infected and recovered individuals in the network is a state, and the absorbing states are those where the epidemic has died out (no more 'Infected' individuals). While the state space is too large to write down by hand, the core logic remains the same: solve a system of linear equations to find the probability and expected size of the final outbreak.

From the quiet drift in a stem cell niche to the chaotic dynamics of an epidemic or the path of economic history, the mathematics of absorbing chains provides a unifying language. It's a tool that lets us peer into the future of any process that has an end, giving us not a crystal ball, but something far better: a rational way to calculate the odds and the timeline of the inevitable.