Markov Chains & Steady States — Markov Chains and Steady...

SECTION 1

Historical Context & Motivation

Imagine you want to predict the weather tomorrow. You know that if today is sunny, there's a 70% chance tomorrow will also be sunny and a 30% chance it will rain. If today is rainy, there's a 40% chance tomorrow will be sunny and a 60% chance of more rain. This kind of thinking — predicting the future based only on the present — is exactly what a Markov chain captures. For over a century, mathematicians have used Markov chains to model everything from board games to internet search engines.

1906

Andrey Markov's Breakthrough

Russian mathematician Andrey Markov introduced chains of linked random events, showing that probability could model sequences where each step depends only on the current state.

1913

Text Analysis with Markov Chains

Markov applied his chains to the letters in Alexander Pushkin's poem Eugene Onegin, analyzing how vowels and consonants follow each other — one of the first uses of math in language processing.

1950s

Markov Chains Meet Computers

With the rise of early computers, scientists began using Markov chains for simulations in physics, biology, and economics. The technique scaled rapidly with computing power.

1998

Google's PageRank Algorithm

Larry Page and Sergey Brin used a giant Markov chain to rank web pages. The steady state of their model determined which pages were most important — the foundation of Google Search.

The central question that Markov chains answer is this: if a system keeps changing randomly according to fixed rules, where does it end up in the long run? That long-run destination is called the steady state, and finding it is one of the most powerful applications of linear algebra.

SECTION 2

Core Principles & Definitions

Before diving into calculations, let's nail down the key vocabulary. A Markov chain is built from just a few simple ideas. Once you understand these building blocks, the rest of the topic clicks into place.

State

A state is a situation or condition the system can be in. For weather, the states might be "Sunny" and "Rainy." For a board game, each square is a state.

Transition Probability

A transition probability is the chance of moving from one state to another in a single step. These probabilities are always between 0 and 1, and from any state they must add up to 1.

Transition Matrix

A transition matrix organizes all the transition probabilities into a grid (matrix). Each column adds up to 1. This matrix is the engine that drives the chain.

Memoryless Property

The memoryless property means the next state depends only on the current state, not on how you got there. The system has no memory of its past.

Steady State

The steady state (or equilibrium) is a probability distribution that doesn't change when you apply the transition matrix. Once the system reaches it, the proportions stay the same forever.

✦ KEY TAKEAWAY

Think of a Markov chain like shuffling between rooms in a house. Each room is a state. The doors between rooms have fixed probabilities — maybe there's a 60% chance you walk through the kitchen door and a 40% chance you head to the living room. After wandering long enough, you'll spend a predictable fraction of your time in each room. That fraction is the steady state.

SECTION 3

Visual Explanation — State Diagrams

The best way to see a Markov chain is with a state diagram. Each state is drawn as a circle, and arrows between circles show the transition probabilities. An arrow that loops back to the same circle means the system can stay in that state. Let's look at our weather example with two states: Sunny and Rainy.

The state diagram shows two states — Sunny (left, gold border) and Rainy (right, blue border). The pink arrow (0.3) shows the chance of going from Sunny to Rainy. The cyan arrow (0.4) shows Rainy to Sunny. Self-loops represent staying in the same state. Notice that the arrows leaving each state always add to 1.

In the diagram above, every arrow carries a number between 0 and 1. The key rule is that all arrows leaving any single state must add up to exactly 1. This makes sense — from any state, something has to happen, so the probabilities must account for every possibility.

SECTION 4

Mathematical Framework

Now let's translate the state diagram into math. We organize the transition probabilities into a transition matrix. Each column of the matrix corresponds to a starting state, and each row corresponds to a destination state. The entries are the probabilities of moving from the column state to the row state.

TRANSITION MATRIX

P = [ 0.7 0.4 ] [ 0.3 0.6 ]

Column 1 = from Sunny. Column 2 = from Rainy. Row 1 = to Sunny. Row 2 = to Rainy. Each column sums to 1.

We also need a state vector to describe where the system is right now. If today is definitely sunny, the state vector is:

INITIAL STATE VECTOR

x₀ = [ 1 ] [ 0 ]

The top entry is the probability of Sunny (100%), and the bottom is the probability of Rainy (0%). The entries always add to 1.

To find the probabilities for tomorrow, we multiply the transition matrix by the current state vector. To find the day after that, we multiply again. In general, after n steps:

STATE AFTER n STEPS

xₙ = P × xₙ₋₁ = Pⁿ × x₀

xₙ is the state vector after n steps. P is the transition matrix. Pⁿ means multiplying P by itself n times.

The steady-state vector q is the special vector that doesn't change when you multiply by P. Mathematically:

STEADY-STATE CONDITION

P × q = q

This equation says: applying the transition matrix to the steady-state vector gives back the same vector. This is actually an eigenvector equation with eigenvalue 1.

SECTION 5

How the System Reaches Steady State

One of the most fascinating things about Markov chains is that no matter where you start, the system often settles into the same steady state. Let's watch the weather chain converge. Starting from 100% Sunny, we multiply by P over and over and track how the state vector changes.

This graph shows how the probabilities of Sunny (gold) and Rainy (blue) change step by step. Even though we started at 100% Sunny, the system quickly approaches the steady state at roughly 57.1% Sunny and 42.9% Rainy (shown by dashed lines). After about 5−6 steps, the values barely change.

Notice how quickly the system converges. After just a few steps, the probability of Sunny has settled near 4/7 ≈ 0.571 and Rainy near 3/7 ≈ 0.429. Even if we had started from 100% Rainy instead, we would reach the exact same steady state. This is the magic of Markov chains — the starting point doesn't matter in the long run, as long as the chain is well-behaved (meaning every state can eventually reach every other state).

💡 Why Does It Converge?

Mathematically, the convergence happens because the transition matrix P has a largest eigenvalue of exactly 1, and all other eigenvalues have absolute value less than 1. When we raise P to higher powers (Pⁿ), the contributions from smaller eigenvalues shrink to zero, leaving only the steady-state component. You'll explore eigenvalues more deeply in later lessons!

SECTION 6

Worked Example — Finding the Steady State

Let's find the exact steady-state vector for our weather Markov chain. We need to solve the equation Pq = q, where q is the steady-state vector and the entries of q add to 1.

Finding the Steady State of the Weather Chain

Step 1 — Write the Steady-State EquationWe want Pq = q. Let q = [q₁, q₂]ᵀ where q₁ = P(Sunny) and q₂ = P(Rainy). This gives us two equations from the matrix multiplication: 0.7q₁ + 0.4q₂ = q₁ and 0.3q₁ + 0.6q₂ = q₂.

Step 2 — Rearrange the First EquationTake 0.7q₁ + 0.4q₂ = q₁ and subtract q₁ from both sides: −0.3q₁ + 0.4q₂ = 0. This simplifies to 0.4q₂ = 0.3q₁, or equivalently q₁ = (4/3)q₂.

q₁ = (4/3) × q₂

Step 3 — Use the Constraint q₁ + q₂ = 1Since q₁ and q₂ are probabilities, they must add to 1. Substituting q₁ = (4/3)q₂: (4/3)q₂ + q₂ = 1. This gives (7/3)q₂ = 1, so q₂ = 3/7.

q₂ = 3/7 ≈ 0.4286

Step 4 — Find q₁Since q₁ + q₂ = 1 and q₂ = 3/7, we get q₁ = 1 − 3/7 = 4/7.

q₁ = 4/7 ≈ 0.5714

Step 5 — State the Steady-State VectorThe steady-state vector is q = [4/7, 3/7]ᵀ. In the long run, it will be sunny about 57.1% of the time and rainy about 42.9% of the time. You can verify: 0.7(4/7) + 0.4(3/7) = 4/10 + 12/70 = 4/7 ✓.

q = [4/7, 3/7]ᵀ ≈ [0.571, 0.429]ᵀ

🔑 WHY THIS WORKS

Solving Pq = q is the same as solving (P − I)q = 0, where I is the identity matrix. This means q is in the null space of (P − I). In eigenvalue language, q is an eigenvector of P with eigenvalue 1. Every transition matrix has eigenvalue 1, so every Markov chain has a steady-state vector!

SECTION 7

Strengths, Limitations & Comparisons

Markov chains are powerful, but they're not always the right tool. Let's compare their strengths and limitations so you know when to use them and when to look for other approaches.

Strengths and limitations of Markov chains

Feature	Strength	Limitation
Simplicity	Easy to set up — just list states and probabilities. The math uses basic matrix multiplication.	Oversimplifies complex systems that have many interacting parts or continuous change.
Memory	The memoryless property makes computation fast — you only need the current state.	Many real systems DO depend on history. Weather depends on the past week, not just today.
Steady State	Predicts long-term behavior without simulating every single step.	Not all chains have a unique steady state — some cycle or have absorbing states.
Scalability	Works for millions of states (e.g., Google's web pages).	Larger matrices require more computational resources to solve.

⚡ WHEN TO USE MARKOV CHAINS

Markov chains shine when the future genuinely depends only on the present. Think of a board game: where you land next depends on your current square and a dice roll — not on your entire game history. If history matters a lot (like predicting stock prices based on trends), you may need more advanced tools like higher-order Markov chains or hidden Markov models.

SECTION 8

Connection to Eigenvalues & Eigenvectors

You might have noticed something interesting in our work. The steady-state equation Pq = q looks a lot like the general eigenvector equation Av = λv, with λ = 1. That's no coincidence — finding the steady state of a Markov chain is a specific case of finding eigenvectors. This table shows how the Markov chain concepts connect to broader linear algebra ideas.

Markov chains as a gateway to eigenvalue theory

Markov Chain Concept	Linear Algebra Concept	Why It Matters
Transition matrix P	Square matrix A	P is a special matrix whose columns sum to 1 (called a stochastic matrix).
Steady-state vector q	Eigenvector for λ = 1	The steady state is the eigenvector of P corresponding to eigenvalue 1, scaled so its entries sum to 1.
Convergence to steady state	Dominant eigenvalue	λ = 1 is the largest eigenvalue. Other eigenvalues are smaller, so their effects fade as n → ∞.
Solving (P − I)q = 0	Null space of (A − λI)	Standard technique for finding any eigenvector — subtract λI from the matrix and find the null space.

As you continue in linear algebra, you'll see eigenvalues and eigenvectors everywhere — in vibrating systems, population models, and data science (principal component analysis). Markov chains are one of the most intuitive entry points into this powerful framework, because the steady state has a concrete, real-world meaning that makes the abstract algebra feel tangible.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

A Markov chain has three states: A, B, and C. The transition probabilities from state A are: 0.5 to A, 0.3 to B, and 0.2 to C. What must the transition probabilities from state B add up to? Explain why.

PROBLEM 2 — BASIC CALCULATION

A two-state Markov chain has transition matrix P = [[0.8, 0.5], [0.2, 0.5]]. If the system starts in state 1 (x₀ = [1, 0]ᵀ), find the state vector after one step.

PROBLEM 3 — INTERMEDIATE

Using the same matrix P = [[0.8, 0.5], [0.2, 0.5]], find the steady-state vector q by solving Pq = q with q₁ + q₂ = 1.

PROBLEM 4 — APPLIED

A music app has two modes: Pop and Jazz. Users listening to Pop have a 0.6 chance of staying on Pop and 0.4 chance of switching to Jazz. Users on Jazz have a 0.3 chance of switching to Pop and 0.7 chance of staying on Jazz. In the long run, what fraction of listening time is spent on each genre? If the app has 10,000 users, how many are expected to be listening to Jazz at steady state?

PROBLEM 5 — CRITICAL THINKING

Consider a Markov chain with transition matrix P = [[0, 1], [1, 0]]. Try to find the steady-state vector. What happens when you repeatedly multiply P by a starting vector like [1, 0]ᵀ? Does this chain converge to a steady state? Explain what's different about this matrix compared to the weather example.

SUMMARY

Lesson Summary

A Markov chain models a system that moves between states with fixed transition probabilities, where the next state depends only on the current one (the memoryless property). These probabilities are organized in a transition matrix P, where each column sums to 1. The state vector tracks the current probability distribution, and multiplying by P advances the system one step: xₙ = P × xₙ₋₁.

The steady-state vector q satisfies Pq = q — it is the eigenvector of P with eigenvalue 1, scaled so its entries sum to 1. To find it, solve the system (P − I)q = 0 with the constraint that entries sum to 1. For well-behaved (irreducible, aperiodic) chains, the system always converges to the steady state regardless of the starting vector — a powerful result that connects probability, matrix algebra, and eigenvalue theory.