Markov Chains

Discrete-state processes where the future depends only on the present, governed by a transition matrix.

1. The idea

A Markov chain moves between a finite set of states such that $P (X_{n + 1} = j ∣ X_{n} = i, X_{n - 1}, \dots) = P (X_{n + 1} = j ∣ X_{n} = i) = P_{ij}$ : the next state depends only on the current one, not the full history.

Collecting these one-step probabilities into a transition matrix $P$ lets you compute $n$ -step transitions as $P^{n}$ , and lets you find long-run behavior without simulating.

A stationary distribution $π$ satisfies $π P = π$ with $\sum_{i} π_{i} = 1$ ; for an irreducible, aperiodic chain, the chain converges to $π$ regardless of the starting state.

2. Why it matters

Markov chains model state transitions in order books, credit ratings, and game states, and "find the stationary distribution" or "find the long-run fraction of time in state X" is a standard interview question type.

3. Core mathematics

Markov property

P (X_{n + 1} = j ∣ X_{n} = i, F_{n}) = P_{ij}

Transition matrix

P = (P_{ij}), j \sum P_{ij} = 1 \forall i

$n$ -step transitions

P (X_{n} = j ∣ X_{0} = i) = (P^{n})_{ij}

Stationary distribution

π P = π, i \sum π_{i} = 1, π_{i} \geq 0

Long-run behavior

n \to \infty lim P_{ij}^{n} = π_{j}

for irreducible, aperiodic chains

4. How to recognize it

Think of this when…

A system with a discrete set of states and given transition probabilities between them
"Find the long-run proportion of time in state $X$ " — asks for the stationary distribution
Weather, credit rating, or game-state transition setups with the Markov (memoryless-in-state) property
Requests to solve $π P = π$ or to find the $n$ -step transition probability

5. Worked example

Worked example

A two-state chain (Sunny $S$ , Rainy $R$ ) has $P (S \to S) = 0.9$ , $P (S \to R) = 0.1$ , $P (R \to S) = 0.5$ , $P (R \to R) = 0.5$ . Find the stationary distribution.

1
Let $π = (π_{S}, π_{R})$ with $π_{S} + π_{R} = 1$ . Write $π P = π$ componentwise.
$π_{S} = 0.9 π_{S} + 0.5 π_{R}$
2
Rearrange the equation.
$0.1 π_{S} = 0.5 π_{R} \Rightarrow π_{S} = 5 π_{R}$
3
Use the normalization constraint.
$5 π_{R} + π_{R} = 1 \Rightarrow π_{R} = \frac{1}{6}, π_{S} = \frac{5}{6}$
Answer: $π = (π_{S}, π_{R}) = (5/6, 1/6)$ : sunny days occur $5/6$ of the time in the long run.

6. Common mistakes

Writing $P π = π$ instead of $π P = π$ (row vector on the left, since $π$ acts on the left of $P$ )
Forgetting the normalization constraint $\sum_{i} π_{i} = 1$ , leaving an underdetermined system
Assuming a stationary distribution exists and is unique without checking irreducibility
Confusing the transition matrix's rows (from-state) with its columns (to-state)

7. Quick check

What two conditions define a stationary distribution $π$ of transition matrix $P$ ?

In a 2-state chain with $P (S \to R) = 0.4$ and $P (R \to S) = 0.2$ , what is $π_{S}$ ?

8. Practice

2 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Recursive Expectation / First-Step Analysis Conditioning on the First Event

Create a free account to save lesson progress.