01 / 21

Markov Chains
& Steady States

Discover how systems evolve over time using transition matrices, and learn to find the long-run equilibrium where change stops.

Linear Algebra

What Is a Markov Chain?

A Markov chain is a mathematical model that describes a system hopping between states according to fixed probabilities. The key idea: where you go next depends only on where you are now, not on the full history of how you got there.

States
The possible conditions the system can be in (e.g., Sunny, Rainy).
Transitions
The probabilities of moving from one state to another at each step.

A Simple Weather Model

Imagine tomorrow's weather depends only on today. If it's sunny today, there's a 70% chance of sun tomorrow and a 30% chance of rain. If it's rainy, there's a 40% chance of sun and a 60% chance of more rain.

Sunny Rainy 0.7 0.6 0.3 0.4

The Transition Matrix \(P\)

We encode all transition probabilities in a single matrix \(P\). Each row represents the current state, and each column represents the next state. Every row sums to 1.

Stochastic Matrix
A matrix where every entry is \(\geq 0\) and every row sums to 1 is called a stochastic matrix.
State Vector
A row vector \(\mathbf{x} = (x_1, x_2, \ldots)\) giving the probability of being in each state.

Evolving the System with \(\mathbf{x} P\)

If \(\mathbf{x}_0\) is your initial state vector, then after one step the new distribution is \(\mathbf{x}_1 = \mathbf{x}_0 P\). After \(n\) steps: \(\mathbf{x}_n = \mathbf{x}_0 P^n\).

What Is a Steady State?

As \(n \to \infty\), many Markov chains converge to a fixed distribution \(\mathbf{q}\) that no longer changes. This is the steady-state (or stationary distribution).

Steps (n) P(Sunny) 0 0.5 1.0 0 2 4 6 8 10 4/7 Start Sunny Start Rainy

The Steady-State Equation

The steady-state vector \(\mathbf{q}\) satisfies a beautifully simple condition: multiplying by \(P\) doesn't change it.

This means \(\mathbf{q}\) is a left eigenvector of \(P\) with eigenvalue \(\lambda = 1\). Every stochastic matrix has at least one such eigenvector.

Regular vs Absorbing Chains

Not every Markov chain has a unique steady state. The type of chain determines the long-run behavior.

Regular Chain Absorbing Chain
Definition Some power \(P^k\) has all positive entries Has at least one absorbing state (self-loop = 1)
Steady state Unique, independent of start Depends on starting state
Long-run Converges to \(\mathbf{q}\) Eventually absorbed
Example Weather model Gambler's ruin

How to Find the Steady State

1
Write the equation \(\mathbf{q} P = \mathbf{q}\), which expands to a system of linear equations.
2
Rearrange to \(\mathbf{q}(P - I) = \mathbf{0}\). This is a homogeneous system.
3
Replace one equation with the constraint \(q_1 + q_2 + \cdots + q_n = 1\) (since the rows of \(P - I\) are linearly dependent).
4
Solve the resulting system using substitution or row reduction.

Worked Example: Weather Model

Find the steady state for \(P = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}\).

Example 2: Three-State Chain

A student's daily mood cycles between Happy, Neutral, and Stressed with transition matrix:

Happy Neutral Stressed 0.5 0.5 0.5 0.3 0.2 0.2 0.3 0.3 0.2

Solving the Three-State System

Example 3: Asymmetric Chain

Consider \(P = \begin{pmatrix} 0.6 & 0.4 \\ 0.8 & 0.2 \end{pmatrix}\). State 2 has a strong pull toward State 1.

Why Does \(P^n\) Converge?

For a regular Markov chain, the Perron-Frobenius theorem guarantees convergence. The eigenvalue \(\lambda = 1\) is the largest, and all other eigenvalues satisfy \(|\lambda_i| < 1\).

1
\(P\) is stochastic, so \(\lambda = 1\) is always an eigenvalue.
2
For a regular chain, all other \(|\lambda_i| < 1\), so those components decay as \(n\) grows.
3
What remains is the projection onto the \(\lambda = 1\) eigenspace: the steady state \(\mathbf{q}\).

Common Mistakes to Avoid

✕ Rows vs Columns
Some textbooks use column-stochastic matrices (columns sum to 1). Always check which convention your book uses. Our convention: rows sum to 1.
✕ Forgetting the Constraint
The system \(\mathbf{q}(P - I) = \mathbf{0}\) has infinitely many solutions. You must include \(q_1 + q_2 + \cdots + q_n = 1\) to get a unique answer.
✕ Assuming All Chains Converge
Periodic or reducible chains may not have a unique steady state. Convergence requires the chain to be regular (some \(P^k\) has all positive entries).

Key Concepts at a Glance

Concept Definition Key Property
Transition Matrix \(P\) Encodes all state-to-state probabilities Rows sum to 1
State Vector \(\mathbf{x}\) Probability distribution over states Entries sum to 1, all \(\geq 0\)
Steady State \(\mathbf{q}\) Long-run equilibrium distribution \(\mathbf{q} P = \mathbf{q}\)
Regular Chain Some \(P^k\) has all positive entries Unique \(\mathbf{q}\), always converges
Eigenvalue \(\lambda = 1\) Largest eigenvalue of any stochastic \(P\) Steady state is its eigenvector

Question 1 of 5

In a Markov chain, the Markov property states that:

Question 2 of 5

For a stochastic (transition) matrix, which property must hold?

Question 3 of 5

Given \(P = \begin{pmatrix} 0.5 & 0.5 \\ 0.3 & 0.7 \end{pmatrix}\), what is the steady-state vector \(\mathbf{q}\)?

Question 4 of 5

If \(\mathbf{x}_0 = (1, 0)\) and \(P = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}\), what is \(\mathbf{x}_2\)?

Question 5 of 5

A Markov chain has the transition matrix \(P = \begin{pmatrix} 1 & 0 \\ 0.5 & 0.5 \end{pmatrix}\). Which statement is true?