Unit 5.1
Markov-Chain Simulation
Specification, multi-step and limiting behaviour, and simulation of state trajectories.
- Unit 5.1
- Unit 5.2
§ Overview
A Markov chain is a stochastic process in which the next state depends only on the current state, not on the path taken to reach it. This memoryless property is restrictive but widely applicable: it underlies models of disease progression, credit-rating migrations, brand-switching behaviour, population dynamics, and many others.
The unit begins with the specification of a Markov chain: its states and its transition probabilities. It develops the multi-step and steady-state behaviour, then closes with the simulation of stochastic state transitions and the comparison of empirical results against theoretical predictions.
Lesson 1
States and transition probabilities
Lesson 2
Multi-step and steady-state behaviour
Lesson 3
Simulation of stochastic state transitions
Laboratory 9
Markov-chain models
§ Learning outcomes
By the end of Unit 5.1 you will be able to
- Specify a Markov chain by its states and transition probabilities.
- Compute multi-step transition probabilities from the transition matrix.
- Compute the steady-state distribution and interpret it.
- Simulate a Markov chain using inverse transform for the state transitions.
- Compare simulated state frequencies against the theoretical distribution.
- Recognise when the Markov assumption is violated in a model.
§ Lessons
States and transition probabilities
Specify a Markov chain and read its one-step behaviour. The Markov property and the transition matrix.
Lesson 2Multi-step and steady-state behaviour
The Chapman–Kolmogorov equations, n-step probabilities, and limiting distributions.
Lesson 3Simulation of stochastic state transitions
Simulate paths with inverse transform and compare empirical behaviour against theory.
§ The transition matrix
A Markov chain with n states is specified by its
transition matrix P, an
n × n matrix whose entry P_ij is the
probability of moving from state i to state j
in one step. The rows of P sum to 1:
Σ_j P_ij = 1 for all i
The distribution over states at time t is a row vector
π^(t). The one-step update is
π^(t+1) = π^(t) P
and the k-step distribution is
π^(t+k) = π^(t) P^kRow-vector convention
The convention in this course is that distributions are row vectors and are multiplied on the right by the transition matrix. Some textbooks use column vectors and multiply on the left. The two conventions are equivalent; what matters is that you are consistent.
§ Steady state
Under suitable conditions, a Markov chain converges to a
stationary distribution π* that satisfies
π* P = π*
The stationary distribution is a left eigenvector of P
with eigenvalue 1, normalised to sum to 1. It describes the long-run
proportion of time the chain spends in each state.
For an irreducible and aperiodic chain, the stationary distribution is
unique, and the k-step distribution converges to it
regardless of the initial state. For periodic chains, the distribution
does not converge, but the long-run proportions still satisfy the
stationarity equation.
Steady state is not short-run behaviour
The stationary distribution describes behaviour in the infinite-time limit. Over a finite horizon — even a long one — the distribution may differ substantially. Decisions that depend on short-run behaviour must be based on the transient distribution, not the stationary one.
§ Key terms
- Markov property
-
The condition that the next state depends only on the current state,
not on the sequence of previous states. Formally,
P(X_{t+1} | X_t, X_{t−1}, …) = P(X_{t+1} | X_t). - State space
- The set of all possible states the chain can occupy. Usually finite in applications.
- Transition matrix
-
The matrix
Pwith entriesP_ij = P(X_{t+1} = j | X_t = i). Rows sum to 1. - Stationary distribution
-
A distribution
π*satisfyingπ* P = π*. Describes the long-run behaviour of the chain. - Irreducible
- A chain is irreducible if every state can be reached from every other state, possibly in multiple steps. Necessary for the stationary distribution to be unique.
- Aperiodic
- A chain is aperiodic if the return times to any state are not constrained to multiples of some period greater than 1. Necessary for convergence to the stationary distribution.
§ Self-check
Check your understanding
Question 1
The Markov property states that:
Show answer
The next state depends only on the current state. Past states provide no additional information.
Question 2
The rows of a transition matrix sum to:
Show answer
1. The probabilities of moving from a given state to each possible next state must sum to 1.
Question 3
The stationary distribution π* satisfies:
Show answer
π* P = π*. Under the row-vector convention used in this course.
Question 4
A Markov chain is irreducible if:
Show answer
Every state can be reached from every other state.
Question 5
The stationary distribution describes:
Show answer
The long-run proportion of time spent in each state.