Markov Chains

Overview

Markov chains model systems that evolve randomly over time, where the future depends only on the present state — not the past. This topic covers the formal definition, transition matrices, state classification, stationary distributions, and first step analysis — the main computational tool for hitting times and absorption probabilities. Markov chains appear directly in quant interviews through random walk problems, gambler's ruin, and expected hitting time questions.

1. Definition & Basic Properties

1.1 Markov Property

Definition

A sequence of random variables $(X_n)_{n \geq 0}$ taking values in a countable state space $\mathcal{S}$ is a Markov chain if it satisfies the Markov property: for all $n \geq 0$ and all states $i_0, \ldots, i_{n-1}, i, j \in \mathcal{S}$ :

\boxed{P(X_{n+1} = j \mid X_n = i,\, X_{n-1} = i_{n-1}, \ldots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i)}

The future is conditionally independent of the past given the present.

Remarque

The Markov property says the current state $X_n$ is a sufficient statistic for predicting the future. All relevant history is encoded in the current state — this is what makes Markov chains tractable.

1.2 Homogeneous Markov Chain

Definition

A Markov chain is time-homogeneous if the transition probabilities do not depend on $n$ :

\boxed{P(X_{n+1} = j \mid X_n = i) = P_{ij} \quad \text{for all } n \geq 0}

Properties

$P_{ij} \geq 0$ for all $i, j \in \mathcal{S}$
$\displaystyle\sum_{j \in \mathcal{S}} P_{ij} = 1$ for all (rows sum to 1)

2. Transition Matrix

2.1 Definition & Properties

Definition

The transition matrix $P$ is the $|\mathcal{S}| \times |\mathcal{S}|$ matrix with entries $P_{ij} = P(X_1 = j \mid X_0 = i)$ :

Properties

Each row sums to 1: $P\,\mathbf{1} = \mathbf{1}$ $\quad$ ( $P$ is a stochastic matrix)
All entries non-negative: $P_{ij} \geq 0$

2.2 Chapman-Kolmogorov Equation

Theorem— Chapman-Kolmogorov

The $n$ -step transition probability $P_{ij}^{(n)} = P(X_n = j \mid X_0 = i)$ satisfies:

Remarque

Chapman-Kolmogorov is the key computational tool: to find the probability of being in state $j$ after $n$ steps starting from $i$ , simply compute $(P^n)_{ij}$ . This is efficient via matrix diagonalization when has distinct eigenvalues.

2.3 Path Probabilities

Formula

The probability of following a specific path $i_0 \to i_1 \to \cdots \to i_n$ is:

Example

For a 3-state chain starting in state 1, the probability of the path $1 \to 2 \to 3 \to 1$ is $P_{12}\cdot P_{23}\cdot P_{31}$ .

3. Classification of States

3.1 Definitions & Terminology

Definition

State $j$ is accessible from $i$ (written $i \to j$ ) if $P_{ij}^{(n)} > 0$ for some

Definition— Recurrence & Transience

Let $T_i = \min\{n \geq 1 : X_n = i\}$ be the to state . Then:

Properties

Recurrence and transience are class properties: if $i \leftrightarrow j$ , then $i$ and $j$ have the same type
A finite irreducible chain is always recurrent
For a recurrent state $i$ : $\sum_{n=0}^\infty P_{ii}^{(n)} = \infty$

Remarque

In finite state spaces, all recurrent states are positive recurrent — null recurrence only arises in infinite chains (e.g. symmetric random walk on $\mathbb{Z}$ ).

3.2 Absorbing Chains

Definition

A state $i$ is absorbing if $P_{ii} = 1$ (once entered, never left). A chain is an absorbing Markov chain if it has at least one absorbing state and from every non-absorbing state it is possible to reach an absorbing state.

Remarque

For an absorbing chain, partition the states into transient states $T$ and absorbing states $A$ . The transition matrix takes the canonical form:

$P = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}$

Formula— Fundamental Matrix

\boxed{N = (I - Q)^{-1}}

$N_{ij}$ is the the chain visits transient state before absorption, starting from transient state .

4. Stationary Distribution & Long-Run Behavior

4.1 Stationary Distribution

Definition

A probability distribution $\pi = (\pi_i)_{i \in \mathcal{S}}$ is a stationary distribution (invariant measure) if:

π P = π, \underset{}{}

Properties

A finite irreducible chain has a unique stationary distribution
$\pi_i > 0$ for all $i$ in an irreducible chain
Expected return time: $\pi_i = \dfrac{1}{E[T_i \mid X_0 = i]}$

💡Tip

To find $\pi$ : solve the linear system $\pi P = \pi$ with $\sum_i \pi_i = 1$ . For a 2-state chain with , the solution is , .

4.2 Detailed Balance (Reversibility)

Definition

A Markov chain with stationary distribution $\pi$ satisfies detailed balance if:

\boxed{\pi_i P_{ij} = \pi_j P_{ji} \quad \text{for all } i, j \in \mathcal{S}}

Theorem

If a distribution $\pi$ satisfies detailed balance with respect to $P$ , then $\pi$ is a stationary distribution of the chain.

💡Tip

Detailed balance is easier to verify than $\pi P = \pi$ directly — it is a pairwise condition. It is the foundation of MCMC algorithms (Metropolis-Hastings): the proposal is designed so that detailed balance holds, guaranteeing $\pi$ is the stationary distribution.

4.3 Ergodic Theorem & Convergence

Theorem— Ergodic Theorem

For an irreducible, positive recurrent chain with stationary distribution $\pi$ , for any bounded function $f$ :

\boxed{\frac{1}{n}\sum_{k=0}^{n-1} f(X_k) \xrightarrow{\text{p.s.}} \sum_{i \in \mathcal{S}} f(i)\,\pi_i = E_\pi[f]}

Theorem— Convergence to Stationarity

For an ergodic (irreducible + aperiodic) chain with stationary distribution $\pi$ :

\boxed{\lim_{n \to \infty} P_{ij}^{(n)} = \pi_j \quad \text{for all } i, j \in \mathcal{S}}

Remarque

Aperiodicity is essential for convergence to stationarity. A periodic chain (e.g. period 2) oscillates and $P^n$ does not converge — it alternates between two limits. Adding a self-loop $P_{ii} > 0$ breaks periodicity.

5. First Step Analysis

5.1 Principle

Definition

First step analysis (analyse de premier pas) sets up recursive equations by conditioning on the first transition $X_1$ . For any quantity $v(i)$ depending on the starting state $i$ :

v (i) = \sum_{j \in S} P_{}

5.2 Absorption Probabilities

Theorem

Let $A \subseteq \mathcal{S}$ be a set of absorbing states and $h_i = P(\text{absorbed in } A \mid X_0 = i)$ . Then is the minimal non-negative solution to:

Example

Gambler's Ruin: player has $k$ dollars, bets 1 dollar at each step, wins with probability $p$ , loses with probability $q=1-p$ . States $0$ and $N$ are absorbing. Let . First step analysis gives with , :

5.3 Expected Hitting Times

Theorem

Let $A \subseteq \mathcal{S}$ and $m_i = E[T_A \mid X_0 = i]$ where . Then is the minimal non-negative solution to:

Example

Expected return time: for an irreducible chain, the expected return time to state $i$ starting from $i$ is $m_i = E[T_i \mid X_0=i] = 1/\pi_i$ .

💡Tip

First step analysis always produces a linear system — never try to sum an infinite series directly. The pattern is always: boundary conditions first, then write the recursive equation for interior states, then solve the system. For 2–3 state problems, the system is $2\times2$ or $3\times3$ and solvable by hand in an interview.

6. Quick Reference

State Classification

Property	Definition	Key implication
Accessible: $i \to j$	$\exists n: P_{ij}^{(n)}>0$	Reachability
Communicating:

Key Formulas

Concept	Formula
Markov property	$P(X_{n+1}=j\\|X_n=i, \ldots) = P_{ij}$