| Meetings | Topic | Textbook sections |
|---|---|---|
| W 08/26–F 08/28 | Finite Markov chains. Invariant measures. Classification of states. | §1.1–1.3 |
| W 09/02–F 09/04 | Return times. Transient states. | §1.4–1.6 |
| W 09/09–F 09/11 | Countable Markov chains. Recurrence, transience, positive recurrence, null recurrence. | §2.1–2.3 |
| W 09/16–F 09/18 | Branching process, Poisson process. | §2.4, §3.1 |
| W 09/23–F 09/25 | General continuous-time Markov chains. | §3.2–3.4 |
| W 09/30–F 10/02 | Reversibility and time-reversal of Markov chains. | Ch. 7 |
| W 10/07–F 10/09 | Mixing times. Cheeger inequalities. | |
| W 10/14 | Midterm exam in class | |
| F 10/16 | Conditional expectation | §5.1 |
| W 10/21–F 10/23 | Martingales and the optional sampling theorem | §5.2–5.3 |
| W 10/28–F 10/30 | Uniform integrability and the martingale convergence theorem | §5.4–5.5 |
| W 11/04–F 11/06 | Martingale convergence, cont'd. Maximal inequalities. | §5.5–5.6 |
| W 11/11–F 11/13 | Review of random walk. Introduction to Brownian motion. Markov property of Brownian motion. | §8.1–8.2 |
| W 11/18–F 11/20 | Brownian motion in higher dimensions. Introduction to path properties of Brownian motion. | §8.4 |
| W 11/25–F 11/27 | Thanksgiving holiday: no class | |
| W 12/02–F 12/04 | Brownian motion and partial differential equations. Recurrence and transience of Brownian motion. | §8.5 |
| Sunday 12/13, 9am–12pm | Final exam |
Definition 1.1 (Probability space). A probability space is a triple \((\Omega, \F, \PP)\), where:
A random variable is a map \(X : \Omega \to \X\) for some range \(\X\).
Definition 1.2 (Independence). A family of events \(A_1, \dots, A_n\) is independent if for every \(1 \le i_1 < i_2 < \dots < i_k \le n\), \[ \PP\!\left(A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}\right) = \PP(A_{i_1})\,\PP(A_{i_2}) \cdots \PP(A_{i_k}). \] A family of random variables \(X_1, \dots, X_n\) is independent if for all \(B_1, \dots, B_n \subseteq \X\), \[ \PP\!\left(X_i \in B_i \text{ for all } i = 1, \dots, n\right) = \prod_{i=1}^{n} \PP(X_i \in B_i). \]
If \(A, B\) are events with \(\PP(B) > 0\), the conditional probability of \(A\) given \(B\) is \[ \PP(A \mid B) = \frac{\PP(A \cap B)}{\PP(B)}. \]
Definition 1.3 (Stochastic process). A stochastic process is a family of random variables indexed by some set \(\mathcal{T}\).
Traditionally \(\mathcal{T} = \N\), \(\R\), or \(\R_{\ge 0}\).
Fix a state space \(\X\) and an \(\X\)-valued stochastic process \(X_0, X_1, X_2, \dots\) indexed by \(\N\).
Definition 1.4 (Markov chain). The process \((X_n)_{n \in \N}\) is a Markov chain if for all \(n \in \N\) and all states \(i_0, i_1, \dots, i_{n-1}, i, j \in \X\) for which the conditioning event has positive probability, \[ \PP\!\left(X_{n+1} = j \mid X_n = i,\, X_{n-1} = i_{n-1},\, \dots,\, X_0 = i_0\right) = \PP\!\left(X_{n+1} = j \mid X_n = i\right). \] That is: the future is independent of the past, given the present (the Markov property).
Definition 1.5 (Time-homogeneity). A Markov chain is time-homogeneous if \(\PP(X_{n+1} = j \mid X_n = i)\) does not depend on \(n\). In that case we write \[ p_{ij} \coloneqq \PP(X_{n+1} = j \mid X_n = i), \] the transition probabilities of the chain.
Note that \(p_{ij} \in [0,1]\) and \(\sum_{j \in \X} p_{ij} = 1\) for every \(i\). From now on, all chains are assumed time-homogeneous.
Proposition 1.6. Let \((X_n)\) be a time-homogeneous Markov chain and let \(i_0, i_1, \dots, i_n \in \X\). Then \[ \PP\!\left(X_0 = i_0,\, X_1 = i_1,\, \dots,\, X_n = i_n\right) = \PP(X_0 = i_0)\, p_{i_0 i_1} p_{i_1 i_2} \cdots p_{i_{n-1} i_n}. \]
Proof. By induction on \(n\). The case \(n = 0\) is the statement \(\PP(X_0 = i_0) = \PP(X_0 = i_0)\).
Assume the formula holds for \(n-1\). Write \(A = \{X_0 = i_0, \dots, X_{n-1} = i_{n-1}\}\). If \(\PP(A) = 0\), then both sides vanish (the left side because it is at most \(\PP(A)\), the right side by the inductive hypothesis), so assume \(\PP(A) > 0\). By the definition of conditional probability, \[ \PP\!\left(X_n = i_n,\, A\right) = \PP\!\left(X_n = i_n \mid A\right) \PP(A). \] By the Markov property and time-homogeneity, \(\PP(X_n = i_n \mid A) = \PP(X_n = i_n \mid X_{n-1} = i_{n-1}) = p_{i_{n-1} i_n}\). Applying the inductive hypothesis to \(\PP(A)\) gives \[ \PP\!\left(X_n = i_n,\, A\right) = p_{i_{n-1} i_n} \cdot \PP(X_0 = i_0)\, p_{i_0 i_1} \cdots p_{i_{n-2} i_{n-1}}, \] which is the claim. ∎
Remark 1.7. So the law of the chain is determined by two ingredients: the initial distribution of \(X_0\) and the transition probabilities \(p_{ij}\).
We organize the \(p_{ij}\) into a transition matrix \(P = (p_{ij})_{i, j \in \X}\). If \(|\X| = N\), this is the \(N \times N\) matrix \[ P = \begin{pmatrix} p_{11} & p_{12} & \dots & p_{1N} \\ p_{21} & p_{22} & \dots & p_{2N} \\ \vdots & \vdots & \ddots & \vdots \\ p_{N1} & p_{N2} & \dots & p_{NN} \end{pmatrix}. \]
Its entries are nonnegative and each row sums to \(1\); such a matrix is called a stochastic matrix.
Example 1.8 (Simple weather model). Take \(\X = \{\text{raining},\ \text{not raining}\}\). If it rains today, it rains tomorrow with probability \(\alpha\); if it does not rain today, it rains tomorrow with probability \(\beta\). Labelling rows by today's weather and columns by tomorrow's, \(R = \text{raining}\) and \(N = \text{not raining}\): \[ P = \begin{array}{c|cc} & R & N \\ \hline R & \alpha & 1 - \alpha \\ N & \beta & 1 - \beta \end{array}. \] Each row sums to \(1\), as it must.
Example 1.9 (Random walk with absorbing boundaries). Let \(\X = \{0, 1, \dots, M\}\). From an interior state the walker steps right with probability \(p\) and left with probability \(1 - p\); the states \(0\) and \(M\) are absorbing (“falling off the cliff”). Explicitly:
Indexing rows and columns by \(0, 1, \dots, M\), \[ P = \begin{pmatrix} 1 & 0 & 0 & \dots & \dots & 0 \\ 1-p & 0 & p & \ddots & & \vdots \\ 0 & 1-p & 0 & p & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & 1-p & 0 & p \\ 0 & \dots & \dots & 0 & 0 & 1 \end{pmatrix}. \] If instead the boundaries are reflecting, only the first and last rows change.
Example 1.10 (Random walk on a graph). Let \(G = (V, E)\) be a finite graph, where \(V\) is the vertex set and \(E\) the edge set, \[ E \subseteq \binom{V}{2} = \bigl\{\, \{i, j\} \;:\; i, j \in V,\ i \neq j \,\bigr\}. \] Write \(i \sim j\) when \(\{i, j\} \in E\) (“\(i\) is adjacent to \(j\)”), and define the degree of a vertex \(i\) by \[ d_i = \#\{\, j \in V \;:\; j \sim i \,\}. \] Assume \(d_i \ge 1\) for every \(i\), i.e. no isolated vertices. Simple random walk on \(G\) is the chain with state space \(\X = V\) and \[ p_{ij} = \begin{cases} 1/d_i, & j \sim i, \\ 0, & \text{otherwise.} \end{cases} \] This is stochastic: \(\sum_{j} p_{ij} = d_i \cdot \frac{1}{d_i} = 1\).
The Markov property is not a property of a physical system. It is a property of the model. We can always enlarge the state space to include whatever memory we may need to model the next step.