Markov chains are fundamental mathematical models for systems that evolve randomly over time, where the future depends only on the present state, not on the history. This memoryless property — called the Markov property — makes them remarkably tractable while still capturing the essential randomness in many real-world phenomena: weather patterns, stock prices, population dynamics, and queuing systems all admit Markov chain descriptions. The course develops both the theory underlying these models and the techniques for analysing their long-run behaviour.

The course unfolds in natural stages. After motivating the Markov property and its consequences, we introduce the formal structure of Markov chains as sequences of states connected by transition probabilities, then classify chains and individual states by their connectivity and recurrence properties. These structural insights lead directly to questions about convergence: do chains settle into stable distributions, do they return to certain states infinitely often, and how long does transient behaviour persist? The final chapter on time reversal reveals a beautiful duality — that many chains look statistically identical when run backward — with applications to sampling algorithms and detailed balance in physical systems.

# Introduction

[motivation] Probability theory, as studied in a first course, is largely a theory of independence. We toss a coin repeatedly, roll dice in sequence, draw from an urn with replacement — in each case, the outcome of one trial tells us nothing about the next. This independence assumption is mathematically convenient and allows us to prove powerful results: the law of large numbers, the central limit theorem, and so on. But it is also, frankly, an idealization. In the real world, consecutive observations are almost never independent. The weather tomorrow is not independent of the weather today. The queue length at a service counter at 3pm is not independent of the queue length at 2pm. The price of a stock next week is not independent of its price this week. If we wish to model such phenomena mathematically, we need a theory of *dependent* random variables. The difficulty is that "dependence" is an enormously broad concept. Given two random variables $X$ and $Y$, knowing that they are dependent tells us very little about their joint structure. Their relationship could be simple or extraordinarily complex, monotone or oscillatory, local or non-local. Without further assumptions, very little can be said in general, and essentially no theory can be built. This parallels the situation in analysis. Given a function $f: \mathbb{R} \to \mathbb{R}$, knowing merely that $f$ exists tells us nothing useful. But if we assume $f$ is continuous, or differentiable, or convex, a rich theory opens up. The structural assumption is what makes the mathematics tractable. The course takes the following approach: restrict attention to a particularly tractable — yet still general enough to be interesting — form of dependence. We study sequences of random variables $(X_0, X_1, X_2, \ldots)$ in which the conditional distribution of the next state $X_{n+1}$, given the entire history $X_0, X_1, \ldots, X_n$, depends only on the current state $X_n$. In symbols: \begin{align*} \mathbb{P}(X_{n+1} = j \mid X_0 = i_0, \ldots, X_{n-1} = i_{n-1}, X_n = i) = \mathbb{P}(X_{n+1} = j \mid X_n = i). \end{align*} This is the *Markov property*, and a sequence satisfying it is called a *Markov chain*. The intuition is vivid: the future of the process is determined entirely by its present state. The past — however the chain arrived at its current position — is irrelevant once the current state is known. This is sometimes called the "memorylessness" of the process, though the more precise term is the Markov property. The Markov property is a structural constraint, and structural constraints enable proofs. As we will see throughout this course, just this single assumption — that the future depends only on the present — is enough to derive a rich and complete theory: - We can compute the probability of reaching any state from any other state. - We can determine which states a chain will eventually return to, and with what probability. - We can identify when a chain settles into a long-run equilibrium distribution, independent of where it started. - We can reverse time and ask whether the chain looks statistically the same run backwards. None of these would be tractable for general dependent sequences. The Markov property is precisely the right level of constraint: strong enough to admit a complete theory, weak enough to model a vast range of real phenomena. Before the formal definitions begin, it is worth noting that Markov chains are not exotic objects. A simple random walk on $\mathbb{Z}$ — where at each step the walker moves right or left with equal probability, independently of everything except the current position — is a Markov chain. The branching process — where each individual independently produces a random number of offspring — is a Markov chain (with the current population size as the state). Coin-tossing and die-rolling are degenerate Markov chains where the transition probabilities do not depend on the current state at all (since consecutive outcomes are independent). What this course provides is the general framework that encompasses all these examples, and the tools to analyse them systematically. This course studies discrete-time Markov chains on countable state spaces. The journey proceeds in four main phases. First, we define the basic objects and establish how the transition matrix $P = (p_{ij})$ encodes the entire dynamics of a homogeneous chain. Second, we classify states and chains according to their long-run behaviour: which states communicate, which are recurrent (the chain will surely return), and which are transient (there is positive probability of never returning). Simple random walks in dimensions one, two, and three provide concrete illustrations of this dichotomy. Third, we study invariant distributions and convergence to equilibrium — the deep theorem that an irreducible, positive recurrent, aperiodic chain forgets its initial state and converges to a unique stationary distribution. Finally, we examine time-reversal and detailed balance, which characterise chains that look the same run forwards and backwards. Throughout, the emphasis is on understanding the probabilistic structure rather than treating Markov chains as a branch of linear algebra — though the language of matrices will appear naturally and usefully at several points. [/motivation]

## The Transition Matrix

The Markov property makes the structure of a chain remarkably concrete. Since the conditional distribution of $X_{n+1}$ given $X_n = i$ does not depend on the past, it is determined entirely by the probabilities

\begin{align*} p_{ij} = \mathbb{P}(X_{n+1} = j \mid X_n = i), \qquad i, j \in S. \end{align*}

For a homogeneous chain (one whose transition probabilities do not change with time), these numbers are constant across all steps, and we arrange them into the **transition matrix** $P = (p_{ij})_{i,j \in S}$. The entry $p_{ij}$ is the probability of moving from state $i$ to state $j$ in a single step.

For $P$ to be a valid transition matrix, its rows must sum to one: $\sum_{j \in S} p_{ij} = 1$ for every $i \in S$ (since from state $i$, the chain must go somewhere). A matrix with non-negative entries and row sums equal to one is called a **stochastic matrix**.

The initial distribution $\lambda = (\lambda_i)_{i \in S}$, where $\lambda_i = \mathbb{P}(X_0 = i)$, completes the specification. The pair $(\lambda, P)$ determines the joint distribution of the entire sequence $(X_0, X_1, X_2, \ldots)$: for any finite sequence of states $i_0, i_1, \ldots, i_n \in S$,

\begin{align*} \mathbb{P}(X_0 = i_0, X_1 = i_1, \ldots, X_n = i_n) = \lambda_{i_0}\, p_{i_0 i_1}\, p_{i_1 i_2} \cdots p_{i_{n-1} i_n}. \end{align*}

This is the fundamental formula of the subject: the probability of any trajectory is a product of one-step transition probabilities, weighted by the initial distribution.

[example: Weather Model] Consider a simple weather model with state space $S = \{\text{Sunny}, \text{Rainy}\}$, which we abbreviate as $S = \{0, 1\}$ with $0 = \text{Sunny}$ and $1 = \text{Rainy}$. Suppose that if today is sunny, tomorrow is sunny with probability $0.8$ and rainy with probability $0.2$; and if today is rainy, tomorrow is sunny with probability $0.4$ and rainy with probability $0.6$. The transition matrix is \begin{align*} P = \begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix}, \end{align*} where row $i$ gives the transition probabilities from state $i$. Each row sums to one, confirming $P$ is stochastic. Suppose it is sunny on day 0, so the initial distribution is $\lambda = (1, 0)$. What is the probability that day 2 is rainy? There are two trajectories reaching state 1 at time 2: - $0 \to 0 \to 1$: probability $\lambda_0 \cdot p_{00} \cdot p_{01} = 1 \cdot 0.8 \cdot 0.2 = 0.16$. - $0 \to 1 \to 1$: probability $\lambda_0 \cdot p_{01} \cdot p_{11} = 1 \cdot 0.2 \cdot 0.6 = 0.12$. So $\mathbb{P}(X_2 = 1) = 0.16 + 0.12 = 0.28$. Equivalently, the two-step transition probability from state 0 to state 1 is $(P^2)_{01} = 0.28$, since the $n$-step transition probabilities are encoded in the matrix power $P^n$ — a fact known as the **Chapman-Kolmogorov equation**, which we establish in the next chapter. [/example]

[illustration:two-state-weather-transition-diagram]

<!-- illustration-needed: transition diagram for the two-state weather model — two nodes labelled Sunny and Rainy with directed edges labelled with transition probabilities 0.8 (self-loop at Sunny), 0.2 (Sunny to Rainy), 0.4 (Rainy to Sunny), 0.6 (self-loop at Rainy) -->

## Three-State Random Walk

A slightly richer example illustrates the main structural questions of the course. Consider a particle performing a random walk on the state space $S = \{0, 1, 2\}$, where at each step the particle moves to an adjacent state with equal probability, with reflecting boundaries at 0 and 2:

\begin{align*} P = \begin{pmatrix} 0 & 1 & 0 \\ 1/2 & 0 & 1/2 \\ 0 & 1 & 0 \end{pmatrix}. \end{align*}

Every row sums to one. From state 0 the particle must go to state 1; from state 1 it goes to state 0 or 2 with equal probability; from state 2 it must return to state 1. Starting from state 0, we can compute $\mathbb{P}(X_1 = 1) = 1$, $\mathbb{P}(X_2 = 0) = 1/2$, $\mathbb{P}(X_2 = 2) = 1/2$.

This chain is **irreducible**: every state can be reached from every other state. It is also **recurrent**: starting from any state, the chain returns to that state with probability one. It has a unique invariant distribution $\pi = (1/4, 1/2, 1/4)$ — that is, $\pi P = \pi$ and $\sum_i \pi_i = 1$. Verifying this: