Stochastic Processes

"A stochastic process is a mathematical model for a randomly evolving system. To understand modern AI is to understand how randomness unfolds over time."

• inspired by Doob, Stochastic Processes (1953)

Overview

A stochastic process is a collection of random variables indexed by time: $\{X_t\}_{t \in T}$. Where probability theory asks "what is the distribution of a single random outcome?", stochastic processes ask "how does a random system evolve?" This shift - from snapshots to trajectories - is essential for understanding modern AI.

The trajectory of SGD through a loss landscape is a stochastic process. The sequence of tokens generated by a language model is a stochastic process. The forward noising schedule of a diffusion model is a stochastic process. The value function estimates in reinforcement learning satisfy martingale properties. None of these can be understood through static probability alone.

This section builds the rigorous framework - filtrations, adapted processes, martingales, stopping times - and applies it to the canonical examples: random walks, Poisson processes, Brownian motion, and stationary Gaussian processes. Markov chains, which deserve their own dedicated treatment, are previewed here and developed fully in Section07 Markov Chains.

Prerequisites

• Section01 Introduction and Random Variables - probability spaces, random variables, measurability
• Section03 Joint Distributions - joint distributions, independence, conditional distributions
• Section04 Expectation and Moments - conditional expectation $\mathbb{E}[X|\mathcal{F}]$, MGF, tower property
• Section05 Concentration Inequalities - Azuma-Hoeffding, McDiarmid (Doob martingale used there)

Companion Notebooks

Learning Objectives

After completing this section, you will be able to:

1. Define a stochastic process and classify it by time/state space type
2. Define filtrations and adapted processes; interpret information accumulation formally
3. Define martingales and verify the martingale property for standard examples
4. State and apply Doob's Optional Stopping Theorem with correct conditions
5. Construct the Doob martingale and connect it to McDiarmid's inequality
6. Define the Poisson process via its three characterising properties and apply superposition/thinning
7. Define Brownian motion via Wiener's axioms and compute quadratic variation
8. Explain the Ornstein-Uhlenbeck process and its connection to regularisation
9. Define strict and wide-sense stationarity, ergodicity, and the Wiener-Khinchin theorem
10. Define Gaussian processes, specify the kernel as covariance function, and compute GP posteriors
11. Explain how diffusion models implement a forward stochastic process and connect to Brownian motion
12. Model SGD as a stochastic process and identify where martingale/near-martingale structure appears

---

Table of Contents

• 1. Intuition and Overview
  • 1.1 What Is a Stochastic Process?
  • 1.2 The Central Examples
  • 1.3 Why Processes Matter for AI
  • 1.4 Historical Timeline
• 2. Formal Framework
  • 2.1 Probability Spaces and Filtrations
  • 2.2 Classification of Stochastic Processes
  • 2.3 Stopping Times
  • 2.4 Sample Paths and Almost-Sure Properties
• 3. Martingales
  • 3.1 Definition and Intuition
  • 3.2 Examples of Martingales
  • 3.3 Doob's Optional Stopping Theorem
  • 3.4 Doob's Martingale Inequalities
  • 3.5 The Doob Martingale Construction
  • 3.6 Supermartingales and Submartingales
  • 3.7 ML: SGD as a Near-Martingale
• 4. Discrete-Time Random Walks
  • 4.1 Simple Random Walk
  • 4.2 Recurrence and Transience
  • 4.3 Gambler's Ruin
  • 4.4 ML: Token Sequences as Random Walks
• 5. Poisson Processes
  • 5.1 Definition and Characterisation
  • 5.2 Properties: Superposition and Thinning
  • 5.3 Compound Poisson Process
  • 5.4 ML: Event Streams and Token Timing
• 6. Brownian Motion
  • 6.1 Definition and Wiener's Axioms
  • 6.2 Key Properties and Quadratic Variation
  • 6.3 Brownian Motion as a Limit
  • 6.4 Geometric Brownian Motion
  • 6.5 Ornstein-Uhlenbeck Process
  • 6.6 ML: Diffusion Models
• 7. Stationary Processes and Ergodicity
  • 7.1 Strict and Wide-Sense Stationarity
  • 7.2 Ergodicity and the Ergodic Theorem
  • 7.3 Autocorrelation and Power Spectral Density
  • 7.4 Gaussian Processes
  • 7.5 ML: RoPE and Stationarity in Attention
• 8. Preview: Markov Chains
  • 8.1 The Markov Property
  • 8.2 Forward Reference
• 9. ML Deep Dive
  • 9.1 SGD Trajectory as Stochastic Process
  • 9.2 RL Value Functions as Martingales
  • 9.3 Attention over Sequences
  • 9.4 Diffusion Model Schedules
• 10. Common Mistakes
• 11. Exercises
• 12. Why This Matters for AI (2026 Perspective)
• 13. Conceptual Bridge

---

1. Intuition and Overview

1.1 What Is a Stochastic Process?

A stochastic process is a family $\{X_t\}_{t \in T}$ of random variables defined on a common probability space $(\Omega, \mathcal{F}, P)$, indexed by a set $T$ called the index set or time set. For each fixed outcome $\omega \in \Omega$, the mapping $t \mapsto X_t(\omega)$ is called a sample path or realisation of the process.

The key conceptual shift from classical probability: rather than asking "what is the distribution of $X$?", we ask "how does the random system $\{X_t\}$ evolve over time?" This trajectory-level view captures phenomena that static distributions cannot: memory, feedback, path dependence, and accumulation of information.

Informal classification: The simplest stochastic process is a sequence of iid random variables - no memory, no dependence. More interesting processes have memory (the present depends on the past), structure (the conditional distributions have a specific form), or continuity (sample paths are almost surely continuous). The richest models - Brownian motion, diffusion processes - have all three.

For AI: Almost every quantity that evolves during training or inference is a stochastic process. The parameter vector $\theta_t$ after $t$ steps of SGD is a stochastic process. The hidden state $h_t$ of an RNN at position $t$ is a stochastic process. The sequence of tokens $(w_1, w_2, \ldots)$ sampled from an LLM is a stochastic process. The noise level $\sigma_t$ in a diffusion model forward pass is a stochastic process. Stochastic process theory gives us the mathematical language to reason about all of these rigorously.

1.2 The Central Examples

The five canonical stochastic processes appear throughout mathematics and AI:

1. Simple Random Walk (SRW): $S_n = \sum_{k=1}^n X_k$ where $X_k \stackrel{iid}{\sim} \text{Uniform}\{-1,+1\}$. Discrete time, discrete state space. Models fair gambling, particle diffusion in discrete space, and gradient noise accumulation.

2. Poisson Process: $N(t)$ = number of events in $[0,t]$, with $N(t) - N(s) \sim \text{Poisson}(\lambda(t-s))$ independent of the past. Continuous time, discrete (integer) state space. Models arrival streams, request queues, neuron spike trains.

3. Brownian Motion (Wiener Process): $B_t$ with $B_0 = 0$, continuous paths, $B_t - B_s \sim \mathcal{N}(0, t-s)$ independent of the past. Continuous time, continuous state space. The fundamental building block of continuous-time stochastic processes, and the forward process in diffusion models.

4. Gaussian Process: A process where every finite collection $(X_{t_1}, \ldots, X_{t_n})$ is jointly Gaussian. Fully specified by its mean function $\mu(t)$ and covariance kernel $k(s,t)$. Foundation of Gaussian process regression (Bayesian nonparametrics) and closely related to neural network functions in the infinite-width limit.

5. Markov Chain: $\{X_n\}$ where $P(X_{n+1} | X_0,\ldots,X_n) = P(X_{n+1} | X_n)$ - the past matters only through the present. Discrete time, arbitrary state space. The backbone of MCMC, reinforcement learning, and language model token generation. Full treatment: Section07 Markov Chains.

1.3 Why Processes Matter for AI

Stochastic process theory provides the theoretical foundation for several pillar areas of modern AI:

Diffusion models (DDPM, DDIM, Score SDE) define a forward process that progressively corrupts data with Gaussian noise - this is literally a discrete-time approximation to the Ornstein-Uhlenbeck SDE. The reverse process learned by the neural network is a time-reversed SDE, and training minimises a score-matching objective derived from Ito calculus.

SGD dynamics can be approximated by a continuous-time diffusion SDE: $d\theta = -\nabla L(\theta)\,dt + \sqrt{2\beta^{-1}}dB_t$ where $\beta^{-1}$ is the effective noise temperature proportional to the learning rate divided by batch size. This approximation (Mandt et al., 2017; Li et al., 2017) explains why SGD finds flat minima: the stationary distribution of the SDE concentrates in regions of low curvature.

Reinforcement learning uses the discounted return $G_t = \sum_{k=0}^\infty \gamma^k r_{t+k}$, which is a function of the trajectory $(r_t, r_{t+1}, \ldots)$ - a stochastic process. The temporal difference error $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ forms a martingale difference sequence under the optimal value function, and TD-learning is an online martingale approximation algorithm.

Gaussian processes are used as priors over functions in Bayesian optimisation (tuning LLM hyperparameters), and the neural tangent kernel theory shows that infinite-width neural networks converge to GPs. RoPE (Rotary Position Embedding) encodes relative position using a stationary kernel - exploiting the wide-sense stationarity machinery developed in Section7.

1.4 Historical Timeline

---

2. Formal Framework

2.1 Probability Spaces and Filtrations

The rigorous foundation of stochastic processes builds on probability spaces enhanced with a filtration - a formal model of accumulating information.

Definition (Filtered Probability Space). A filtered probability space is a quadruple $(\Omega, \mathcal{F}, (\mathcal{F}_t)_{t \geq 0}, P)$ where:

• $(\Omega, \mathcal{F}, P)$ is a probability space
• $(\mathcal{F}_t)_{t \geq 0}$ is a filtration: an increasing family of sub-$\sigma$-algebras, $\mathcal{F}_s \subseteq \mathcal{F}_t \subseteq \mathcal{F}$ for all $s \leq t$

Intuitively, $\mathcal{F}_t$ represents the information available at time $t$ - everything that has been observed up to and including time $t$. The filtration captures how information accumulates: knowing more over time means larger $\sigma$-algebras.

Definition (Adapted Process). A stochastic process $\{X_t\}$ is adapted to the filtration $(\mathcal{F}_t)$ if $X_t$ is $\mathcal{F}_t$-measurable for each $t$. Intuitively: the value of the process at time $t$ is determined by information available at time $t$ (not the future).

The natural filtration: Given a process $\{X_t\}$, the natural filtration is $\mathcal{F}_t^X = \sigma(X_s : s \leq t)$ - the $\sigma$-algebra generated by the process up to time $t$. Every process is adapted to its natural filtration.

For AI: In online learning, $\mathcal{F}_t$ represents the set of training examples seen up to step $t$. The model parameters $\theta_t$ are $\mathcal{F}_t$-measurable (they depend only on past data). A look-ahead bias - where $\theta_t$ depends on future data - violates adaptedness and invalidates PAC bounds.

In a causal language model, the token at position $t$ is sampled conditioned on all previous tokens - this is precisely the adaptedness condition. Non-causal (bidirectional) models like BERT use a different filtration where $\mathcal{F}_t$ includes information from both past and future.

Standard conditions (usual conditions): A filtration satisfies the usual conditions if:

1. $(\mathcal{F}_t)$ is right-continuous: $\mathcal{F}_t = \bigcap_{s > t} \mathcal{F}_s$
2. $\mathcal{F}_0$ contains all $P$-null sets (completeness)

These technical conditions ensure stopping times and martingales behave as expected. All filtrations in this section are assumed to satisfy the usual conditions.

2.2 Classification of Stochastic Processes

Processes are classified by the structure of their time set $T$ and state space $S$:

TAXONOMY OF STOCHASTIC PROCESSES
========================================================================

                    State Space S
                    ---------------------------------
                    Discrete             Continuous
                    ---------------------------------
  Time  Discrete  | Markov chains        Random walk  |
  Set T |          | HMMs                 AR(p) models |
        |          | Galton-Watson trees               |
        +----------+----------------------------------+
        Continuous | Poisson process      Brownian mot |
                  | Birth-death proc     OU process   |
                  | Counting processes   Diffusion SDE|
                   ---------------------------------

========================================================================

Discrete time, discrete state: Markov chains, hidden Markov models (HMMs used in speech recognition), random walks on graphs. The transition dynamics are described by a stochastic matrix.

Discrete time, continuous state: Random walks in $\mathbb{R}^d$, AR/ARMA time series models, recurrent neural network hidden states. State space is $\mathbb{R}^d$ for some dimension $d$.

Continuous time, discrete state: Poisson processes, birth-death processes, queueing models. Transitions happen at random times; between transitions the state is constant.

Continuous time, continuous state: Brownian motion, Ornstein-Uhlenbeck process, general diffusion SDEs. These are the most mathematically sophisticated and most relevant to diffusion models and SGD dynamics.

2.3 Stopping Times

A stopping time (or optional time) formalises the idea of a "decision made using only available information."

Definition (Stopping Time). A random variable $\tau: \Omega \to [0,\infty]$ is a stopping time with respect to filtration $(\mathcal{F}_t)$ if $\{\tau \leq t\} \in \mathcal{F}_t$ for all $t \geq 0$. Equivalently, the decision "stop now" can be made using only information available at the current time.

Examples:

• $\tau = 5$: constant time - trivially a stopping time
• $\tau = \inf\{t : X_t \geq a\}$ (first passage time): stopping time (the event $\{\tau \leq t\} = \{\max_{s \leq t} X_s \geq a\}$ is $\mathcal{F}_t$-measurable)
• $\tau = \sup\{t \leq T : X_t \geq a\}$ (last time above level): not a stopping time (requires future knowledge)

The $\sigma$-algebra $\mathcal{F}_\tau$: For a stopping time $\tau$, the $\sigma$-algebra at $\tau$ is $\mathcal{F}_\tau = \{A \in \mathcal{F} : A \cap \{\tau \leq t\} \in \mathcal{F}_t \text{ for all } t\}$. This represents "information available at the random time $\tau$."

For AI: Early stopping in neural network training is a stopping time: the rule "stop when validation loss hasn't improved for $k$ steps" depends only on past validation losses - it is $\mathcal{F}_t$-measurable. In contrast, "stop at the training step that achieves minimum test loss" is NOT a stopping time - it requires knowing future test losses.

In RL, $\tau$ = "the first time the agent reaches the goal state" is a stopping time. Doob's Optional Stopping Theorem (Section3.3) characterises the distribution of $M_\tau$ - the martingale value at this random time.

2.4 Sample Paths and Almost-Sure Properties

For each fixed $\omega \in \Omega$, the sample path $t \mapsto X_t(\omega)$ is an ordinary function of time. The regularity of sample paths (continuity, measurability, boundedness) is crucial for the applicability of theorems.

Path properties:

• Continuous paths: $t \mapsto X_t(\omega)$ is continuous for a.e. $\omega$. Example: Brownian motion.
• Cadlag paths (right-continuous with left limits): $X_t(\omega)$ is right-continuous with left limits for a.e. $\omega$. Example: Poisson process. Pronounced "cadlag" from French continu a droite, limite a gauche.
• Caglad paths: left-continuous with right limits. Useful in predictable integrands.

Why continuity matters: A process with continuous paths can be approximated by discrete-time processes as the mesh goes to zero - this is the content of Donsker's invariance principle (Section6.3) and justifies the SDE approximation of SGD. A process with only cadlag paths (like Poisson) has discontinuities that cannot be approximated this way.

Almost-sure properties: Properties that hold with probability one (a.s.) are the gold standard. For example, Brownian motion is a.s. nowhere differentiable - every sample path is continuous but has infinite variation everywhere. This non-differentiability is responsible for the $\sqrt{dt}$ scaling of noise in SDEs (Ito's formula) and explains why diffusion model noise scales as $\sqrt{\bar{\alpha}_t}$ rather than linearly in time.

---

3. Martingales

3.1 Definition and Intuition

The word martingale comes from a gambling strategy: double your bet after each loss. Mathematically, a martingale captures the notion of a "fair game" - the best prediction of the future value is the current value, given everything known so far.

Definition (Martingale). An adapted process $\{M_t\}_{t \geq 0}$ with $\mathbb{E}[|M_t|] < \infty$ for all $t$ is a martingale with respect to filtration $(\mathcal{F}_t)$ if:

$$\mathbb{E}[M_t \mid \mathcal{F}_s] = M_s \quad \text{for all } s \leq t$$

The condition says: given all information up to time $s$, the best prediction of $M_t$ is $M_s$. The process neither drifts up nor down in conditional expectation.

Three types:

• Martingale: $\mathbb{E}[M_t | \mathcal{F}_s] = M_s$ - fair game
• Submartingale: $\mathbb{E}[M_t | \mathcal{F}_s] \geq M_s$ - tends upward on average (e.g., convex functions of martingales via Jensen)
• Supermartingale: $\mathbb{E}[M_t | \mathcal{F}_s] \leq M_s$ - tends downward on average

Discrete-time discrete version: $\{M_n\}_{n \geq 0}$ is a martingale if $\mathbb{E}[M_{n+1} | M_0,\ldots,M_n] = M_n$ for all $n$. This is equivalent to the martingale difference condition: $\mathbb{E}[M_{n+1} - M_n | \mathcal{F}_n] = 0$.

Immediate consequence (tower property): For any $s \leq t$, $\mathbb{E}[M_t] = \mathbb{E}[\mathbb{E}[M_t | \mathcal{F}_s]] = \mathbb{E}[M_s]$. So the mean of a martingale is constant: $\mathbb{E}[M_t] = \mathbb{E}[M_0]$ for all $t$.

3.2 Examples of Martingales

Example 1: Partial Sums of Zero-Mean iid. Let $X_1, X_2, \ldots$ be iid with $\mathbb{E}[X_i] = 0$. Then $S_n = \sum_{k=1}^n X_k$ is a martingale:

$$\mathbb{E}[S_{n+1} | \mathcal{F}_n] = \mathbb{E}[S_n + X_{n+1} | \mathcal{F}_n] = S_n + \mathbb{E}[X_{n+1}] = S_n$$

Example 2: Products of Unit-Mean iid. Let $X_1, X_2, \ldots$ be iid with $\mathbb{E}[X_i] = 1$, $X_i > 0$. Then $M_n = \prod_{k=1}^n X_k$ is a martingale:

$$\mathbb{E}[M_{n+1} | \mathcal{F}_n] = M_n \cdot \mathbb{E}[X_{n+1}] = M_n$$

This is the likelihood ratio (Radon-Nikodym derivative) martingale - fundamental to sequential hypothesis testing and importance sampling.

Example 3: Conditional Expectations. For any integrable $Z$ and filtration $(\mathcal{F}_t)$, the process $M_t = \mathbb{E}[Z | \mathcal{F}_t]$ is a martingale (the Doob martingale). This follows directly from the tower property: $\mathbb{E}[M_t | \mathcal{F}_s] = \mathbb{E}[\mathbb{E}[Z|\mathcal{F}_t] | \mathcal{F}_s] = \mathbb{E}[Z|\mathcal{F}_s] = M_s$.

Example 4: Polya Urn. An urn contains $r$ red and $b$ blue balls. At each step, draw a ball, record its colour, return it with one extra ball of the same colour. Let $R_n$ = fraction of red balls after step $n$. Then $R_n$ is a martingale. The limiting fraction $R_\infty \sim \text{Beta}(r, b)$.

Example 5: Squared SRW minus time. The simple random walk $S_n$ satisfies $S_n^2 - n$ is a martingale (when $\text{Var}(X_k) = 1$):

$$\mathbb{E}[S_{n+1}^2 - (n+1) | \mathcal{F}_n] = \mathbb{E}[(S_n + X_{n+1})^2 | \mathcal{F}_n] - n - 1 = S_n^2 + 1 - n - 1 = S_n^2 - n$$

For AI: The gradient of the expected loss $\nabla L(\theta)$ minus the mini-batch gradient estimate $\nabla \hat{L}(\theta)$ is a martingale difference - the fundamental quantity that makes SGD unbiased. The accumulation of these martingale differences over training steps determines the SGD trajectory.

3.3 Doob's Optional Stopping Theorem

Doob's Optional Stopping Theorem (OST) is perhaps the most useful result in martingale theory. It answers: "what is the expected value of a martingale at a stopping time?"

Naively: Since $\mathbb{E}[M_n] = \mathbb{E}[M_0]$ for all $n$, one might expect $\mathbb{E}[M_\tau] = \mathbb{E}[M_0]$ for any stopping time $\tau$. This is false in general (e.g., the doubling strategy in gambling can exploit martingale properties without bounded stopping times).

Theorem (Doob's Optional Stopping Theorem). Let $\{M_n\}$ be a martingale and $\tau$ a stopping time. Then $\mathbb{E}[M_\tau] = \mathbb{E}[M_0]$ provided at least one of the following holds:

1. $\tau$ is bounded: $\tau \leq N$ a.s. for some constant $N$
2. $\mathbb{E}[\tau] < \infty$ and $|M_{n+1} - M_n| \leq C$ a.s. for some constant $C$
3. $\mathbb{E}[\sup_{n} |M_{n \wedge \tau}|] < \infty$ (uniformly integrable)

Proof sketch (bounded case). $\mathbb{E}[M_\tau] = \sum_{k=0}^N \mathbb{E}[M_k \mathbf{1}_{\tau=k}]$. Write $M_k = M_N - \sum_{j=k}^{N-1}(M_{j+1}-M_j)$, use adaptedness of $\{\tau=k\}$, and the martingale property $\mathbb{E}[M_{j+1}-M_j | \mathcal{F}_j] = 0$. Each cross term vanishes, leaving $\mathbb{E}[M_\tau] = \mathbb{E}[M_N] = \mathbb{E}[M_0]$. $\square$

Application: Gambler's Ruin. Symmetric random walk $S_n$ on $\{0, 1, \ldots, N\}$ with absorbing barriers. Start at $S_0 = k$. Let $\tau = \inf\{n : S_n \in \{0, N\}\}$.

Since $S_n$ is a martingale and $\tau$ is bounded by Wald's identity (it can be shown $\mathbb{E}[\tau] < \infty$):

$$\mathbb{E}[S_\tau] = \mathbb{E}[S_0] = k$$ $$\mathbb{E}[S_\tau] = N \cdot P(S_\tau = N) + 0 \cdot P(S_\tau = 0) = N \cdot P(\text{win})$$ $$\Rightarrow P(\text{win}) = k/N$$

Also: $S_n^2 - n$ is a martingale, so $\mathbb{E}[S_\tau^2 - \tau] = k^2 - 0$, giving $\mathbb{E}[\tau] = \mathbb{E}[S_\tau^2] - k^2 = (N \cdot (k/N) \cdot N + 0) - k^2 = k(N-k)$.

3.4 Doob's Martingale Inequalities

Beyond Optional Stopping, Doob proved several fundamental inequalities that control the maximum of a martingale.

Theorem (Doob's Maximal Inequality). For a non-negative submartingale $\{M_n\}$ and $\lambda > 0$:

$$\lambda \cdot P\!\left(\max_{0 \leq k \leq n} M_k \geq \lambda\right) \leq \mathbb{E}[M_n]$$

Corollary (Doob's $L^2$ Inequality). For a martingale $\{M_n\}$ with $\mathbb{E}[M_n^2] < \infty$:

$$\mathbb{E}\!\left[\max_{0 \leq k \leq n} M_k^2\right] \leq 4\mathbb{E}[M_n^2]$$

Theorem (Martingale Convergence Theorem, Doob 1953). Every $L^1$-bounded martingale (i.e., $\sup_n \mathbb{E}[|M_n|] < \infty$) converges almost surely to a finite limit $M_\infty$.

This convergence theorem is the rigorous foundation for why TD-learning and Q-learning converge under appropriate conditions - the value function updates form a bounded supermartingale under the optimal policy.

3.5 The Doob Martingale Construction

Definition. For a function $f(X_1,\ldots,X_n)$ of independent random variables, define:

$$M_k = \mathbb{E}[f(X_1,\ldots,X_n) \mid X_1,\ldots,X_k], \quad k = 0, 1, \ldots, n$$

Then $M_0 = \mathbb{E}[f]$, $M_n = f(X_1,\ldots,X_n)$, and $\{M_k\}$ is a martingale (by tower property). This is the Doob martingale for $f$.

Connection to McDiarmid: The martingale differences are $D_k = M_k - M_{k-1}$. If $f$ has bounded differences $|f(\ldots,x_k,\ldots) - f(\ldots,x_k',\ldots)| \leq c_k$, then $|D_k| \leq c_k$ a.s. Applying Azuma's inequality to the martingale $(M_0, M_1, \ldots, M_n)$:

$$P(f - \mathbb{E}[f] \geq t) = P(M_n - M_0 \geq t) \leq \exp\!\left(\frac{-2t^2}{\sum_k c_k^2}\right)$$

This is exactly McDiarmid's inequality - it is Azuma applied to the Doob martingale. The Doob construction thus unifies martingale theory with the concentration inequalities of Section05.

For AI: The empirical risk $\hat{R}(h) = \frac{1}{n}\sum_{i=1}^n \ell(h(x_i), y_i)$ is a function of $n$ independent training examples, each contributing $c_i = 1/n$ bounded difference. The Doob martingale $M_k = \mathbb{E}[\hat{R}(h) | z_1,\ldots,z_k]$ converges from $R(h)$ to $\hat{R}(h)$, and Azuma gives the McDiarmid generalisation bound $P(|\hat{R}-R| \geq t) \leq 2e^{-2nt^2}$.

3.6 Supermartingales and Submartingales

Supermartingales ($\mathbb{E}[M_{n+1}|\mathcal{F}_n] \leq M_n$) model processes that decrease in conditional expectation - losing bets, damped oscillators, optimisation algorithms.

Key example: For a Lyapunov function $V(\theta)$ in optimisation, if $\mathbb{E}[V(\theta_{n+1}) | \theta_n] \leq V(\theta_n) - \alpha \|\nabla L(\theta_n)\|^2 + \text{noise}$, then $V(\theta_n)$ is a "noisy supermartingale." Under appropriate noise control, the Martingale Convergence Theorem guarantees $V(\theta_n) \to V^*$ a.s., implying convergence to a critical point.

Submartingales ($\mathbb{E}[M_{n+1}|\mathcal{F}_n] \geq M_n$) arise as convex functions of martingales (by Jensen's inequality: $f$ convex, $M_n$ martingale $\Rightarrow$ $f(M_n)$ submartingale). Examples: $|M_n|$, $M_n^2$, $e^{tM_n}$ (for $t > 0$).

For AI: The training loss trajectory is typically a supermartingale in the early phases of training (decreasing in expectation per step). Plateau phases correspond to near-martingale behaviour. The Doob decomposition theorem guarantees any submartingale $Y_n$ can be written as $Y_n = M_n + A_n$ where $M_n$ is a martingale and $A_n$ is a predictable increasing process - this decomposition underlies variance reduction in stochastic optimisation.

3.7 ML: SGD as a Near-Martingale

Consider the SGD update: $\theta_{n+1} = \theta_n - \eta \nabla \hat{L}_n(\theta_n)$ where $\hat{L}_n$ is the mini-batch loss. Define $g_n = \nabla \hat{L}_n(\theta_n) - \nabla L(\theta_n)$ = gradient noise.

Since each mini-batch is sampled iid, $\mathbb{E}[g_n | \theta_n] = 0$ - the gradient noise is a martingale difference sequence. The noise accumulation $S_N = \sum_{n=1}^N g_n$ forms a martingale.

The diffusion approximation (continuous-time limit): As step size $\eta \to 0$ with $N \to \infty$ and $\eta N \to T$ fixed, the SGD trajectory converges in distribution to the SDE:

$$d\theta_t = -\nabla L(\theta_t)\,dt + \sqrt{\eta \cdot \Sigma(\theta_t)}\,dB_t$$

where $\Sigma(\theta) = \text{Cov}(\nabla \hat{L}(\theta))$ is the gradient covariance matrix and $B_t$ is a Brownian motion in parameter space. The noise temperature $\eta/B$ (learning rate / batch size) controls the diffusion coefficient.

Variance reduction methods: SVRG (Stochastic Variance Reduced Gradient) and SAG (Stochastic Average Gradient) reduce $\|g_n\|$ to make SGD closer to a true gradient descent. They convert the martingale noise $g_n$ from $O(1)$ variance to $O(1/n)$ variance by periodically computing the full gradient. The convergence improvement from $O(1/\sqrt{n})$ (SGD) to $O(\rho^n)$ (linear convergence of SVRG) directly reflects this martingale variance reduction.

---

4. Discrete-Time Random Walks

4.1 Simple Random Walk

Definition. The simple random walk (SRW) on $\mathbb{Z}$ is $S_0 = 0$, $S_n = \sum_{k=1}^n X_k$ where $X_k \stackrel{iid}{\sim} \text{Uniform}\{-1, +1\}$ (so $P(X_k = +1) = P(X_k = -1) = 1/2$).

Distribution: $P(S_n = k) = \binom{n}{(n+k)/2} 2^{-n}$ for $k \equiv n \pmod{2}$. By CLT: $S_n / \sqrt{n} \xrightarrow{d} \mathcal{N}(0,1)$.

Key identity (Reflection Principle): The number of paths from $(0,0)$ to $(n, k)$ that touch or cross the $x$-axis equals the number of all paths from $(0, -2)$ to $(n, k)$. This gives:

$$P\!\left(\max_{0 \leq k \leq n} S_k \geq m\right) = 2P(S_n \geq m) - P(S_n = m)$$

for integers $m > 0$ - approximately $2P(S_n \geq m)$ for large $n$.

The arc-sine law: The last time the SRW is at 0 before time $n$ has a distribution that concentrates near 0 and $n$, not at $n/2$ as intuition suggests. Formally: if $L_n = \max\{k \leq n : S_k = 0\}$, then $L_n/n \xrightarrow{d} \text{Arcsine}(0,1)$.

Biased random walk: With $P(X_k = +1) = p$, $P(X_k = -1) = 1-p$, the walk has drift $\mu = 2p-1$. It is a submartingale if $p > 1/2$, supermartingale if $p < 1/2$, martingale if $p = 1/2$. The exponential tilting $M_n = ((1-p)/p)^{S_n}$ is a martingale for any $p$.

4.2 Recurrence and Transience

Definition. A random walk is recurrent if it returns to its starting point with probability 1; transient if it escapes to infinity with positive probability.

Polya's Theorem (1921). The SRW on $\mathbb{Z}^d$ is:

• Recurrent for $d = 1$ and $d = 2$ (probability 1 of returning to origin)
• Transient for $d \geq 3$ (positive probability of never returning)

Proof idea for $d=1$: The expected number of returns to 0 is $\sum_{n} P(S_{2n}=0) = \sum_n \binom{2n}{n}4^{-n} \sim \sum_n (1/\sqrt{\pi n}) = \infty$ by Stirling. Since the expected number of returns is infinite, the walk must return infinitely often (Borel-Cantelli).

Proof idea for $d=3$: $\sum_n P(S_{2n}=0) = \sum_n \binom{2n}{n}^3 6^{-2n} < \infty$ by Stirling, so by Borel-Cantelli the walk returns only finitely many times.

For AI: In gradient descent on a loss landscape with one flat direction (rank deficiency), the gradient is zero in that direction - the component of the iterate in the flat direction performs a random walk. In 2D, this walk is recurrent: training can drift arbitrarily far in the flat direction, explaining parameter growth and the need for weight decay (which adds a restoring force, converting the walk from recurrent to transient).

4.3 Gambler's Ruin

Setup: A gambler starts with $k$ dollars, plays a fair game (win/lose \1$each round), and stops when reaching$$N$(success) or$$0$ (ruin).

Result (via OST): Using the martingales $S_n$ and $S_n^2 - n$:

• $P(\text{ruin}) = 1 - k/N$, $P(\text{success}) = k/N$
• $\mathbb{E}[\tau] = k(N-k)$ (expected duration)

Biased gambler ($p \neq 1/2$): Use the exponential martingale $M_n = ((1-p)/p)^{S_n}$:

$$P(\text{success}) = \frac{1 - (q/p)^k}{1 - (q/p)^N}, \quad q = 1-p$$

For AI: Gambler's ruin models early stopping in training: the training loss random-walks around a local minimum, and we stop when it either reaches a "good" threshold (success) or explodes (ruin). The expected stopping time $k(N-k)$ motivates why learning rate schedules that reduce the step size as training progresses can reduce expected convergence time.

4.4 ML: Token Sequences as Random Walks

A language model generates tokens sequentially. Conditional on the context, each token selection is a draw from a distribution - making the sequence $w_1, w_2, \ldots$ a stochastic process. The log-probability of a sequence:

$$\log P(w_1, \ldots, w_T) = \sum_{t=1}^T \log P(w_t | w_1, \ldots, w_{t-1})$$

is a sum of log-probabilities - a random walk in log-space. The perplexity $\text{PPL} = \exp(-\frac{1}{T}\sum_t \log P(w_t|\cdot))$ is the geometric mean of the inverse probabilities, and concentrates around $e^{H}$ where $H$ is the true entropy rate of the language.

Surprise accumulation: The cumulative surprise $-\log P(w_t | w_{<t})$ for a well-calibrated model is a martingale (under the true distribution). If the model is miscalibrated, the surprise process is either a submartingale (model too confident -> underestimates entropy) or supermartingale (model too diffuse). This connects language model calibration to martingale theory.

---

5. Poisson Processes

5.1 Definition and Characterisation

The Poisson process is the canonical continuous-time counting process - it counts the number of events in an interval.

Definition (Poisson Process). A right-continuous process $\{N(t)\}_{t \geq 0}$ with $N(0) = 0$ is a Poisson process with rate $\lambda > 0$ if:

1. Independent increments: For any $0 \leq t_0 < t_1 < \cdots < t_n$, the increments $N(t_1)-N(t_0), N(t_2)-N(t_1), \ldots$ are mutually independent
2. Stationary increments: $N(t+s) - N(s) \stackrel{d}{=} N(t) - N(0)$ for all $t, s \geq 0$
3. Poisson distribution of increments: $N(t) - N(s) \sim \text{Poisson}(\lambda(t-s))$ for $t > s$

Equivalent characterisation via inter-arrivals: If $T_1, T_2, \ldots$ are the inter-arrival times between successive events, then $\{N(t)\}$ is a Poisson process iff $T_1, T_2, \ldots \stackrel{iid}{\sim} \text{Exp}(\lambda)$.

The $\lambda \to 0$ limit: A Poisson process can be approximated by a Bernoulli process: divide $[0,T]$ into $n$ intervals of length $\delta = T/n$. Place an event in interval $k$ with probability $\lambda\delta$ independently. As $n \to \infty$ with $\lambda\delta n = \lambda T$ fixed, this converges to a Poisson process.

Martingale structure: $N(t) - \lambda t$ is a martingale (compensated Poisson process). Its quadratic variation is also $\lambda t$, so $(N(t)-\lambda t)^2 - \lambda t$ is also a martingale.

5.2 Properties: Superposition and Thinning

Superposition: If $N_1(t) \sim \text{Poisson}(\lambda_1)$ and $N_2(t) \sim \text{Poisson}(\lambda_2)$ are independent, then $N(t) = N_1(t) + N_2(t) \sim \text{Poisson}(\lambda_1 + \lambda_2)$. The superposition of $k$ independent Poisson processes is Poisson with rate $\sum_i \lambda_i$.

Thinning (Coloring): Start with a Poisson process $N(t) \sim \text{Poisson}(\lambda)$. Independently colour each arrival red with probability $p$ and blue with probability $1-p$. Then the red and blue counting processes are independent Poisson processes with rates $\lambda p$ and $\lambda(1-p)$.

Conditioning (uniform order statistics): Given $N(T) = n$, the arrival times $T_1 < T_2 < \cdots < T_n$ are distributed as the order statistics of $n$ iid Uniform$(0,T)$ random variables. This is the conditional uniformity property - conditioning on the count makes the arrival times maximally spread.

Non-homogeneous Poisson process: Generalise by allowing a time-varying rate $\lambda(t)$: $N(t) - N(s) \sim \text{Poisson}(\int_s^t \lambda(u)\,du)$ with independent increments. The compensator is $\Lambda(t) = \int_0^t \lambda(u)\,du$ (the integrated intensity).

5.3 Compound Poisson Process

Definition. Let $\{N(t)\}$ be a Poisson process with rate $\lambda$ and $\{Y_k\}$ iid random variables (independent of $N$). The compound Poisson process is:

$$X(t) = \sum_{k=1}^{N(t)} Y_k$$

Key moments:

• $\mathbb{E}[X(t)] = \lambda t \cdot \mathbb{E}[Y_1]$
• $\text{Var}(X(t)) = \lambda t \cdot \mathbb{E}[Y_1^2]$
• MGF: $M_{X(t)}(s) = \exp(\lambda t (M_{Y_1}(s) - 1))$

For AI: The total compute consumed by serving an LLM API follows a compound Poisson model: requests arrive as a Poisson process, and each request requires a random amount of compute (the "jump size" $Y_k$). Capacity planning uses compound Poisson theory to compute the required buffer size to handle peak demand with high probability.

5.4 ML: Event Streams and Token Timing

LLM inference event streams: In deployed LLMs, user requests arrive as a Poisson process with rate $\lambda$ (requests/second). Under heavy load, the inter-arrival distribution determines queueing behaviour. If token generation takes $\mu^{-1}$ seconds on average, the system is stable when $\lambda < \mu$ (arrival rate < service rate) - an M/M/1 queue analysis using Poisson process theory.

KV-cache access patterns: In multi-head attention with prefix caching, the pattern of cache hits/misses follows a complex point process. Poisson approximation applies when individual hit probabilities are small and requests are approximately independent.

Continuous batching: Modern LLM serving (vLLM, TensorRT-LLM) uses continuous batching: new requests join an existing batch as others complete. The batch size at time $t$ is a birth-death process - a continuous-time Markov chain with Poisson arrivals and Exponential service times.

---

6. Brownian Motion

6.1 Definition and Wiener's Axioms

Brownian motion (the Wiener process) is the fundamental continuous-time continuous-path stochastic process. It is simultaneously the limit of rescaled random walks (Donsker's theorem) and the building block for all diffusion processes in modern AI.

Definition (Standard Brownian Motion). A stochastic process $\{B_t\}_{t \geq 0}$ is a standard Brownian motion (or Wiener process) if:

1. $B_0 = 0$ a.s.
2. Independent increments: For $0 \leq t_0 < t_1 < \cdots < t_n$, the increments $B_{t_1}-B_{t_0}, B_{t_2}-B_{t_1}, \ldots$ are mutually independent
3. Gaussian increments: $B_t - B_s \sim \mathcal{N}(0, t-s)$ for all $0 \leq s < t$
4. Continuous paths: $t \mapsto B_t(\omega)$ is continuous a.s.

Existence: Wiener (1923) proved that such a process exists by constructing it on the space $C([0,\infty))$ of continuous functions with the Wiener measure. The construction uses Levy's Haar wavelet representation and is one of the foundational results of modern probability.

Finite-dimensional distributions: For $0 < t_1 < \cdots < t_n$, the joint density of $(B_{t_1}, \ldots, B_{t_n})$ is:

$$p(x_1, \ldots, x_n) = \prod_{k=1}^n \frac{1}{\sqrt{2\pi(t_k - t_{k-1})}} \exp\!\left(-\frac{(x_k - x_{k-1})^2}{2(t_k - t_{k-1})}\right)$$

with $t_0 = x_0 = 0$.

Martingale properties: The following are all martingales:

• $B_t$ (mean zero, no drift)
• $B_t^2 - t$ (variance process)
• $\exp(sB_t - s^2t/2)$ for any $s \in \mathbb{R}$ (exponential martingale / Doleans-Dade)

6.2 Key Properties and Quadratic Variation

Self-similarity: $\{cB_{t/c^2}\}_{t \geq 0} \stackrel{d}{=} \{B_t\}_{t \geq 0}$ for any $c > 0$. The process "looks the same" at any scale - it is fractal.

Time inversion: $\{tB_{1/t}\}_{t > 0} \stackrel{d}{=} \{B_t\}_{t > 0}$ (with $B_0 = 0$).

Non-differentiability: Brownian motion is a.s. nowhere differentiable. Formally: for almost every $\omega$, the function $t \mapsto B_t(\omega)$ is not differentiable at any point. This is why stochastic calculus requires the Ito integral - the standard Riemann-Stieltjes integral does not apply.

Quadratic variation: The key property distinguishing Brownian motion from ordinary functions is its quadratic variation:

$$[B]_t \coloneqq \lim_{|\mathcal{P}| \to 0} \sum_{k} (B_{t_k} - B_{t_{k-1}})^2 = t \quad \text{a.s.}$$

where the limit is over partitions $\mathcal{P} = \{0 = t_0 < t_1 < \cdots < t_n = t\}$ as the mesh $|\mathcal{P}| \to 0$. Informally: $(dB_t)^2 = dt$. This is the foundation of Ito's lemma and the $\sqrt{dt}$ scaling of stochastic noise.

The Levy characterisation: A continuous martingale $\{M_t\}$ with $M_0 = 0$ and quadratic variation $[M]_t = t$ is a standard Brownian motion. This characterises BM among all continuous martingales.

For AI: The quadratic variation formula $(dB_t)^2 = dt$ explains why diffusion model noise at timestep $t$ scales as $\sqrt{t}$, not $t$. In DDPM, the forward process adds noise $\epsilon \sim \mathcal{N}(0, I)$ scaled by $\sqrt{\bar{\alpha}_t}$, where $\bar{\alpha}_t = \prod_{s=1}^t (1-\beta_s)$ - a discretisation of BM's variance accumulation.

6.3 Brownian Motion as a Limit

Theorem (Donsker's Invariance Principle, 1951). Let $X_1, X_2, \ldots$ be iid with $\mathbb{E}[X_i] = 0$ and $\mathbb{E}[X_i^2] = \sigma^2 < \infty$. Define the continuous interpolation:

$$B_n(t) = \frac{1}{\sigma\sqrt{n}}\left(S_{\lfloor nt \rfloor} + (nt - \lfloor nt \rfloor) X_{\lfloor nt \rfloor + 1}\right), \quad t \in [0,1]$$

Then $B_n \Rightarrow B$ (convergence in distribution on $C([0,1])$ with the uniform topology), where $B$ is standard Brownian motion.

This is the functional central limit theorem - it upgrades the CLT from convergence of individual random variables to convergence of entire paths. The SRW path, rescaled by $1/\sqrt{n}$ in space and $1/n$ in time, converges to Brownian motion.

Implications: Any result proved for Brownian motion has a discrete-time analogue for random walks. This transfers insights between the continuous-time theory (SDEs, Ito calculus) and the discrete-time practice (mini-batch SGD, RL).

6.4 Geometric Brownian Motion

Definition. A process $\{S_t\}$ satisfies geometric Brownian motion if:

$$dS_t = \mu S_t \,dt + \sigma S_t \,dB_t, \quad S_0 = s_0 > 0$$

By Ito's lemma applied to $f(S) = \log S$:

$$d\log S_t = \left(\mu - \frac{\sigma^2}{2}\right)dt + \sigma\,dB_t$$ $$S_t = s_0 \exp\!\left(\left(\mu - \frac{\sigma^2}{2}\right)t + \sigma B_t\right)$$

So $S_t \sim \text{LogNormal}\!\left(\log s_0 + (\mu - \sigma^2/2)t,\, \sigma^2 t\right)$.

For AI: GBM models multiplicative noise, which appears in layer-normalisation dynamics. When a transformer residual stream is updated as $h_{t+1} = h_t + \Delta_t$ where $\Delta_t / \|h_t\| \sim \mathcal{N}(0, \sigma^2)$, the norm $\|h_t\|$ approximately follows GBM, explaining the norm growth observed in deep transformers without proper initialisation.

6.5 Ornstein-Uhlenbeck Process

The Ornstein-Uhlenbeck (OU) process is the unique stationary Gaussian Markov process - and the theoretical foundation for diffusion model forward processes.

Definition (OU SDE). The OU process satisfies:

$$dX_t = -\theta(X_t - \mu)\,dt + \sigma\,dB_t, \quad \theta > 0$$

The drift $-\theta(X_t - \mu)$ is a mean-reverting force pulling the process toward $\mu$.

Solution (via Ito's formula):

$$X_t = \mu + (X_0 - \mu)e^{-\theta t} + \sigma\int_0^t e^{-\theta(t-s)}\,dB_s$$

Distributions:

• $X_t | X_0 \sim \mathcal{N}\!\left(\mu + (X_0-\mu)e^{-\theta t},\ \frac{\sigma^2}{2\theta}(1 - e^{-2\theta t})\right)$
• Stationary distribution: $X_\infty \sim \mathcal{N}(\mu, \sigma^2/(2\theta))$
• Autocorrelation: $\text{Corr}(X_s, X_t) = e^{-\theta|t-s|}$ - exponential decay

For AI: The DDPM forward process is $q(x_t|x_0) = \mathcal{N}(\sqrt{\bar{\alpha}_t}x_0, (1-\bar{\alpha}_t)I)$, which matches the OU solution with $\theta = 1/2$, $\mu = 0$, $\sigma^2 = 1$ (after time reparametrisation). The variance-preserving SDE (VP-SDE) of Song et al. (2021) makes this correspondence exact:

$$dx = -\frac{1}{2}\beta(t)x\,dt + \sqrt{\beta(t)}\,dB_t$$

with $\bar{\alpha}_t = \exp(-\frac{1}{2}\int_0^t \beta(s)\,ds)$. The OU process provides the continuous-time foundation for all modern diffusion models.

L2 regularisation as OU: L2 regularisation in gradient descent adds a restoring force $-\lambda\theta$ to the update, giving a discrete-time OU process for the parameters. The stationary distribution concentrates around $\theta=0$ with variance $\propto \eta/\lambda$ (noise / regularisation), explaining why stronger L2 keeps parameters smaller.

6.6 ML: Diffusion Models

The forward process (data -> noise): Given clean data $x_0 \sim p_{\text{data}}$, DDPM defines:

$$q(x_t | x_{t-1}) = \mathcal{N}(x_t; \sqrt{1-\beta_t}x_{t-1}, \beta_t I), \quad t = 1,\ldots,T$$

The marginal is $q(x_t | x_0) = \mathcal{N}(\sqrt{\bar{\alpha}_t}x_0, (1-\bar{\alpha}_t)I)$ where $\bar{\alpha}_t = \prod_{s=1}^t(1-\beta_s)$. This forward process is a discretised OU process.

The reverse process (noise -> data): By Bayes' theorem and the Gaussian Markov property:

$$p_\theta(x_{t-1}|x_t) = \mathcal{N}(x_{t-1}; \mu_\theta(x_t, t), \Sigma_\theta(t))$$

The network learns to predict the score $\nabla_{x_t}\log q(x_t)$ (or equivalently, the noise $\epsilon$), enabling the reverse process to denoise step by step.

Score matching: The training objective minimises:

$$\mathcal{L} = \mathbb{E}_{t, x_0, \epsilon}\!\left[\|\epsilon - \epsilon_\theta(\sqrt{\bar{\alpha}_t}x_0 + \sqrt{1-\bar{\alpha}_t}\epsilon, t)\|^2\right]$$

This is equivalent to minimising Fisher divergence between $p_\theta$ and $q$, connecting to information-geometric stochastic process theory.

Continuous-time perspective (Score SDE, Song et al. 2021): The continuous limit is:

• Forward SDE: $dx = f(x,t)\,dt + g(t)\,dB_t$
• Reverse SDE: $dx = [f(x,t) - g(t)^2\nabla_x\log p_t(x)]\,dt + g(t)\,d\bar{B}_t$

The neural network approximates $\nabla_x\log p_t(x)$ - the score function - enabling the SDE to run backward from noise to data. This is the unified framework behind DDPM (discrete VP-SDE), DDIM (deterministic ODE), and Consistency Models.

---

7. Stationary Processes and Ergodicity

7.1 Strict and Wide-Sense Stationarity

Definition (Strict Stationarity). A stochastic process $\{X_t\}$ is strictly stationary if for any $n$, any times $t_1, \ldots, t_n$, and any shift $h$:

$$(X_{t_1+h}, \ldots, X_{t_n+h}) \stackrel{d}{=} (X_{t_1}, \ldots, X_{t_n})$$

The finite-dimensional distributions are invariant under time shifts.

Definition (Wide-Sense Stationarity, WSS). A process $\{X_t\}$ is wide-sense stationary (or second-order stationary) if:

1. $\mathbb{E}[X_t] = \mu$ (constant mean)
2. $\text{Cov}(X_t, X_s) = k(t-s)$ depends only on the lag $\tau = t-s$

Examples:

• Strictly stationary but not WSS: $t$-distributed noise with 1 DOF (undefined variance)
• WSS but not strictly stationary: $X_t = A\cos(\omega t) + B\sin(\omega t)$ with $A,B \sim \mathcal{N}(0,\sigma^2)$ iid - WSS with $k(\tau) = \sigma^2\cos(\omega\tau)$; not strictly stationary since $X_t$ is perfectly periodic with a random phase
• Both: Gaussian processes with stationary kernels; iid sequences

The autocovariance function $k(\tau)$ for a WSS process satisfies:

• Symmetry: $k(\tau) = k(-\tau)$ (real process)
• Positive semidefiniteness: $\sum_{i,j} a_i a_j k(t_i - t_j) \geq 0$ for all finite sequences

For AI: A WSS process is fully characterised by $\mu$ and $k(\tau)$ - enormously parsimonious compared to the general joint distribution. This is why WSS is the right model for relative position encodings in transformers.

7.2 Ergodicity and the Ergodic Theorem

Intuition: A process is ergodic if "time averages equal ensemble averages" - a single long trajectory captures the full statistical behaviour of the process.

Theorem (Birkhoff's Ergodic Theorem, 1931). For a stationary ergodic process $\{X_t\}$ with $\mathbb{E}[|X_0|] < \infty$:

$$\frac{1}{T}\int_0^T X_t\,dt \xrightarrow{a.s.} \mathbb{E}[X_0] \quad \text{as } T \to \infty$$

For discrete time: $\frac{1}{N}\sum_{n=0}^{N-1} X_n \xrightarrow{a.s.} \mathbb{E}[X_0]$.

What "ergodic" means formally: A stationary process is ergodic if the only time-invariant events have probability 0 or 1 (the $\sigma$-algebra of invariant events is trivial). Equivalently, correlations decay: $\frac{1}{N}\sum_{n=0}^{N-1}\text{Cov}(X_0, X_n) \to 0$.

Non-ergodic example: $X_t = Z$ for all $t$, where $Z \sim \mathcal{N}(0,1)$ is fixed once and for all. This is stationary (distribution constant) but not ergodic (time average $= Z \neq \mathbb{E}[Z] = 0$ for any realisation).

For AI: SGD convergence analysis assumes that the gradient noise process is ergodic - the time average of gradient variance equals the ensemble average. If the data distribution shifts during training (non-stationarity), this fails. Continual learning methods address the resulting catastrophic forgetting, which is fundamentally a violation of the stationarity assumption.

7.3 Autocorrelation and Power Spectral Density

Definition. The autocovariance function (ACVF) is $k(\tau) = \text{Cov}(X_t, X_{t+\tau})$. The autocorrelation function (ACF) is $\rho(\tau) = k(\tau)/k(0)$, normalised to $[-1,1]$.

Examples of ACFs:

• iid white noise: $k(\tau) = \sigma^2 \mathbf{1}[\tau=0]$
• AR(1) process ($X_t = \phi X_{t-1} + \epsilon_t$, $|\phi|<1$): $k(\tau) = \sigma^2\phi^{|\tau|}/(1-\phi^2)$ - geometric decay
• OU process: $k(\tau) = (\sigma^2/2\theta)e^{-\theta|\tau|}$ - continuous-time geometric decay
• Seasonal process: periodic ACF

Theorem (Wiener-Khinchin, 1934). For a WSS process with absolutely summable autocovariance:

$$S(\omega) = \sum_{\tau=-\infty}^\infty k(\tau)e^{-i\omega\tau} = \mathcal{F}[k](\omega)$$

The power spectral density (PSD) $S(\omega)$ is the Fourier transform of $k(\tau)$ and is non-negative: $S(\omega) \geq 0$ for all $\omega$.

Conversely, any non-negative integrable function $S(\omega)$ is the PSD of some WSS process (Bochner's theorem). PSD decomposes the variance of a process by frequency: low-frequency components explain slow variation, high-frequency components explain rapid fluctuation.

For AI: The attention mechanism computes $\text{softmax}(QK^\top/\sqrt{d_k})V$. For a stationary input sequence, $Q_i = W_Q x_i$ and $K_j = W_K x_j$, so the attention score between positions $i$ and $j$ depends (via the input autocorrelation) only on $|i-j|$ - the relative position. This is the stationarity condition that relative position encodings (ALiBi, T5 bias, RoPE) exploit.

7.4 Gaussian Processes

Definition. A stochastic process $\{f(t)\}_{t \in T}$ is a Gaussian process (GP) if every finite collection $(f(t_1), \ldots, f(t_n))$ is jointly Gaussian. A GP is fully specified by:

• Mean function: $m(t) = \mathbb{E}[f(t)]$
• Covariance kernel: $k(s,t) = \text{Cov}(f(s), f(t))$

Notation: $f \sim \mathcal{GP}(m, k)$.

The kernel determines everything: Properties of the GP sample paths are determined by $k$:

• Smoothness: Matern-$\nu$ kernel controls differentiability ($\nu$ times differentiable paths)
• Length scale: $k(s,t) = e^{-|s-t|^2/(2\ell^2)}$ (RBF/squared-exponential) has length scale $\ell$
• Periodicity: $k(s,t) = \sigma^2\cos(2\pi|s-t|/p)$ for periodic processes

Common kernels:

GP Posterior (Bayesian inference): Given observations $\mathbf{y} = f(\mathbf{t}) + \epsilon$, $\epsilon \sim \mathcal{N}(0, \sigma_n^2 I)$:

$$f_* | \mathbf{t}_*, \mathbf{t}, \mathbf{y} \sim \mathcal{N}(\mu_*, \Sigma_*)$$ $$\mu_* = m(\mathbf{t}_*) + k(\mathbf{t}_*, \mathbf{t})[k(\mathbf{t},\mathbf{t}) + \sigma_n^2 I]^{-1}(\mathbf{y} - m(\mathbf{t}))$$ $$\Sigma_* = k(\mathbf{t}_*, \mathbf{t}_*) - k(\mathbf{t}_*, \mathbf{t})[k(\mathbf{t},\mathbf{t}) + \sigma_n^2 I]^{-1}k(\mathbf{t}, \mathbf{t}_*)$$

This is exact Bayesian inference in $O(n^3)$ time (from the Cholesky decomposition of the $n \times n$ kernel matrix).

For AI: Bayesian optimisation for hyperparameter search uses a GP prior over the loss surface. The acquisition function (UCB, EI) determines where to evaluate next, and the GP posterior updates after each observation. This is the principled method for tuning LLM training hyperparameters ($\eta$, $\beta_1$, $\beta_2$, etc.) when each evaluation is expensive.

Neural tangent kernel (NTK): An infinite-width neural network at initialisation is a GP with kernel determined by the architecture. During gradient descent with small learning rate, the network stays approximately GP (lazy training regime). The NTK $\Theta(x,x') = \nabla_\theta f(x;\theta)^\top \nabla_\theta f(x';\theta)$ determines the learning dynamics via the Gram matrix $\Theta(X,X)$.

7.5 ML: RoPE and Stationarity in Attention

Wide-sense stationarity of attention: For a sequence of token embeddings $\{x_t\}$, the attention matrix $A_{ij} = \text{softmax}(\frac{q_i^\top k_j}{\sqrt{d}})$ can be made to depend only on the relative position $i-j$ if we choose position encoding appropriately. This is equivalent to making the $Q$-$K$ inner product a stationary kernel.

RoPE (Rotary Position Embedding, Su et al. 2022): RoPE encodes position $t$ by rotating the query and key vectors:

$$R_t\mathbf{q}, \quad R_t\mathbf{k}, \quad \text{where } R_t \text{ is a block-diagonal rotation matrix}$$

The inner product satisfies:

$$(R_m\mathbf{q})^\top(R_n\mathbf{k}) = \mathbf{q}^\top R_{m-n}^\top R_0 \mathbf{k} = \mathbf{q}^\top R_{n-m}\mathbf{k}$$

which depends only on $m-n$ - exactly the stationarity condition! RoPE makes attention score a stationary kernel in position, enabling efficient relative position encoding.

ALiBi and linear bias: ALiBi (Press et al., 2022) adds $-m|i-j|$ to each attention logit where $m$ is a per-head slope. The resulting attention scores are of the form $f(q_i, k_j) - m|i-j|$, where the $-m|i-j|$ term is a stationary (translation-invariant) bias. This enables extrapolation to longer sequences - a key advantage when the training distribution has stationarity structure.

---

8. Preview: Markov Chains

8.1 The Markov Property

A stochastic process $\{X_n\}$ satisfies the Markov property if:

$$P(X_{n+1} = j \mid X_0, X_1, \ldots, X_n) = P(X_{n+1} = j \mid X_n) \quad \forall n, j$$

The past is irrelevant - the present state $X_n$ is a sufficient statistic for the future. Markov chains are the simplest non-trivial stochastic processes with memory.

Markov chains fit within the stochastic process framework developed here:

• They are adapted to their natural filtration $\mathcal{F}_n = \sigma(X_0,\ldots,X_n)$
• The transition function $P(X_{n+1}=j|X_n=i) = P_{ij}$ defines a stochastic matrix
• Many Markov chains are martingale transforms: $f(X_n)$ is a martingale if $f$ is harmonic for the transition operator

8.2 Forward Reference

Full treatment: Section07 Markov Chains

That section covers: transition matrices, invariant/stationary distributions, detailed balance, recurrence/transience (Markov chain version), mixing times, spectral gap, Perron-Frobenius theorem, reversibility, MCMC (Metropolis-Hastings, Gibbs), and ML applications in language model generation, RL policy evaluation, and PageRank.

---

9. ML Deep Dive

9.1 SGD Trajectory as Stochastic Process

The parameter sequence $\{\theta_n\}_{n \geq 0}$ produced by SGD is a discrete-time stochastic process with values in $\mathbb{R}^p$. Understanding its properties as a process - not just its endpoint - reveals why deep learning generalises.

The update rule as a random dynamical system:

$$\theta_{n+1} = \theta_n - \eta_n \tilde{g}_n(\theta_n), \quad \tilde{g}_n(\theta) = \frac{1}{B}\sum_{i \in \mathcal{B}_n}\nabla\ell(\theta; z_i)$$

where $\mathcal{B}_n$ is a random mini-batch drawn at step $n$.

Key stochastic process properties:

• $\theta_n$ is adapted to $\mathcal{F}_n = \sigma(\mathcal{B}_1,\ldots,\mathcal{B}_n)$
• $\mathbb{E}[\tilde{g}_n(\theta_n) | \mathcal{F}_{n-1}] = \nabla L(\theta_n)$ - unbiasedness means the noise is a martingale difference
• $\tilde{g}_n - \nabla L(\theta_n)$ is a martingale difference sequence

The diffusion approximation (Mandt et al., 2017): Under small step size and local quadratic approximation $L(\theta) \approx \frac{1}{2}(\theta-\theta^*)^\top H (\theta-\theta^*)$, the SGD dynamics converge to:

$$d\theta = -H\theta\,dt + \sqrt{\eta \Sigma}\,dB_t$$

This is a multivariate OU process with mean-reversion matrix $H$ and noise $\sqrt{\eta\Sigma}$. The stationary distribution is:

$$\theta_\infty \sim \mathcal{N}\!\left(\theta^*,\ \frac{\eta}{2}\Sigma H^{-1}\right)$$

Lower learning rate $\eta$ -> smaller stationary variance -> SGD concentrates more tightly around $\theta^*$. The ratio $\eta/B$ determines the noise temperature.

Flat minima and generalisation: The stationary distribution of the SGD SDE concentrates in regions of small Hessian $H$ (flat minima). Fisher-Rao information connects $\Sigma$ to the curvature, and the entropy of the stationary distribution $\propto \log\det(H^{-1})$ is large for flat minima. This provides a stochastic process explanation for why SGD with large learning rates prefers flat minima that generalise well.

9.2 RL Value Functions as Martingales

In reinforcement learning, the agent at time $t$ is in state $s_t$, takes action $a_t$, receives reward $r_t$, and transitions to $s_{t+1}$. The discounted return is:

$$G_t = \sum_{k=0}^\infty \gamma^k r_{t+k}$$

The Bellman equation: Under a fixed policy $\pi$, the value function $V^\pi(s) = \mathbb{E}[G_t | s_t = s]$ satisfies:

$$V^\pi(s) = \mathbb{E}[r_t + \gamma V^\pi(s_{t+1}) | s_t = s]$$

Martingale characterisation: Define $Z_t = \sum_{k=0}^{t-1}\gamma^k r_k + \gamma^t V^\pi(s_t)$. Under the true $V^\pi$:

$$\mathbb{E}[Z_{t+1} | \mathcal{F}_t] = \mathbb{E}\!\left[\gamma^t r_t + \gamma^{t+1} V^\pi(s_{t+1}) + \sum_{k=0}^{t-1}\gamma^k r_k \,\Big|\, \mathcal{F}_t\right] = Z_t$$

So $\{Z_t\}$ is a martingale! The TD error $\delta_t = r_t + \gamma V^\pi(s_{t+1}) - V^\pi(s_t)$ is a martingale difference: $\mathbb{E}[\delta_t | \mathcal{F}_t] = 0$. TD-learning converges because it performs online martingale approximation - stochastic approximation theory guarantees convergence of martingale difference algorithms under Robbins-Monro conditions.

REINFORCE gradient: The policy gradient estimator $\hat{g} = G_t \nabla\log\pi_\theta(a_t|s_t)$ is an unbiased estimator of $\nabla J(\theta)$ - it is a martingale difference. The baseline $b(s_t)$ reduces variance without introducing bias: $\mathbb{E}[(G_t - b(s_t))\nabla\log\pi | s_t] = \nabla J - b(s_t)\cdot 0 = \nabla J$ since $\mathbb{E}[\nabla\log\pi|s_t] = 0$.

9.3 Attention over Sequences

Attention can be viewed as a stochastic process operating over the token sequence:

Token sequence as discrete-time process: $(w_1, w_2, \ldots, w_T)$ with embedding $x_t = \text{Embed}(w_t)$. The attention mechanism at layer $\ell$ computes:

$$h_t^{(\ell)} = \sum_{s=1}^T \alpha_{ts}^{(\ell)} v_s^{(\ell)}, \quad \alpha_{ts} = \text{softmax}\left(\frac{q_t^\top k_s}{\sqrt{d_k}}\right)$$

The hidden state $h_t^{(\ell)}$ is a weighted average of all positions - a generalisation of the conditional expectation $\mathbb{E}[V | \text{query} = q]$.

Causal attention as filtration: In autoregressive generation, causal masking ensures $h_t$ depends only on $h_1, \ldots, h_t$ - maintaining the adaptedness condition to the natural filtration of the sequence. Bidirectional attention (BERT) uses a "global" $\sigma$-algebra that is not filtered.

KV-cache as path memory: The key-value cache stores $\{k_s, v_s\}_{s \leq t}$ - the full path of the process up to position $t$. This is the computational realisation of the filtration $\mathcal{F}_t$: at each new token, the model has access to the complete history.

9.4 Diffusion Model Schedules

Different noise schedules in diffusion models correspond to different continuous-time SDEs:

The reverse SDE (Anderson, 1982) is:

$$dx = \left[f(x,t) - g(t)^2\nabla_x\log p_t(x)\right]dt + g(t)\,d\bar{B}_t$$

where $\bar{B}_t$ is a backward Brownian motion. The neural network $s_\theta(x,t) \approx \nabla_x\log p_t(x)$ is trained to estimate the score function, enabling the reverse process to convert noise into data.

Consistency Models (Song et al., 2023) learn to map any point on the reverse SDE trajectory directly to the final sample, bypassing the iterative nature of full diffusion. The key insight uses probability flow ODE theory - replacing the stochastic reverse SDE with a deterministic ODE that has the same marginals.

---

10. Common Mistakes

---

11. Exercises

Exercise 1 * - Martingale Verification Let $X_1, X_2, \ldots$ be iid with $\mathbb{E}[X_i] = 0$, $\text{Var}(X_i) = \sigma^2$. Define $S_n = \sum_{k=1}^n X_k$ and $V_n = S_n^2 - n\sigma^2$.

(a) Prove $\{S_n\}$ is a martingale with respect to its natural filtration. (b) Prove $\{V_n\}$ is a martingale. What does $\mathbb{E}[V_\tau] = \mathbb{E}[V_0]$ imply for a bounded stopping time $\tau$? (c) For $X_k \sim \text{Uniform}\{-1,+1\}$, verify (a) and (b) numerically with $n=100$ and $10^5$ simulations. Check $\mathbb{E}[S_n] \approx 0$ and $\mathbb{E}[V_n] \approx 0$. (d) Let $\tau = \min(n, 50)$ for a fixed $n=100$ simulation. Verify $\mathbb{E}[S_\tau] \approx 0$ and $\mathbb{E}[V_\tau] \approx 0$ empirically.

Exercise 2 * - Doob's OST: Gambler's Ruin A fair gambler starts with $k = 30$ dollars and plays until reaching $N = 100$ or going broke.

(a) Use OST applied to $S_n$ to derive $P(\text{win}) = k/N$. Compute numerically for $k=30$, $N=100$. (b) Use OST applied to $S_n^2 - n$ to derive $\mathbb{E}[\tau] = k(N-k)$. Compute for the given values. (c) Simulate $10^5$ games and verify both $P(\text{win})$ and $\mathbb{E}[\tau]$ empirically. (d) For a biased game with $p=0.6$, use the exponential martingale $M_n = ((1-p)/p)^{S_n}$ to derive $P(\text{win})$. Verify numerically.

Exercise 3 * - Poisson Process Properties Let $N(t) \sim \text{Poisson}(\lambda=2)$.

(a) Compute $P(N(3) \geq 5)$ exactly and via simulation ($10^5$ trials). (b) Show that $M(t) = N(t) - \lambda t$ is a martingale (verify $\mathbb{E}[M(t)] = 0$ and $\mathbb{E}[M(t)|N(s), s \leq r] = M(r)$ for $r < t$). (c) Thinning: Generate a Poisson process with rate $\lambda=5$. Thin independently with $p=0.4$. Verify the thinned process is Poisson($2$) by checking its inter-arrival distribution. (d) Superposition: Show that the superposition of $\text{Poisson}(1)$ and $\text{Poisson}(2)$ is $\text{Poisson}(3)$ empirically.

Exercise 4 ** - Doob Martingale and McDiarmid Let $f(x_1,\ldots,x_n) = \max_{1 \leq k \leq n} x_k$ on $[0,1]^n$ with $X_i \stackrel{iid}{\sim}\text{Uniform}[0,1]$.

(a) Show $f$ has bounded differences: $\sup |f(\ldots,x_k,\ldots) - f(\ldots,x_k',\ldots)| \leq 1$ for each $k$, so $c_k = 1$. (b) Construct the Doob martingale $M_k = \mathbb{E}[\max X | X_1,\ldots,X_k]$ and compute $M_0$ and $M_n$ analytically. (c) Apply Azuma's inequality to bound $P(f - \mathbb{E}[f] \geq t)$ and compare to McDiarmid's bound. (d) Verify both bounds numerically for $n=100$, $t=0.05$. Compute the empirical tail probability and compare to the bound.

Exercise 5 ** - Brownian Motion Properties Simulate $B_t$ on $[0,1]$ using $n=1000$ steps.

(a) Verify the increment distribution: check that $B_t - B_s \sim \mathcal{N}(0, t-s)$ holds for several $(s,t)$ pairs using KS test. (b) Verify quadratic variation: compute $QV_n = \sum_{k=1}^n (B_{k/n} - B_{(k-1)/n})^2$ for $n = 10, 100, 1000, 10000$ and show $QV_n \to 1$. (c) Verify non-differentiability heuristically: compute finite differences $\Delta B / \Delta t$ for $\Delta t = 10^{-1}, 10^{-2}, 10^{-3}$ and observe they grow as $1/\sqrt{\Delta t}$. (d) Simulate the OU process $dX = -X\,dt + \sqrt{2}\,dB_t$ with Euler-Maruyama. Verify the stationary distribution is $\mathcal{N}(0,1)$.

Exercise 6 ** - Gaussian Process Posterior Let $f \sim \mathcal{GP}(0, k_{\text{RBF}})$ with $k_{\text{RBF}}(x,x') = \exp(-|x-x'|^2/(2\ell^2))$, $\ell = 0.5$.

(a) Draw 5 sample paths from the GP prior on $[0,5]$ using the covariance matrix. (b) Given observations $y_i = f(x_i) + \epsilon_i$ at $x = \{0.5, 1.5, 2.5, 3.5\}$ with $\epsilon_i \sim \mathcal{N}(0, 0.01)$, compute the GP posterior mean and variance. (c) Plot the posterior mean $\pm 2$ standard deviations and verify that all observation points are covered. (d) Compare the posterior using RBF kernel vs Matern-1/2 kernel. Which has smoother interpolation? Which has faster uncertainty growth away from observations?

Exercise 7 *** - SGD as Diffusion Process Minimise $L(\theta) = \theta^2/2$ (quadratic, $H=1$, $\theta^* = 0$) using SGD with $\tilde{g}(\theta) = \theta + \epsilon$, $\epsilon \sim \mathcal{N}(0, \sigma^2)$.

(a) Show that the SGD iterates satisfy $\theta_{n+1} = (1-\eta)\theta_n - \eta\epsilon_n$. Find the stationary distribution of $\theta_n$. (b) Verify analytically that $\text{Var}(\theta_\infty) = \eta\sigma^2/(2-\eta) \approx \eta\sigma^2/2$ for small $\eta$. (c) Simulate for $\eta \in \{0.01, 0.1, 0.3\}$, $\sigma^2 = 1$, $n = 10000$ steps. Plot the stationary distribution and compare to the analytical prediction. (d) Verify the diffusion approximation: the continuous-time SDE $d\theta = -\theta\,dt + \sqrt{\eta}\sigma\,dB_t$ has stationary distribution $\mathcal{N}(0, \eta\sigma^2/2)$. Compare to part (b).

Exercise 8 *** - RL TD-Error as Martingale Consider a Markov reward process: states $\{1, 2, 3\}$, transition matrix $P = [[0.5,0.3,0.2],[0.4,0.4,0.2],[0.3,0.3,0.4]]$, rewards $r = [1, 2, 3]$, discount $\gamma = 0.9$.

(a) Compute the true value function $V = (I - \gamma P)^{-1}r$ exactly. (b) Implement TD(0) to estimate $V$: run $10^4$ episodes of length 50, update $V(s_t) \leftarrow V(s_t) + \alpha(r_t + \gamma V(s_{t+1}) - V(s_t))$ with $\alpha = 0.01$. Compare to exact $V$. (c) Verify the martingale property of the TD error: under the true $V^*$, the TD error $\delta_t = r_t + \gamma V^*(s_{t+1}) - V^*(s_t)$ has $\mathbb{E}[\delta_t | s_t] = 0$. Verify numerically. (d) Implement variance-reduced version using baseline $b(s) = \bar{r}$ (mean reward). Show this reduces the variance of the gradient estimate without introducing bias.

---

12. Why This Matters for AI (2026 Perspective)

---

13. Conceptual Bridge

Looking backward: This section builds directly on the static probability of Section01-Section05. Filtrations formalise conditional expectations (Section04) over time; the Doob martingale makes McDiarmid's inequality (Section05) a consequence of Azuma applied to a martingale; the Gaussian process is the stochastic-process version of the multivariate Gaussian (Section03). Every concept here has a static probability antecedent.

Looking forward: Stochastic processes enable the dynamic probability of Section07 and beyond. Markov chains (Section07) are stochastic processes satisfying the Markov property - the specialisation of the general framework to memoryless dynamics. Statistics (Section07-Statistics) uses time series models (AR, MA, ARIMA) which are stationary stochastic processes analysed via the autocorrelation and spectral density tools developed here. Optimisation (Section08) uses the SDE/martingale formalism to analyse SGD convergence and diffusion-based sampling.

The martingale as a unifying concept: The martingale is arguably the most powerful single concept in probability theory. It appears in: (a) concentration inequalities as the Doob/Azuma construction, (b) SGD as a near-martingale gradient process, (c) RL value functions as martingale transforms, (d) diffusion model reverse processes as time-reversed SDEs with martingale driving noise, (e) sequential hypothesis testing (SPRT) as a martingale stopping problem. Understanding martingales is understanding the probabilistic structure that makes machine learning algorithms work.

STOCHASTIC PROCESSES: POSITION IN CURRICULUM
========================================================================

  STATIC PROBABILITY (Section01-Section05)
  ---------------------------------------------
  Section01 Random Variables  ->  Section02 Distributions
  Section03 Joint Dist.       ->  Section04 Expectation/MGF
  Section05 Concentration     ->  Azuma = Doob + Azuma
  ---------------------------------------------
                | filtrations, martingales, paths
                v
  +---------------------------------------------+
  |  Section06 STOCHASTIC PROCESSES (THIS SECTION)    |
  |  -----------------------------------------  |
  |  Filtrations    Martingales   OST           |
  |  Random Walks   Poisson       BM/OU         |
  |  Stationarity   GPs           SGD/RL/Diff   |
  +---------------------------------------------+
                |
       +--------+--------+
       v                 v
  Section07 Markov Chains   Section07-Stat/05 Time Series
  (Markov property,   (AR/MA/ARIMA, spectral
  MCMC, PageRank,     analysis, forecasting,
  RL policy eval)     seasonal decomposition)
       |
       v
  Section08 Optimisation (SDE/martingale-based
  convergence of SGD, Langevin dynamics,
  diffusion-based sampling)

========================================================================

The AI synthesis: In 2026, the stochastic process framework permeates every major AI subfield. Diffusion models are explicit SDE constructions. RL convergence relies on martingale theory. LLM evaluation uses Hoeffding/CLT on sequences of i.i.d. samples (Poisson processes of test cases). Bayesian optimisation uses GP posteriors. Continual learning grapples with non-stationarity. The practitioner who understands stochastic processes sees the probabilistic skeleton underlying methods that otherwise appear unrelated.

---

This completes Section06 Stochastic Processes. The framework built here - filtrations, martingales, the canonical processes - is the common language of probability theory in motion.

<- Back to Chapter 6: Probability Theory | Next: Markov Chains ->

---

Appendix A: Stochastic Calculus Primer

A.1 The Ito Integral

Classical calculus integrates smooth functions. The Ito integral extends integration to Brownian motion, where the integrand is a stochastic process.

Why ordinary integrals fail: Define $\int_0^T B_t\,dB_t$ using Riemann sums. Two natural choices:

• Left-endpoint (Ito): $\sum_{k=0}^{n-1} B_{t_k}(B_{t_{k+1}} - B_{t_k})$
• Midpoint (Stratonovich): $\sum_{k=0}^{n-1} \frac{B_{t_k}+B_{t_{k+1}}}{2}(B_{t_{k+1}} - B_{t_k})$

These give different limits as $n \to \infty$! This is unique to stochastic integration - in classical calculus all Riemann sums give the same limit.

Computation:

$$\text{Ito: } \int_0^T B_t\,dB_t = \frac{B_T^2 - T}{2}$$ $$\text{Stratonovich: } \int_0^T B_t \circ dB_t = \frac{B_T^2}{2}$$

The Ito integral gives an extra $-T/2$ term from the quadratic variation $[B]_T = T$. This is the source of Ito's lemma.

The Ito integral is a martingale: For any adapted square-integrable integrand $H_t$:

$$M_T = \int_0^T H_t\,dB_t \quad \text{is a martingale}$$

with $\mathbb{E}[M_T^2] = \int_0^T \mathbb{E}[H_t^2]\,dt$ (Ito isometry).

A.2 Ito's Lemma

Theorem (Ito's Lemma). Let $X_t$ satisfy the SDE $dX_t = \mu_t\,dt + \sigma_t\,dB_t$. For any $C^2$ function $f$:

$$df(X_t) = f'(X_t)\,dX_t + \frac{1}{2}f''(X_t)\sigma_t^2\,dt$$ $$= \left(\mu_t f'(X_t) + \frac{\sigma_t^2}{2}f''(X_t)\right)dt + \sigma_t f'(X_t)\,dB_t$$

The extra term $\frac{1}{2}f''(X_t)\sigma_t^2\,dt$ (the Ito correction) arises from the quadratic variation $(dB_t)^2 = dt$. It has no classical analogue.

Example: GBM. $dS = \mu S\,dt + \sigma S\,dB$. Apply Ito to $f(S) = \log S$:

$$d\log S = \frac{1}{S}\mu S\,dt + \frac{1}{S}\sigma S\,dB - \frac{1}{2}\frac{1}{S^2}\sigma^2 S^2\,dt = \left(\mu - \frac{\sigma^2}{2}\right)dt + \sigma\,dB$$

The $-\sigma^2/2$ Ito correction converts the arithmetic drift $\mu$ to the geometric/log drift $\mu - \sigma^2/2$.

For AI: DDPM noise levels satisfy $d\bar\alpha_t \approx -\beta_t\bar\alpha_t\,dt$ (linear SDE for $\log\bar\alpha$). The Ito correction explains why the SNR $\bar\alpha_t/(1-\bar\alpha_t)$ does not decrease linearly even for linear schedules - the correction term shifts the effective noise profile.

A.3 Stochastic Differential Equations

General Ito SDE:

$$dX_t = b(X_t, t)\,dt + \sigma(X_t, t)\,dB_t, \quad X_0 = x_0$$

• $b(x,t)$: drift (deterministic tendency)
• $\sigma(x,t)$: diffusion coefficient (noise strength)

Existence and uniqueness (Lipschitz conditions): If $b$ and $\sigma$ are Lipschitz in $x$ uniformly in $t$ and have linear growth, the SDE has a unique strong solution (Picard-Lindelof for SDEs).

Important SDEs in ML:

Langevin dynamics and MCMC: The Langevin SDE $dX_t = -\nabla U(X_t)\,dt + \sqrt{2}\,dB_t$ has stationary distribution $\pi(x) \propto e^{-U(x)}$. This is the continuous-time version of Langevin MCMC, used for sampling from complex posteriors (e.g., Bayesian neural networks, energy-based models).

---

Appendix B: Convergence Theorems for Martingales

B.1 Martingale Convergence

Theorem (Doob's Martingale Convergence, 1953). If $\{M_n\}$ is a martingale and $\sup_n \mathbb{E}[|M_n|] < \infty$ ($L^1$ bounded), then $M_\infty = \lim_{n\to\infty} M_n$ exists a.s. and $\mathbb{E}[|M_\infty|] < \infty$.

This theorem is foundational for proving convergence of:

• Bayesian posterior updates (likelihood ratio martingales)
• Online learning algorithms (regret bounds via bounded martingales)
• Stochastic approximation algorithms (Robbins-Monro)

The $L^2$ version: If $\sup_n \mathbb{E}[M_n^2] < \infty$, then $M_n \to M_\infty$ both a.s. and in $L^2$.

B.2 Upcrossing Inequality

The proof of martingale convergence uses the upcrossing inequality: the number of times a martingale upcrosses an interval $[a,b]$ (goes from below $a$ to above $b$) satisfies:

$$\mathbb{E}[U_n[a,b]] \leq \frac{\mathbb{E}[(M_n - a)^+]}{b - a}$$

If $M_n$ is $L^1$ bounded, then $\mathbb{E}[U_\infty[a,b]] < \infty$, so upcrossings are finite for every rational interval $[a,b]$. This means oscillation in the limit is impossible, forcing convergence.

B.3 Uniform Integrability and $L^1$ Convergence

Definition. A family $\{M_t\}$ is uniformly integrable (UI) if:

$$\sup_t \mathbb{E}[|M_t|\mathbf{1}_{|M_t| > K}] \to 0 \quad \text{as } K \to \infty$$

UI is the condition needed for $\mathbb{E}[M_\infty] = \lim_n \mathbb{E}[M_n]$ (exchange of limit and expectation). Without UI, a.s. convergence does not imply $L^1$ convergence.

Sufficient condition for UI: $\sup_n \mathbb{E}[|M_n|^p] < \infty$ for any $p > 1$.

For AI: Uniform integrability is implicitly required for most SGD convergence proofs that need $\mathbb{E}[L(\theta_N)] \to L^*$ (expectation of limit = limit of expectations). When gradient clipping is used, it ensures the gradient process is UI, validating the convergence proofs.

---

Appendix C: Gaussian Process Details

C.1 Kernel Properties

A function $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ is a valid kernel (positive semidefinite / Mercer kernel) iff:

$$\sum_{i,j=1}^n c_i c_j k(x_i, x_j) \geq 0 \quad \forall n, x_1,\ldots,x_n \in \mathcal{X}, c_i \in \mathbb{R}$$

Operations preserving PSD kernels:

• Sum: $k_1 + k_2$ (sum of two valid kernels is valid)
• Product: $k_1 \cdot k_2$ (product of two valid kernels is valid)
• Scaling: $\alpha k$ for $\alpha > 0$
• Composition: $k(x,x') = k_1(\phi(x), \phi(x'))$ for any feature map $\phi$

Bochner's theorem (characterisation of stationary kernels): A continuous function $k(\tau)$ is the covariance of a stationary process iff:

$$k(\tau) = \int e^{i\omega\tau}\,dF(\omega)$$

for some non-decreasing bounded measure $F$ (the spectral measure). The PSD is $S(\omega) = dF/d\omega$.

C.2 Sparse GP Approximations

Exact GP inference costs $O(n^3)$ for $n$ training points. For large $n$ (e.g., $n = 10^5$), this is intractable. Sparse GP approximations use $m \ll n$ inducing points $\mathbf{u} = f(\mathbf{z})$:

$$p(f) \approx q(f) = \int p(f|\mathbf{u})q(\mathbf{u})\,d\mathbf{u}$$

The most common is the SVGP (Sparse Variational GP) which optimises a variational lower bound (ELBO), reducing cost to $O(nm^2 + m^3)$.

For AI: Sparse GPs enable scalable Bayesian optimisation for LLM hyperparameter tuning with $n > 1000$ evaluations. The inducing points act as a compressed representation of the observations, analogous to the key-value cache in attention.

C.3 Deep Kernel Learning

Neural-network kernels: Replace the input $x$ with a neural network representation $\phi_\theta(x)$ and use:

$$k_\theta(x,x') = k_{\text{base}}(\phi_\theta(x), \phi_\theta(x'))$$

This is deep kernel learning (DKL): train $\theta$ by maximising the GP marginal likelihood. DKL combines the flexibility of deep representations with the uncertainty quantification of GPs, and is used in scalable Bayesian optimisation for AutoML.

---

Appendix D: Extended ML Applications

D.1 Diffusion Models: Mathematical Details

The probability flow ODE for the VP-SDE is:

$$\frac{dx}{dt} = f(x,t) - \frac{1}{2}g(t)^2\nabla_x\log p_t(x)$$

This ODE has the same marginal distributions as the reverse SDE but is deterministic. It enables:

• DDIM sampling: Solve the ODE with large step sizes (fewer function evaluations)
• Latent space interpolation: Deterministic ODE gives unique encoding of each data point
• Consistency models: Learn direct $x_t \to x_0$ mapping that is consistent along ODE trajectories

The score function $s_\theta(x_t, t) \approx \nabla_{x_t}\log p_t(x_t)$ is the neural network that drives both the SDE and ODE. At optimum:

$$s_\theta^*(x_t, t) = \mathbb{E}\!\left[\frac{x_0 - \sqrt{\bar\alpha_t}x_t}{1-\bar\alpha_t}\,\Big|\,x_t\right] \cdot \frac{-1}{\sqrt{1-\bar\alpha_t}}$$

This is a conditional expectation - directly connecting score learning to the Doob martingale construction.

D.2 Online Learning and Martingale Regret Bounds

In online learning, at each round $t$ the learner predicts $\hat{y}_t$, suffers loss $\ell_t(\hat{y}_t)$, and observes true outcome $y_t$. The regret against best fixed action $a^*$ is:

$$\text{Regret}_T = \sum_{t=1}^T \ell_t(\hat{y}_t) - \min_{a}\sum_{t=1}^T \ell_t(a)$$

Martingale structure: In Follow-the-Regularised-Leader (FTRL) algorithms, the loss differences $\ell_t(\hat{y}_t) - \mathbb{E}[\ell_t(\hat{y}_t)|\mathcal{F}_{t-1}]$ form a martingale difference sequence. Applying Azuma's inequality:

$$P\!\left(\text{Regret}_T \geq \mathbb{E}[\text{Regret}_T] + t\sqrt{T}\right) \leq e^{-2t^2}$$

This gives high-probability regret bounds - the stochastic process framework converts expected regret into individual-run guarantees.

Bandit algorithms (Thompson Sampling): In multi-armed bandits with $K$ arms, at each round the agent samples parameters from the posterior and plays the arm with highest reward. The number of plays of suboptimal arms is bounded using stopping time arguments on the likelihood ratio martingale.

D.3 RLHF and Reward Models as Stochastic Processes

RLHF (Reinforcement Learning from Human Feedback) trains a language model $\pi_\theta$ to maximise a learned reward model $r_\phi(x,y)$ subject to a KL penalty:

$$\max_\pi \mathbb{E}_{x\sim\mathcal{D}, y\sim\pi}[r_\phi(x,y)] - \beta\text{KL}(\pi \| \pi_{\text{ref}})$$

This is a stochastic control problem: the policy $\pi$ is a controller, the generation trajectory $(y_1,\ldots,y_T)$ is the controlled stochastic process, and the reward $r_\phi(x, y_{1:T})$ is a terminal cost.

The RLHF policy update (PPO) as a martingale: The policy gradient estimator in PPO is:

$$\hat{g} = \mathbb{E}_t\!\left[\frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_\text{old}}(a_t|s_t)}A_t\right]$$

where $A_t$ is the advantage estimate. Under the true advantage function, $A_t = Q^\pi(s_t,a_t) - V^\pi(s_t)$ has $\mathbb{E}[A_t | s_t] = 0$ - it is a martingale difference. PPO clips the ratio to prevent large updates, maintaining stability of the martingale approximation.

D.4 Stochastic Processes in LLM Interpretability

Mechanistic interpretability (Elhage et al., Nanda et al.) studies circuits in transformer weights. The token sequence flowing through a transformer layers can be modelled as a stochastic process evolving through residual stream updates:

$$x_t^{(\ell+1)} = x_t^{(\ell)} + \text{Attn}^{(\ell)}(x_{1:t}^{(\ell)}) + \text{MLP}^{(\ell)}(x_t^{(\ell)})$$

Each residual update is a perturbation to the current state - the trajectory through layers is a discrete-time process indexed by layer depth $\ell$, not token position $t$. Understanding this process (what information is stored/retrieved at each layer) is the central question of interpretability.

Induction heads are attention heads that implement the operation "if A appeared before B at some position, predict B will appear after the current A." This is a pattern-matching stopping time: the head activates when it detects that the current context matches a past pattern. Formalising this as a stopping time over the layer-depth stochastic process is an active research direction.

---

Appendix E: The Functional CLT (Donsker's Theorem)

E.1 Weak Convergence on Function Spaces

Donsker's theorem states convergence in distribution on the function space $C([0,1])$ - the space of continuous functions equipped with the supremum norm $\|f\|_\infty = \sup_t |f(t)|$.

Theorem (Donsker, 1951). Let $X_1, X_2, \ldots$ be iid with $\mathbb{E}[X_i]=0$, $\sigma^2 = \mathbb{E}[X_i^2] < \infty$. Define:

$$W_n(t) = \frac{1}{\sigma\sqrt{n}}S_{\lfloor nt \rfloor}, \quad t \in [0,1]$$

Then $W_n \Rightarrow B$ weakly in $(C([0,1]), \|\cdot\|_\infty)$, where $B$ is standard Brownian motion.

Continuous mapping theorem: If $W_n \Rightarrow B$ and $g: C([0,1]) \to \mathbb{R}$ is continuous, then $g(W_n) \Rightarrow g(B)$. This gives:

• $\max_{0 \leq k \leq n} S_k / (\sigma\sqrt{n}) \Rightarrow \max_{0 \leq t \leq 1} B_t$ - reflection principle for random walks
• $n^{-1}\sum_{k=1}^n S_k^2 / \sigma^2 \Rightarrow \int_0^1 B_t^2\,dt$ - law of Brownian local time

E.2 Applications to SGD Analysis

Donsker's theorem justifies the SDE approximation of SGD: as step size $\eta \to 0$, the piecewise-constant SGD interpolation converges (in distribution, as a path) to the SDE $d\theta = -\nabla L\,dt + \sqrt{\eta\Sigma}\,dB$. This means:

• Convergence results for the SDE (e.g., mixing time to stationary distribution) translate to discrete-time SGD results
• The stationary distribution of SGD approximates $\mathcal{N}(\theta^*, \frac{\eta}{2}H^{-1}\Sigma)$ near a minimum $\theta^*$
• The escape rate from a local minimum scales as $\exp(-\Delta L / (\eta/B))$ - the Kramers escape rate formula

This is why practitioners observe that increasing batch size $B$ by factor $k$ requires proportionally increasing learning rate $\eta$ by $k$ to maintain the same noise temperature $\eta/B$ and thus the same optimisation dynamics.

---

Appendix F: Notation Summary

---

Appendix G: Worked Examples

G.1 Symmetric Random Walk: Hitting Probabilities

Problem. A particle starts at position $x = 3$ on the integer line. At each step it moves $+1$ or $-1$ with equal probability. Find: (a) The probability it hits 0 before hitting 10 (b) The expected number of steps to hit $\{0, 10\}$ (c) The probability it ever returns to 3 starting from 3

Solution.

(a) By the gambler's ruin result, $P(\text{hit 0 before 10}) = 1 - 3/10 = 7/10$.

(b) $\mathbb{E}[\tau] = k(N-k) = 3 \times 7 = 21$ steps.

(c) For a symmetric walk starting at $x=3$ on $\mathbb{Z}$, the probability of ever returning to 3 equals 1 (by Polya's theorem, $d=1$ recurrence). However, the expected return time is $\infty$ (the walk is null-recurrent).

Numerical verification:

import numpy as np
np.random.seed(42)
N_trials = 100_000

# (a) Gambler's ruin simulation
hits_zero = 0
for _ in range(N_trials):
    x = 3
    while 0 < x < 10:
        x += np.random.choice([-1, 1])
    hits_zero += (x == 0)
print(f"P(hit 0) \\approx {hits_zero/N_trials:.4f}, theory: 0.7000")  # -> 0.7000

# (b) Expected steps
total_steps = 0
for _ in range(N_trials):
    x, steps = 3, 0
    while 0 < x < 10:
        x += np.random.choice([-1, 1])
        steps += 1
    total_steps += steps
print(f"E[\\tau] \\approx {total_steps/N_trials:.2f}, theory: 21.00")  # -> 21.00

G.2 Poisson Process: Conditional Uniformity

Problem. Events arrive as a Poisson process with rate $\lambda$. Given that exactly 5 events occurred in $[0,3]$, what is the distribution of the first event time $T_1$?

Solution. By the conditional uniformity property, given $N(3) = 5$, the 5 event times are the order statistics of 5 iid Uniform$[0,3]$ random variables. Therefore $T_1 | N(3)=5 \sim \text{Beta}(1,5)$ scaled to $[0,3]$:

$$T_1 | N(3)=5 \sim \frac{3 \cdot \text{Beta}(1,5)}{1} = \frac{3}{6}\text{Uniform}[0,3] \text{ in distribution}$$

More precisely: $P(T_1 > t | N(3)=5) = (1-t/3)^5$ for $t \in [0,3]$.

Verification: Simulate 5 Uniform$[0,3]$ random variables, take the minimum. Compare to conditional Poisson process simulation.

G.3 Brownian Motion: The Arc-Sine Distribution

Problem. Let $L_1 = \sup\{t \in [0,1]: B_t = 0\}$ be the last zero of Brownian motion before time 1. Find $P(L_1 \leq t)$.

Solution. By Levy's arc-sine law:

$$P(L_1 \leq t) = \frac{2}{\pi}\arcsin(\sqrt{t})$$

This is the CDF of the arc-sine distribution on $[0,1]$. The density $p(t) = 1/(\pi\sqrt{t(1-t)})$ concentrates near 0 and 1 - the last zero before time 1 is most likely to be near 0 or near 1, and least likely to be near $1/2$. This violates the naive intuition that "the last zero should be somewhere in the middle."

Implication for AI: The arc-sine law suggests that in a long random walk (or SRW approximation of SGD noise), the trajectory spends most of its time on one side of zero - the noise process can have long "runs" of the same sign. This persistent structure in gradient noise is why momentum-based optimisers (Adam, SGD with momentum) perform better than pure SGD for certain problem structures.

G.4 OU Process: Analytical vs Numerical

Problem. Solve $dX = -2(X-1)\,dt + \sqrt{3}\,dB$, $X_0 = 5$.

Solution. This is OU with $\theta=2$, $\mu=1$, $\sigma=\sqrt{3}$.

• Solution: $X_t = 1 + (5-1)e^{-2t} + \sqrt{3}\int_0^t e^{-2(t-s)}\,dB_s$
• Mean: $\mathbb{E}[X_t] = 1 + 4e^{-2t}$
• Variance: $\text{Var}(X_t) = \frac{3}{4}(1 - e^{-4t})$
• Stationary distribution: $X_\infty \sim \mathcal{N}(1, 3/4)$

The process decays exponentially from $X_0=5$ toward the mean $\mu=1$ with decay rate $\theta=2$, while accumulating noise that saturates at $\sigma^2/(2\theta) = 3/4$.

For diffusion models: This corresponds to DDPM with $\beta_t = 4\Delta t$ (time-discretised) and the signal-to-noise ratio at time $T$ approaching $\mathbb{E}[X_T] = 1 + 4e^{-2T}$ for $T \to \infty$ - which is the "pure noise" terminal condition when $X_T \approx \mathcal{N}(1, 3/4)$.

G.5 Gaussian Process: Prior vs Posterior

Problem. Fit a GP to three observations $(x_1, y_1) = (0, 1)$, $(x_2, y_2) = (1, -0.5)$, $(x_3, y_3) = (2, 0.8)$ with RBF kernel $k(x,x') = e^{-(x-x')^2}$ and noise $\sigma_n^2 = 0.01$.

Solution. Build the $3 \times 3$ kernel matrix $K$:

$$K_{ij} = e^{-(x_i-x_j)^2} + 0.01\,\delta_{ij}$$

Posterior at test point $x_* = 1.5$:

• Compute $k_* = [k(x_*, x_1), k(x_*, x_2), k(x_*, x_3)]$
• $\mu_* = k_*^\top(K)^{-1}\mathbf{y}$
• $\sigma_*^2 = k(x_*,x_*) - k_*^\top K^{-1} k_*$

The posterior mean interpolates between the observations, and the posterior variance is small near observations (where the kernel provides strong correlation) and large away from them.

---

Appendix H: Self-Assessment Checklist

After completing this section, verify you can:

• State the definition of a stochastic process and give 3 examples of each combination of (discrete/continuous) x (time/state space)
• Define a filtration and explain what "adapted" means in ML context
• Verify the martingale property for a new process by computing $\mathbb{E}[M_{n+1}|\mathcal{F}_n]$
• State all three conditions of Doob's OST and identify which applies to a given problem
• Apply OST to compute expected stopping times and boundary hitting probabilities
• Construct the Doob martingale for a given function $f$ and derive McDiarmid from Azuma
• State the three defining properties of a Poisson process and derive the superposition/thinning results
• State Wiener's four axioms for Brownian motion and compute $P(B_t \geq a)$
• Compute the quadratic variation $[B]_T = T$ and state Ito's lemma
• Solve the OU SDE and state its stationary distribution
• Connect the DDPM forward process to the VP-SDE and OU process
• Define WSS and ergodicity, and state the Wiener-Khinchin theorem
• Specify a GP by its mean function and kernel, and compute the posterior given observations
• Explain why RoPE makes attention a stationary kernel in position
• Model SGD as a near-martingale and state the diffusion SDE approximation

---

Appendix I: Connections to Other Areas

I.1 Information Theory (Section09)

• The log-likelihood ratio process $\sum_k \log(p/q)(X_k)$ is a supermartingale under $Q$ and a submartingale under $P$
• The sequential probability ratio test (SPRT) is an optimal stopping time for hypothesis testing, derived using the likelihood ratio martingale
• Renyi entropy rates and the entropy rate $\bar{H} = \lim_n H(X_n|X_{n-1},\ldots,X_1)/1$ of a stationary process are central concepts at the intersection of stochastic processes and information theory

I.2 Functional Analysis (Section12)

• The space $C([0,1])$ of continuous functions is a Banach space; weak convergence on this space is Donsker's theorem
• Gaussian processes are infinite-dimensional Gaussian distributions on function spaces (Hilbert spaces)
• Reproducing Kernel Hilbert Spaces (RKHS): For each valid kernel $k$, there is a unique RKHS $\mathcal{H}_k$ with the reproducing property $f(x) = \langle f, k(\cdot,x)\rangle_{\mathcal{H}_k}$. GP regression in $\mathcal{H}_k$ is equivalent to minimising a regularised empirical risk in the RKHS

I.3 Optimisation (Section08)

• Stochastic approximation (Robbins-Monro, 1951): The original framework for SGD convergence uses martingale theory. Under step sizes $\sum_t \eta_t = \infty$, $\sum_t \eta_t^2 < \infty$ and bounded variance, the iterates converge a.s.
• Lyapunov methods: Proving convergence of SGD amounts to constructing a Lyapunov function $V(\theta)$ that is a (noisy) supermartingale, then applying martingale convergence
• Langevin MCMC: The Langevin SDE $d\theta = -\nabla U(\theta)\,dt + \sqrt{2}\,dB_t$ is used for posterior sampling in Bayesian DL, connecting optimisation and stochastic process theory

I.4 Statistics (Section07-Statistics)

• Time series analysis (ARIMA, state-space models) is the statistical estimation side of stochastic processes: given observed data $X_1,\ldots,X_n$, estimate the model parameters of an assumed process
• Spectral analysis uses the Wiener-Khinchin theorem to estimate the PSD from data via the periodogram
• Hypothesis testing for stationarity (Augmented Dickey-Fuller test, KPSS test) checks whether an observed time series is consistent with a stationary process

---

Appendix J: Advanced Topics

J.1 Levy Processes

A Levy process generalises both Brownian motion (continuous paths) and Poisson process (jumps) to arbitrary combinations of drift, diffusion, and jumps.

Levy-Khinchin representation: Every Levy process $X_t$ has characteristic function:

$$\mathbb{E}[e^{i\theta X_t}] = \exp\!\left(t\left[i\mu\theta - \frac{\sigma^2\theta^2}{2} + \int_{\mathbb{R}\setminus\{0\}} (e^{i\theta x} - 1 - i\theta x\mathbf{1}_{|x|<1})\,\nu(dx)\right]\right)$$

where $\mu \in \mathbb{R}$ (drift), $\sigma^2 \geq 0$ (diffusion), and $\nu$ is the Levy measure (jump intensity).

For AI: Heavy-tailed gradient distributions in neural network training are better modelled by Levy processes (with large jumps) than by Brownian motion (Gaussian, no jumps). The Levy stable distribution family includes the Gaussian (index $\alpha=2$) and Cauchy ($\alpha=1$) as special cases. Empirical studies of gradient statistics in transformers show heavy tails (Student-$t$ with low degrees of freedom), suggesting Levy process models may be more appropriate than the Gaussian SDE approximation.

J.2 Malliavin Calculus

Malliavin calculus is a variational calculus on Wiener space - it provides derivatives of random variables with respect to the underlying Brownian motion.

The Malliavin derivative $\mathcal{D}_s F$ measures the sensitivity of $F$ to the Brownian increment at time $s$. It satisfies:

$$\mathcal{D}_s F = \lim_{\varepsilon\to 0}\frac{F(B + \varepsilon\mathbf{1}_{[s,\infty)}) - F(B)}{\varepsilon}$$

Clark-Ocone formula: For $F \in L^2$ with $\mathbb{E}[F]=0$:

$$F = \int_0^T \mathbb{E}[\mathcal{D}_s F | \mathcal{F}_s]\,dB_s$$

This represents any square-integrable random variable as a stochastic integral - connecting Malliavin calculus to the martingale representation theorem.

For AI: Malliavin calculus provides pathwise gradients for diffusion models, enabling gradient computation through the stochastic sampling process. This is used in score-based generative model training with more stable gradient estimates than the standard score-matching loss.

J.3 Stochastic Control and HJB Equation

A stochastic control problem seeks to find a policy $u_t(\omega)$ (adapted to $\mathcal{F}_t$) minimising:

$$J(u) = \mathbb{E}\!\left[\int_0^T \mathcal{L}(X_t, u_t)\,dt + g(X_T)\right]$$

subject to $dX_t = b(X_t, u_t)\,dt + \sigma(X_t, u_t)\,dB_t$.

The Hamilton-Jacobi-Bellman (HJB) equation gives the optimal value function $V(x,t) = \inf_u J(u; x,t)$:

$$-\partial_t V = \min_u\!\left[\mathcal{L}(x,u) + b(x,u)^\top\nabla_x V + \frac{1}{2}\text{tr}(\sigma\sigma^\top \nabla^2_x V)\right]$$

For AI: RLHF can be formulated as a stochastic control problem where the LLM generates tokens sequentially (the SDE), the reward is the RLHF reward model (the cost), and the KL penalty is a regularisation term. The HJB equation characterises the optimal RLHF policy, and PPO approximately solves it using neural network approximations of $V$.

---

Appendix K: Python Recipes for Stochastic Processes

K.1 Simulating Stochastic Processes

import numpy as np
import matplotlib.pyplot as plt

np.random.seed(42)

# Simple Random Walk
def simulate_srw(n_steps, n_paths=5):
    steps = np.random.choice([-1, 1], size=(n_paths, n_steps))
    return np.hstack([np.zeros((n_paths,1)), steps.cumsum(axis=1)])

# Brownian Motion (via SRW limit)
def simulate_bm(T=1.0, n_steps=1000, n_paths=5):
    dt = T / n_steps
    increments = np.random.normal(0, np.sqrt(dt), (n_paths, n_steps))
    return np.hstack([np.zeros((n_paths,1)), increments.cumsum(axis=1)])

# Ornstein-Uhlenbeck (Euler-Maruyama)
def simulate_ou(theta=1.0, mu=0.0, sigma=1.0, T=10.0, n_steps=1000, n_paths=5):
    dt = T / n_steps
    X = np.zeros((n_paths, n_steps+1))
    X[:,0] = 2.0  # initial condition
    for t in range(n_steps):
        dB = np.random.normal(0, np.sqrt(dt), n_paths)
        X[:,t+1] = X[:,t] + theta*(mu - X[:,t])*dt + sigma*dB
    return X

# Poisson Process
def simulate_poisson(lam=1.0, T=10.0, n_paths=5):
    paths = []
    for _ in range(n_paths):
        t, events = 0, [0]
        while t < T:
            t += np.random.exponential(1/lam)
            events.append(min(t, T))
        paths.append(events)
    return paths

# Geometric Brownian Motion
def simulate_gbm(mu=0.1, sigma=0.3, S0=100.0, T=1.0, n_steps=252, n_paths=5):
    dt = T / n_steps
    log_S = np.zeros((n_paths, n_steps+1))
    log_S[:,0] = np.log(S0)
    for t in range(n_steps):
        log_S[:,t+1] = log_S[:,t] + (mu - sigma**2/2)*dt + sigma*np.random.normal(0, np.sqrt(dt), n_paths)
    return np.exp(log_S)

K.2 Gaussian Process Posterior

import numpy as np
from scipy.linalg import cho_factor, cho_solve

def rbf_kernel(X1, X2, length_scale=1.0, variance=1.0):
    """Squared-exponential (RBF) kernel."""
    dists = ((X1[:,None] - X2[None,:])**2).sum(-1)
    return variance * np.exp(-dists / (2 * length_scale**2))

def gp_posterior(X_train, y_train, X_test, kernel_fn, noise_var=1e-3):
    """Compute GP posterior mean and variance."""
    K_tt = kernel_fn(X_train, X_train) + noise_var * np.eye(len(X_train))
    K_ts = kernel_fn(X_train, X_test)
    K_ss = kernel_fn(X_test, X_test)

    # Solve K_tt @ alpha = y_train using Cholesky
    cho = cho_factor(K_tt)
    alpha = cho_solve(cho, y_train)
    v = cho_solve(cho, K_ts)

    mu_post = K_ts.T @ alpha
    var_post = np.diag(K_ss) - (K_ts * v).sum(0)
    return mu_post, np.sqrt(np.maximum(var_post, 0))

# Usage:
# X_train = np.array([0., 1., 2.])
# y_train = np.array([1., -0.5, 0.8])
# X_test = np.linspace(-0.5, 2.5, 100)
# mu, std = gp_posterior(X_train, y_train, X_test, rbf_kernel)

K.3 Martingale Verification

import numpy as np

def verify_martingale(process_fn, n_steps=100, n_paths=10000, tol=0.05):
    """
    Verify martingale property: E[M_{n+1} | M_n] \\approx M_n.
    process_fn: callable that generates (n_paths, n_steps+1) array.
    """
    paths = process_fn(n_steps, n_paths)
    # Check: mean at step n equals mean at step 0
    means = paths.mean(axis=0)
    assert np.allclose(means, means[0], atol=tol), f"Mean not constant: {means[:5]}"
    # Check: E[M_{n+1}^2] - E[M_n^2] = variance increment
    print(f"Mean at all steps: {means[0]:.4f} +/- {means.std():.4f} (should be ~0)")
    print(f"PASS: Martingale mean constant within tolerance {tol}")

def simulate_srw_paths(n_steps, n_paths):
    steps = np.random.choice([-1., 1.], size=(n_paths, n_steps))
    return np.hstack([np.zeros((n_paths,1)), steps.cumsum(axis=1)])

np.random.seed(42)
verify_martingale(simulate_srw_paths)

K.4 Diffusion Model Forward Process

import numpy as np

def ddpm_forward_process(x0, T=1000, beta_start=1e-4, beta_end=0.02):
    """
    DDPM forward process: q(x_t | x_0) = N(sqrt(alpha_bar_t)*x0, (1-alpha_bar_t)*I)
    Returns: {t: (x_t, alpha_bar_t)} for t = 0, 1, ..., T
    """
    betas = np.linspace(beta_start, beta_end, T)
    alphas = 1 - betas
    alpha_bars = np.cumprod(alphas)

    trajectory = {0: (x0, 1.0)}
    x0_arr = np.array(x0, dtype=float)

    for t in range(1, T+1):
        ab = alpha_bars[t-1]
        eps = np.random.randn(*x0_arr.shape)
        x_t = np.sqrt(ab) * x0_arr + np.sqrt(1 - ab) * eps
        trajectory[t] = (x_t, ab)
    return trajectory, alpha_bars

def snr(alpha_bar):
    """Signal-to-noise ratio: alpha_bar / (1 - alpha_bar)."""
    return alpha_bar / (1 - alpha_bar + 1e-9)

# Example:
# x0 = np.array([1.0, 0.0, -1.0])
# traj, alpha_bars = ddpm_forward_process(x0, T=1000)
# For t=500: SNR \\approx 1 (equal signal and noise)
# For t=1000: SNR \\approx 0 (pure noise)

K.5 DDPM Schedule Comparison

import numpy as np

def linear_schedule(T=1000, beta_start=1e-4, beta_end=0.02):
    return np.linspace(beta_start, beta_end, T)

def cosine_schedule(T=1000, s=0.008):
    t = np.arange(T+1) / T
    f = np.cos((t + s)/(1+s) * np.pi/2)**2
    alpha_bars = f / f[0]
    betas = 1 - alpha_bars[1:] / alpha_bars[:-1]
    return np.clip(betas, 0, 0.999)

T = 1000
betas_linear = linear_schedule(T)
betas_cosine = cosine_schedule(T)

ab_linear = np.cumprod(1 - betas_linear)
ab_cosine = np.cumprod(1 - betas_cosine)

print("Signal preserved at t=T/4, T/2, 3T/4, T:")
for name, ab in [("Linear", ab_linear), ("Cosine", ab_cosine)]:
    vals = [ab[T//4-1], ab[T//2-1], ab[3*T//4-1], ab[-1]]
    print(f"  {name}: {[f'{v:.4f}' for v in vals]}")
# Cosine schedule destroys signal more uniformly across timesteps

---

Appendix L: Theory Problems (Advanced)

L.1 Optional Stopping and Wald's Identity

Problem. Let $X_1, X_2, \ldots$ be iid with $\mathbb{E}[X_i] = \mu$ and $\mathbb{E}[X_i^2] = \sigma^2 + \mu^2$. Let $\tau$ be a stopping time with $\mathbb{E}[\tau] < \infty$. Prove Wald's Identity:

$$\mathbb{E}[S_\tau] = \mu \cdot \mathbb{E}[\tau], \quad \mathbb{E}[S_\tau^2] = \sigma^2\mathbb{E}[\tau] + \mu^2\mathbb{E}[\tau]^2$$

Hint: $S_n - n\mu$ is a martingale. Apply OST. For the second moment, use $(S_n - n\mu)^2 - n\sigma^2$.

L.2 The Optional Stopping Theorem: Necessary Conditions

Problem. Show that the condition $\mathbb{E}[\tau] < \infty$ alone does NOT suffice for OST. Construct a martingale $\{M_n\}$ and stopping time $\tau$ with $\mathbb{E}[\tau] < \infty$ but $\mathbb{E}[M_\tau] \neq \mathbb{E}[M_0]$.

Hint: Let $M_n =$ SRW and $\tau = \min(T, \text{hitting time of level } n)$ for appropriate $T$ depending on $n$...

L.3 Levy Characterisation of BM

Problem. Prove that if $\{M_t\}$ is a continuous local martingale starting at 0 with quadratic variation $[M]_t = t$, then $M_t$ is a standard Brownian motion.

Hint: Use the exponential martingale $e^{i\theta M_t + \theta^2 t/2}$ and show it is a martingale. Then compute the characteristic function of $(M_{t_1},\ldots,M_{t_n})$.

L.4 GP Posterior as Hilbert Space Projection

Problem. Show that the GP posterior mean $\mu_*(x) = k_*^\top K^{-1}\mathbf{y}$ is the orthogonal projection of $f$ onto the span of $\{k(\cdot, x_1),\ldots,k(\cdot, x_n)\}$ in the RKHS $\mathcal{H}_k$.

Hint: Use the reproducing property $f(x_i) = \langle f, k(\cdot,x_i)\rangle_{\mathcal{H}_k}$ to express the GP as a Hilbert space problem.

---

Appendix M: References and Further Reading

Textbooks

1. Karatzas & Shreve, Brownian Motion and Stochastic Calculus (1991) - The standard reference for rigorous continuous-time stochastic processes, Ito calculus, and SDEs. Graduate-level.

2. Durrett, Probability: Theory and Examples (5th ed., 2019) - Comprehensive coverage including martingales, stopping times, ergodic theory, Brownian motion. Excellent exercises.

3. Williams, Probability with Martingales (1991) - Elegant, concise introduction to martingale theory. The clearest proof of martingale convergence. Highly recommended.

4. Oksendal, Stochastic Differential Equations (7th ed., 2014) - Standard SDEs reference. Accessible treatment of Ito calculus and applications.

5. Rasmussen & Williams, Gaussian Processes for Machine Learning (2006) - The canonical GP reference. Available free online.

6. Doob, Stochastic Processes (1953) - The original monograph. Still valuable for historical context.

Papers for AI Connections

1. Song et al. (2021), Score-Based Generative Modeling through Stochastic Differential Equations - Score SDE framework unifying DDPM, SMLD.

2. Mandt, Hoffman & Blei (2017), Stochastic Gradient Descent as Approximate Bayesian Inference - SDE approximation of SGD.

3. Su et al. (2022), RoFormer: Enhanced Transformer with Rotary Position Embedding - RoPE as stationary kernel.

4. Ho, Jain & Abbeel (2020), Denoising Diffusion Probabilistic Models - DDPM.

5. Li et al. (2017), Stochastic Modified Equations and Adaptive Stochastic Gradient Algorithms - SDE theory for SGD.

6. Song et al. (2023), Consistency Models - Distillation of diffusion models via probability flow ODE.

7. Tropp (2015), An Introduction to Matrix Concentration Inequalities - Matrix Bernstein, extends scalar martingale results.

8. Williams (1997), Reinforcement Learning: An Introduction (Sutton & Barto) - RL value functions as martingales; Chapter 6 on TD-learning.

---

Appendix N: Extended Proofs

N.1 Proof of Doob's Maximal Inequality

Theorem. For a non-negative submartingale $\{M_k\}_{k=0}^n$ and $\lambda > 0$:

$$\lambda \cdot P\!\left(\max_{0 \leq k \leq n} M_k \geq \lambda\right) \leq \mathbb{E}[M_n]$$

Proof. Let $\tau = \min\{k : M_k \geq \lambda\}$ (first time the process crosses $\lambda$), with $\tau = n$ if no crossing occurs. Then $\tau$ is a stopping time (the crossing event is $\mathcal{F}_k$-measurable).

Decompose the expectation $\mathbb{E}[M_n]$:

$$\mathbb{E}[M_n] = \mathbb{E}[M_n \mathbf{1}_{\tau \leq n}] + \mathbb{E}[M_n \mathbf{1}_{\tau > n}]$$

For the first term: since $\{M_k\}$ is a submartingale, $\mathbb{E}[M_n | \mathcal{F}_\tau] \geq M_\tau \geq \lambda$ on $\{\tau \leq n\}$:

$$\mathbb{E}[M_n \mathbf{1}_{\tau \leq n}] = \mathbb{E}[\mathbb{E}[M_n|\mathcal{F}_\tau]\mathbf{1}_{\tau \leq n}] \geq \lambda \cdot P(\tau \leq n) = \lambda \cdot P\!\left(\max_k M_k \geq \lambda\right)$$

Since $\mathbb{E}[M_n \mathbf{1}_{\tau > n}] \geq 0$:

$$\mathbb{E}[M_n] \geq \lambda P\!\left(\max_k M_k \geq \lambda\right)$$

$\square$

Corollary. Applying to $\{|M_k|\}$ (non-negative submartingale since $f(x)=|x|$ is convex):

$$P\!\left(\max_{0 \leq k \leq n}|M_k| \geq \lambda\right) \leq \frac{\mathbb{E}[|M_n|]}{\lambda}$$

N.2 Proof of Azuma's Inequality

Theorem (Azuma-Hoeffding). Let $\{M_k\}_{k=0}^n$ be a martingale with $|M_k - M_{k-1}| \leq c_k$ a.s. Then:

$$P(M_n - M_0 \geq t) \leq \exp\!\left(\frac{-t^2}{2\sum_k c_k^2}\right)$$

Proof. Let $D_k = M_k - M_{k-1}$ be the martingale differences. Since $\mathbb{E}[D_k|\mathcal{F}_{k-1}] = 0$ and $|D_k| \leq c_k$, by Hoeffding's lemma:

$$\mathbb{E}[e^{sD_k}|\mathcal{F}_{k-1}] \leq e^{s^2c_k^2/2}$$

By the Markov inequality for $e^{s(M_n - M_0)}$ (for any $s > 0$):

$$P(M_n - M_0 \geq t) \leq e^{-st}\mathbb{E}[e^{s(M_n-M_0)}]$$

Factor the MGF using conditional independence:

$$\mathbb{E}[e^{s\sum_k D_k}] = \mathbb{E}\!\left[\prod_k e^{sD_k}\right] = \mathbb{E}\!\left[\prod_{k=1}^{n-1}e^{sD_k}\mathbb{E}[e^{sD_n}|\mathcal{F}_{n-1}]\right] \leq \mathbb{E}\!\left[\prod_{k=1}^{n-1}e^{sD_k}\right] \cdot e^{s^2c_n^2/2}$$

Iterating: $\mathbb{E}[e^{s(M_n-M_0)}] \leq e^{s^2\sum_k c_k^2/2}$.

Combining:

$$P(M_n - M_0 \geq t) \leq e^{-st + s^2\sum c_k^2/2}$$

Optimise over $s > 0$: set $s = t/\sum c_k^2$ to get:

$$P(M_n - M_0 \geq t) \leq \exp\!\left(\frac{-t^2}{2\sum c_k^2}\right)$$

$\square$

N.3 Proof of Polya's Theorem ($d=1$: Recurrence)

Theorem. The SRW on $\mathbb{Z}$ is recurrent.

Proof. It suffices to show the expected number of returns to 0 is infinite: $\sum_{n=1}^\infty P(S_{2n}=0) = \infty$.

By Stirling's approximation $\binom{2n}{n} \sim 4^n/\sqrt{\pi n}$:

$$P(S_{2n}=0) = \binom{2n}{n}4^{-n} \sim \frac{1}{\sqrt{\pi n}}$$

Therefore $\sum_{n=1}^\infty P(S_{2n}=0) \sim \sum_{n=1}^\infty \frac{1}{\sqrt{\pi n}} = \infty$.

By the second Borel-Cantelli lemma (the events $\{S_{2n}=0\}$ are independent since each depends on distinct steps): $P(\text{return to 0 infinitely often}) = 1$.

Note: In $d \geq 3$, $P(S_{2n}=0) \sim C_d/n^{d/2}$ by CLT in $\mathbb{R}^d$, and $\sum C_d/n^{d/2} < \infty$ for $d \geq 3$ (since $d/2 > 1$). By Borel-Cantelli (first lemma): returns occur finitely often, so the walk is transient. $\square$

N.4 Proof that the OU Process Has the Correct Stationary Distribution

Theorem. The stationary distribution of $dX = -\theta X\,dt + \sigma\,dB$ ($\mu=0$) is $\mathcal{N}(0, \sigma^2/(2\theta))$.

Proof via Fokker-Planck equation. The probability density $p(x,t)$ satisfies:

$$\partial_t p = -\partial_x((-\theta x)p) + \frac{\sigma^2}{2}\partial_x^2 p = \theta\partial_x(xp) + \frac{\sigma^2}{2}\partial_x^2 p$$

At stationarity $\partial_t p = 0$:

$$0 = \theta\partial_x(xp) + \frac{\sigma^2}{2}\partial_x^2 p$$ $$0 = \theta(p + x\partial_x p) + \frac{\sigma^2}{2}\partial_x^2 p$$

Try $p(x) = Z^{-1}\exp(-\theta x^2/\sigma^2)$:

$$\partial_x p = -\frac{2\theta x}{\sigma^2}p, \quad \partial_x^2 p = \left(-\frac{2\theta}{\sigma^2} + \frac{4\theta^2 x^2}{\sigma^4}\right)p$$

Substituting: $\theta(1 - 2\theta x^2/\sigma^2)p + \frac{\sigma^2}{2}(-2\theta/\sigma^2 + 4\theta^2x^2/\sigma^4)p = [\theta - 2\theta^2x^2/\sigma^2 - \theta + 2\theta^2x^2/\sigma^2]p = 0$ [ok]

The normalisation gives $p_\infty(x) = \mathcal{N}(0, \sigma^2/(2\theta))$. $\square$

---

Appendix O: Spectral Theory of Stochastic Processes

O.1 Spectral Representation

Every WSS process $\{X_t\}$ with absolutely integrable ACVF admits the spectral representation:

$$X_t = \int_{-\infty}^\infty e^{i\omega t}\,dZ(\omega)$$

where $Z(\omega)$ is an orthogonal increment process (the spectral process) satisfying $\mathbb{E}[dZ(\omega)\overline{dZ(\omega')}] = S(\omega)\delta(\omega-\omega')\,d\omega$.

This is the stochastic analogue of the Fourier transform: a stationary process decomposes into uncorrelated frequency components, each contributing variance $S(\omega)\,d\omega$ in the frequency band $[\omega, \omega+d\omega]$.

For AI: The power spectral density of a token sequence determines how information is distributed across "frequencies" (temporal scales). A language model with strong long-range dependencies (like GPT-4 modelling coherent long documents) will have a PSD with high power at low frequencies. Attention head specialisation can be viewed as learning frequency-selective filters - heads that attend to nearby tokens (high frequency) vs. distant tokens (low frequency).

O.2 Spectral Gap and Mixing

For a stationary Markov chain with transition operator $P$, the spectral gap $\gamma = 1 - |\lambda_2|$ (where $\lambda_2$ is the second-largest eigenvalue of $P$) determines the mixing time $t_{\text{mix}} \sim 1/\gamma$.

• Large spectral gap -> fast mixing -> samples become independent quickly
• Small spectral gap -> slow mixing -> long-range correlations persist

For transformers: The attention pattern at each layer can be viewed as a stochastic matrix $A \in \mathbb{R}^{T\times T}$ (for sequence length $T$). The spectral gap of $A$ determines how quickly information "mixes" across the sequence. Heads with nearly uniform attention (large spectral gap) aggregate globally; heads with peaked attention (small spectral gap) attend locally.

---

Appendix P: Decision Framework for Choosing Process Models

CHOOSE THE RIGHT STOCHASTIC PROCESS MODEL
========================================================================

  Is the system evolving over time?
  +-- No  -> Use static probability (Section01-Section05)
  +-- Yes ->
        Does the state space have a natural structure?
        +-- Countable (e.g., integer counts, categories)
        |   +-- Discrete time -> Markov chain (Section07)
        |   +-- Continuous time -> Poisson or birth-death process
        +-- Continuous (e.g., parameter vector, embedding)
            +-- Does it have independent increments?
            |   +-- Yes, with Gaussian increments -> Brownian motion
            |   +-- Yes, with jump structure -> Poisson / Levy
            |   +-- No, but stationary -> ARMA or OU process
            +-- Does it decrease toward an attractor?
            |   +-- Yes -> OU process or SDE with drift
            +-- Does it only depend on the current state?
                +-- Yes -> Markov process (continuous time)
                +-- No, depends on full history -> GP or ARIMA

========================================================================

  AI Application -> Recommended Model
  ---------------------------------------------------------------------
  SGD parameter trajectory     -> OU SDE (diffusion approx)
  Mini-batch gradient noise    -> Martingale difference sequence
  Diffusion model forward      -> VP-SDE (discrete OU)
  LLM token generation         -> Markov chain (Section07)
  Request arrivals             -> Poisson process
  Hyperparameter optimisation  -> Gaussian process (Bayesian opt)
  RL value function            -> Martingale transform
  Training loss trajectory     -> Supermartingale
  NTK / infinite-width NN      -> Gaussian process
  Residual stream updates      -> Additive noise SDE
  ---------------------------------------------------------------------

---

Appendix Q: Connections to Measure Theory

Q.1 Stochastic Processes as Measurable Functions

A stochastic process $\{X_t\}_{t \in T}$ on $(\Omega, \mathcal{F}, P)$ can be viewed as a measurable function from $\Omega$ to the path space $\mathbb{R}^T$. The probabilistic properties of the process are encoded in the pushforward measure $P \circ X^{-1}$ on $\mathbb{R}^T$.

For Brownian motion: The path space is $C([0,\infty))$ (continuous functions). The Wiener measure $W$ is the unique probability measure on $C([0,\infty))$ such that $B_t(\omega) = \omega(t)$ (coordinate process) satisfies the four BM axioms. Constructing $W$ rigorously is Wiener's 1923 achievement.

Q.2 The Radon-Nikodym Theorem and Change of Measure

If $P$ and $Q$ are probability measures on $(\Omega, \mathcal{F})$ with $Q \ll P$ (Q is absolutely continuous wrt P), then there exists the Radon-Nikodym derivative $dQ/dP = Z$ such that $Q(A) = \mathbb{E}^P[Z\mathbf{1}_A]$ for all $A$.

Girsanov's theorem: Under mild conditions, if $B_t$ is a BM under $P$ and $\theta_t$ is adapted, then:

$$\tilde{B}_t = B_t + \int_0^t \theta_s\,ds$$

is a BM under $Q$ where $dQ/dP = \exp(-\int_0^T \theta_t\,dB_t - \frac{1}{2}\int_0^T\theta_t^2\,dt)$ (the Girsanov kernel).

For diffusion models: Girsanov's theorem is the mathematical basis for the reverse diffusion process. The reverse SDE under the data distribution $P$ corresponds to a change of measure from the noise distribution $Q$ (standard BM), with the Radon-Nikodym derivative involving the score function $\nabla\log p_t$. This makes the score-matching objective the likelihood maximisation objective under the reverse measure.

---

Appendix R: Supplementary: Concentration and Martingales Revisited

R.1 The Azuma-McDiarmid Connection - Full Detail

In Section3.5 we introduced the Doob martingale construction as the proof of McDiarmid's inequality. Here we make the connection fully explicit.

Setup. Let $X_1, \ldots, X_n$ be independent random variables and $f: \mathcal{X}^n \to \mathbb{R}$ satisfy the bounded differences condition: for each $k$,

$$\sup_{x_1,\ldots,x_n, x_k'} |f(x_1,\ldots,x_k,\ldots,x_n) - f(x_1,\ldots,x_k',\ldots,x_n)| \leq c_k$$

Step 1: Doob martingale. Define $M_k = \mathbb{E}[f | X_1,\ldots,X_k]$ for $k=0,\ldots,n$. Then $M_0 = \mathbb{E}[f]$, $M_n = f$, and $\{M_k\}$ is a martingale.

Step 2: Bounded differences. The martingale difference $D_k = M_k - M_{k-1}$ satisfies $|D_k| \leq c_k$ a.s. because:

$$|M_k - M_{k-1}| = |\mathbb{E}[f|X_1,\ldots,X_k] - \mathbb{E}[f|X_1,\ldots,X_{k-1}]| \leq \sup_{x_k, x_k'} |\mathbb{E}[f(\ldots,x_k,\ldots) - f(\ldots,x_k',\ldots)|X_{1:k-1}]| \leq c_k$$

Step 3: Azuma. Apply Azuma's inequality (proved in SectionN.2) to the martingale $\{M_k\}$:

$$P(f - \mathbb{E}[f] \geq t) = P(M_n - M_0 \geq t) \leq \exp\!\left(\frac{-t^2}{2\sum c_k^2}\right)$$

This IS McDiarmid's inequality. The concentration inequality Section05 is a consequence of martingale theory.

R.2 The Freedman Inequality

Azuma's inequality uses only the almost-sure bound $|D_k| \leq c_k$. Freedman's inequality (1975) also uses conditional variances, giving a Bernstein-type improvement:

Theorem (Freedman, 1975). Let $\{M_n\}$ be a martingale with $|D_k| \leq M$ a.s. Define $W_n = \sum_{k=1}^n \mathbb{E}[D_k^2|\mathcal{F}_{k-1}]$ (total conditional variance). Then for $t, v > 0$:

$$P(M_n - M_0 \geq t, W_n \leq v) \leq \exp\!\left(\frac{-t^2/2}{v + Mt/3}\right)$$

This is a martingale version of Bernstein's inequality. The event $W_n \leq v$ restricts to "low variance" trajectories. Unconditionally:

$$P(M_n - M_0 \geq t) \leq \exp\!\left(\frac{-t^2/2}{V + Mt/3}\right) \text{ where } V = \sup_\omega W_n(\omega)$$

For AI: Freedman's inequality gives tighter bounds for SGD convergence when the gradient variance is small. In the low-variance early-training phase (when the model is near initialisation and gradients are large but consistent), Freedman gives $e^{-t^2/(2v)}$ bounds tighter than Azuma's $e^{-t^2/(2nM^2)}$.

---

Appendix S: Practice Problems (All Levels)

Level * (Computation)

S.1. Let $M_n = 2^{S_n}$ where $S_n$ is the SRW. For what value of $p$ in the biased walk ($P(+1)=p$) is $M_n = 2^{S_n}$ a martingale?

Answer: $\mathbb{E}[2^{S_{n+1}}|S_n] = 2^{S_n}(2p + (1-p)/2)$. Set equal to $2^{S_n}$: $2p + (1-p)/2 = 1$, so $p = 1/3$.

S.2. A Poisson process has rate $\lambda = 3$ (events per hour). Find $P(N(2) \geq 5)$ and the expected time to the 4th event.

Answer: $N(2) \sim \text{Poisson}(6)$, so $P(N(2)\geq 5) = 1 - \sum_{k=0}^4 e^{-6}6^k/k! \approx 0.715$. Time to 4th event: $T_4 \sim \text{Gamma}(4, 1/3)$, $\mathbb{E}[T_4] = 4/3$ hours.

S.3. For the OU process with $\theta=1$, $\mu=2$, $\sigma=\sqrt{2}$, $X_0=0$: compute $\mathbb{E}[X_3]$ and $\text{Var}(X_3)$.

Answer: $\mathbb{E}[X_3] = 2 + (0-2)e^{-3} = 2 - 2e^{-3} \approx 1.9$. $\text{Var}(X_3) = \frac{2}{2}(1-e^{-6}) = 1-e^{-6} \approx 0.9975$.

Level ** (Theory)

S.4. Show that for a martingale $\{M_n\}$, the sequence $M_n^2 - [M]_n$ is also a martingale, where $[M]_n = \sum_{k=1}^n \mathbb{E}[D_k^2|\mathcal{F}_{k-1}]$ is the predictable quadratic variation.

S.5. Prove that if $f$ is convex and $\{M_n\}$ is a martingale, then $\{f(M_n)\}$ is a submartingale (using Jensen's inequality).

S.6. For the compound Poisson process $X(t) = \sum_{k=1}^{N(t)} Y_k$ with $\lambda = 2$, $Y_k \sim \text{Exp}(3)$: compute the MGF $M_{X(t)}(s)$ and use it to find $\mathbb{E}[X(t)]$ and $\text{Var}(X(t))$.

Level *** (AI Applications)

S.7. (Diffusion model noise schedule design) You want a noise schedule $\beta_t$ for the DDPM forward process such that the SNR $\alpha_t/(1-\alpha_t)$ decreases linearly from $\text{SNR}_0 = 100$ to $\text{SNR}_T = 0.01$ over $T=1000$ steps. Derive the required $\beta_t$ and compare to the linear schedule.

S.8. (SGD stationary distribution) In a 2D quadratic loss $L(\theta) = \frac{1}{2}\theta^\top H\theta$ with $H = \text{diag}(1, 10)$, SGD with step $\eta$ and gradient noise $\Sigma = I$ has stationary distribution $\mathcal{N}(0, \frac{\eta}{2}H^{-1})$. Show that the ratio of the standard deviations in the two directions is $\sqrt{10}$, and interpret this for optimisation.

S.9. (Martingale in RLHF) In PPO with KL-regularised reward $r_\theta(s,a) = r_\phi(s,a) - \beta\log(\pi_\theta(a|s)/\pi_{\text{ref}}(a|s))$, show that the KL penalty term creates a non-martingale perturbation to the policy gradient estimator. Under what conditions on $\beta$ does the perturbation become negligible?

---

Appendix T: Theorem Index

---

Appendix U: Continuous-Time Martingales

U.1 Local Martingales

In continuous time, the natural generalisation of a martingale is a local martingale: a process $\{M_t\}$ such that there exist stopping times $\tau_n \uparrow \infty$ and each stopped process $M_{t \wedge \tau_n}$ is a martingale.

Every continuous local martingale with $M_0 = 0$ can be written as a time-changed Brownian motion (by the Dambis-Dubins-Schwarz theorem):

$$M_t = B_{[M]_t}$$

where $B$ is a standard BM and $[M]_t$ is the quadratic variation of $M$.

The Ito integral $\int_0^t H_s\,dB_s$ is a local martingale (and a true martingale when $\mathbb{E}[\int_0^T H_s^2\,ds] < \infty$).

U.2 The Martingale Representation Theorem

Theorem (Martingale Representation). Every square-integrable martingale $\{M_t\}$ adapted to the Brownian filtration can be written as:

$$M_t = M_0 + \int_0^t H_s\,dB_s$$

for some adapted process $H_s$ with $\mathbb{E}[\int_0^T H_s^2\,ds] < \infty$.

For AI: In score-based diffusion model training, the training loss can be expressed as an Ito integral against the Wiener process of the forward noise. The neural network effectively learns the integrand $H_s(x_s)$ that represents the reverse process. The martingale representation theorem guarantees that such a representation exists - it is the theoretical justification for why neural networks can learn to "undo" Brownian noise.

U.3 Feynman-Kac Formula

For the SDE $dX_t = b(X_t)\,dt + \sigma(X_t)\,dB_t$ and function $f$, the Feynman-Kac formula relates the SDE to a PDE:

$$u(x,t) = \mathbb{E}\!\left[f(X_T)\exp\!\left(-\int_t^T r(X_s)\,ds\right)\,\Big|\, X_t = x\right]$$

satisfies the PDE $-\partial_t u = b\partial_x u + \frac{\sigma^2}{2}\partial_{xx}u - ru$ with terminal condition $u(x,T) = f(x)$.

For AI: The score function in diffusion models satisfies a backward Kolmogorov equation (the PDE form of the reverse SDE). Feynman-Kac connects this PDE to the expectation form $\nabla\log p_t(x_t) = \mathbb{E}[\frac{x_0 - \sqrt{\bar\alpha_t}x_t}{1-\bar\alpha_t}|x_t]$, which is directly implemented by the neural denoiser.

---

Appendix V: Numerical Methods for SDEs

V.1 Euler-Maruyama Method

The simplest numerical scheme for $dX = b(X,t)\,dt + \sigma(X,t)\,dB_t$:

$$X_{n+1} = X_n + b(X_n, t_n)\Delta t + \sigma(X_n, t_n)\Delta B_n$$

where $\Delta B_n \sim \mathcal{N}(0, \Delta t)$.

Convergence: Euler-Maruyama has strong order 1/2 (pathwise error $\sim \sqrt{\Delta t}$) and weak order 1 (distributional error $\sim \Delta t$). Compare to Euler method for ODEs which has order 1 for pathwise error - the $\sqrt{\Delta t}$ order reflects the irregularity of BM.

V.2 Milstein Method

The Milstein method improves strong convergence to order 1 by adding an Ito correction:

$$X_{n+1} = X_n + b\Delta t + \sigma\Delta B_n + \frac{1}{2}\sigma\sigma'\left[(\Delta B_n)^2 - \Delta t\right]$$

The extra term $\frac{1}{2}\sigma\sigma'[(\Delta B_n)^2 - \Delta t]$ uses the Ito formula's second-order term. For scalar SDEs, Milstein achieves the same convergence order as the trapezoidal rule for ODEs.

V.3 DDPM as Euler-Maruyama

The DDPM update $x_t = \sqrt{1-\beta_t}x_{t-1} + \sqrt{\beta_t}\epsilon_t$ is exactly the Euler-Maruyama discretisation of the VP-SDE $dx = -\frac{1}{2}\beta(t)x\,dt + \sqrt{\beta(t)}\,dB_t$ with step size $\Delta t = 1/T$:

$$x_t = x_{t-1} - \frac{\beta_t}{2}x_{t-1} \cdot 1 + \sqrt{\beta_t}\epsilon_t = (1-\beta_t/2)x_{t-1} + \sqrt{\beta_t}\epsilon_t \approx \sqrt{1-\beta_t}x_{t-1} + \sqrt{\beta_t}\epsilon_t$$

where the approximation $\sqrt{1-\beta_t} \approx 1 - \beta_t/2$ holds for small $\beta_t$. DDIM corresponds to using an implicit (backward Euler) discretisation of the probability flow ODE, which allows larger step sizes.

---

Appendix W: Bridge Processes and Conditional Diffusions

W.1 Brownian Bridge

A Brownian bridge from $a$ to $b$ on $[0,T]$ is a Brownian motion conditioned to be at $b$ at time $T$:

$$X_t^{\text{BB}} = a + (b-a)\frac{t}{T} + B_t - \frac{t}{T}B_T$$

This is a Gaussian process with $\mathbb{E}[X_t] = a + (b-a)t/T$ and $\text{Cov}(X_s, X_t) = s(T-t)/T$ for $s \leq t$.

For AI: Stochastic interpolation (Albergo & Vanden-Eijnden, 2023) uses Brownian bridges to construct generative models that interpolate between data and noise along curved paths, rather than straight (linear interpolation) or OU (DDPM) paths. Flow matching (Lipman et al., 2022) uses deterministic bridges (straight-line paths) for efficient training.

W.2 Conditional Score Function

Given a forward process $q(x_t|x_0)$, the conditional score is:

$$\nabla_{x_t}\log q(x_t|x_0) = \frac{-(x_t - \sqrt{\bar\alpha_t}x_0)}{1-\bar\alpha_t} = \frac{-\epsilon}{\sqrt{1-\bar\alpha_t}}$$

where $\epsilon$ is the noise added in the forward process. The marginal score satisfies:

$$\nabla_{x_t}\log q(x_t) = \mathbb{E}\!\left[\nabla_{x_t}\log q(x_t|x_0)\,\big|\,x_t\right]$$

This is a conditional expectation - a Doob martingale evaluated at $t$! The diffusion model learns to estimate $\mathbb{E}[\epsilon|x_t]$, which by Tweedie's formula equals the MMSE denoiser. The entire diffusion model training objective is a stochastic process estimation problem formulated in martingale language.

---

End of Section06 Stochastic Processes.

<- Back to Chapter 6: Probability Theory | Next: Markov Chains ->

---

Appendix X: Glossary