Linear Algebra: Markov Chains and Stochastic Matrices

Markov chains provide a powerful framework for modeling systems that transition randomly between states, from predicting weather patterns to ranking web pages. At their core, they transform complex probabilistic dynamics into a problem of linear algebra, where matrices become tools for forecasting long-term behavior. Mastering this connection equips you to analyze everything from game algorithms to population genetics with mathematical precision.

Probability Vectors and Stochastic Matrices

The foundation of any Markov model is the concept of state. A probability vector is a column vector whose entries are non-negative and sum to 1. Each entry $v_i$ represents the probability of being in state $i$. For example, if a weather model has states "Sunny" and "Rainy," the vector $v=\left[\begin{array}{c}0.7\\ 0.3\end{array}\right]$ means a 70% chance of sun and 30% chance of rain now.

The engine of change is the stochastic matrix (or transition matrix). This is a square matrix where every column is a probability vector. Each entry $P_{ij}$ represents the probability of moving to state $i$ from state $j$ in one step. Crucially, columns sum to 1. If our weather model states that a sunny day is followed by another sunny day 80% of the time and a rainy day 20% of the time, while a rainy day is followed by a sunny day 50% of the time and rain 50% of the time, the stochastic matrix is: $$P=\left[\begin{array}{cc}0.8& 0.5\\ 0.2& 0.5\end{array}\right].$$ Here, $P_{11}=0.8$ is the probability of going from Sunny (column 1) to Sunny (row 1).

State Transition Diagrams and Step-by-Step Evolution

A state transition diagram is a weighted graph that visually represents the Markov chain. Each state is a node, and directed edges show possible transitions, labeled with their probabilities. For our matrix $P$, the diagram has two nodes (Sunny, Rainy). An edge from Sunny to Sunny has weight 0.8, from Sunny to Rainy has weight 0.2, from Rainy to Sunny has weight 0.5, and from Rainy to Rainy has weight 0.5. This diagram makes the process intuitive and helps verify that outgoing probabilities from each node sum to 1.

To compute the probability distribution after one step, you use matrix multiplication. If the current state is given by probability vector $v$, then the distribution after one step is $Pv$. Starting with a sunny day, $v_0=\left[\begin{array}{c}1\\ 0\end{array}\right]$. The forecast for tomorrow is: $$v_1=P{v}_0=\left[\begin{array}{cc}0.8& 0.5\\ 0.2& 0.5\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}0.8\\ 0.2\end{array}\right].$$ For the day after tomorrow, you apply $P$ again: $v_2=P{v}_1=P^2{v}_0$. This reveals the core principle: the probability distribution after $n$ steps is given by $v_n=P^n{v}_0$. Computing long-term behavior via matrix powers becomes a central task, often done by diagonalization or finding the steady state directly.

Steady-State Distributions

For many Markov chains, as $n$ grows large, $P^n$ converges to a matrix where all columns are identical. This column is the steady-state distribution, often denoted $\mathbf{q}$. It represents the long-run probability of being in each state, independent of the starting point. Mathematically, $\mathbf{q}$ satisfies $P\mathbf{q}=\mathbf{q}$, making it an eigenvector of $P$ with eigenvalue 1. It is also a probability vector (entries sum to 1).

To find $\mathbf{q}=\left[\begin{array}{c}{q}_1\\ q_2\end{array}\right]$ for our weather model, solve $P\mathbf{q}=\mathbf{q}$: $$\left[\begin{array}{cc}0.8& 0.5\\ 0.2& 0.5\end{array}\right]\left[\begin{array}{c}{q}_1\\ q_2\end{array}\right]=\left[\begin{array}{c}{q}_1\\ q_2\end{array}\right].$$ This gives the system: $0.8q_1+0.5q_2=q_1$ and $0.2q_1+0.5q_2=q_2$. Both simplify to $0.2q_1=0.5q_2$, or $2q_1=5q_2$. Using the probability condition $q_1+q_2=1$, we substitute $q_2=(2/5)q_1$ to get $q_1+(2/5)q_1=1$, so $(7/5)q_1=1$. Thus, $q_1=5/7\approx 0.714$ and $q_2=2/7\approx 0.286$. In the long run, about 71.4% of days are sunny.

Absorbing Markov Chains and Their Analysis

An absorbing Markov chain has at least one absorbing state—a state that, once entered, cannot be left (its transition probability to itself is 1). Other states are called transient. A classic example is a simple gambling game where you go broke or reach a target wealth; both are absorbing states.

To analyze these, we rearrange the transition matrix into canonical form: $$P=\left[\begin{array}{cc}I& 0\\ R& Q\end{array}\right].$$ Here, $I$ is an identity matrix for the absorbing states, $Q$ governs transitions between transient states, and $R$ covers transitions from transient to absorbing states. The fundamental matrix $N=(I-Q{)}^{-1}$ is key. Its entry $N_{ij}$ gives the expected number of visits to transient state $j$ starting from transient state $i$ before absorption. Furthermore, $NR$ gives the probabilities of being absorbed in each absorbing state.

Applications to Web Ranking and Population Modeling

The power of Markov chains shines in diverse applications. Web ranking, as in the original PageRank algorithm, models a "random surfer" who clicks links at random. Each webpage is a state. The stochastic matrix $P$ has entries $P_{ij}$ representing the probability of moving from page $j$ to page $i$. A steady-state vector $\mathbf{q}$ then ranks pages by their long-run visitation probability, interpreted as importance. To handle pages with no outgoing links (absorbing states), the model adds a "teleportation" factor, ensuring a unique steady state.

In population modeling, Markov chains can track genetic traits, species migration, or disease states. For instance, a population might be divided into "Susceptible," "Infected," and "Recovered" compartments in a simplified SIR model. A stochastic matrix can model the weekly probabilities of individuals moving between these health states. Analyzing the steady state or absorption times (like time until an epidemic ends) provides critical insights for public health planning.

Common Pitfalls

1. Misinterpreting matrix entries: The most common error is confusing rows and columns. Remember: in a stochastic matrix $P$, the entry $P_{ij}$ is the probability of going to state $i$ (row) from state $j$ (column). Writing the matrix with rows as "from" and columns as "to" will invert all your calculations.

• Correction: Always define your matrix explicitly as $P=[p_{ij}]$ where $p_{ij}=P(\text{next state is }i\mid \text{current state is }j)$. Verify that each column sums to 1.

1. Assuming a unique steady state always exists: Not all Markov chains have a single, well-defined steady-state distribution. Chains that are periodic or have multiple disconnected communicating classes may not converge.

• Correction: Check if the chain is ergodic (irreducible and aperiodic). For an ergodic chain, a unique steady-state vector is guaranteed. For absorbing chains, look for the fundamental matrix and absorption probabilities instead.

1. Incorrectly solving for the steady state: When solving $P\mathbf{q}=\mathbf{q}$, it's tempting to treat it as a standard homogeneous system $(P-I)\mathbf{q}=0$. However, $P-I$ is always singular (since columns sum to zero), leading to infinite solutions.

• Correction: Use the equation $P\mathbf{q}=\mathbf{q}$ along with the normalization condition $q_1+q_2+...+q_n=1$. Replace one of the equations from $P\mathbf{q}=\mathbf{q}$ with this normalization condition to get a unique, invertible system.

1. Neglecting to check for absorption in applications: When modeling real-world systems like web graphs, failing to account for dangling nodes (pages with no links) can create absorbing states and break the model.

• Correction: As in PageRank, incorporate a damping factor or teleportation probability. This adds a chance to jump to any random page, making the adjusted transition matrix ergodic and ensuring a meaningful steady state.

Summary

• Markov chains model systems that transition randomly between states using probability vectors to describe current state distributions and stochastic matrices (columns sum to 1) to define transition probabilities.
• The state distribution after $n$ steps is computed by $v_n=P^n{v}_0$, and long-term behavior is analyzed by finding the steady-state distribution $\mathbf{q}$, an eigenvector of $P$ with eigenvalue 1.
• Absorbing Markov chains contain states that cannot be left; their analysis uses the canonical form and the fundamental matrix $N=(I-Q{)}^{-1}$ to calculate expected visits and absorption probabilities.
• These tools are applied in foundational algorithms like web ranking (PageRank), where the steady-state vector determines page importance, and in population modeling for genetics, ecology, and epidemiology.
• Success requires careful attention to the definition of the transition matrix, conditions for steady-state existence, and practical adjustments (like teleportation) to ensure models are robust and analytically tractable.