Stochastic Processes: Appendix V: Numerical Methods for SDEs to Appendix X: Glossary

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

Term	Definition
Adapted process	Process $X_t$ that is $\mathcal{F}_t$ -measurable at each $t$
Autocorrelation function (ACF)	$\rho(\tau) = \text{Cov}(X_t, X_{t+\tau})/\text{Var}(X_t)$
Azuma's inequality	Concentration bound for martingales with bounded differences
Brownian motion	Continuous Gaussian process with independent stationary increments
Cadlag	Right-continuous with left limits (French acronym)
Compensated Poisson	$N(t) - \lambda t$ - a martingale
Doob martingale	$M_k = \mathbb{E}[f
Ergodic theorem	Time average $\to$ ensemble average a.s.
Filtration	Increasing family of $\sigma$ -algebras: $\mathcal{F}_s \subseteq \mathcal{F}_t$ for $s \leq t$
Gaussian process (GP)	Process where every finite marginal is jointly Gaussian
Ito integral	Stochastic integral $\int H_t\,dB_t$ adapted to BM filtration
Ito's lemma	Chain rule for BM: $df = f'dX + \frac{1}{2}f''(dX)^2$
Kernel	Positive semidefinite function $k(x,x')$ - covariance of GP
Local martingale	Stopped process $M_{t\wedge\tau_n}$ is a martingale for each $n$
Martingale	$\mathbb{E}[M_t
Martingale difference	$D_k = M_k - M_{k-1}$ with $\mathbb{E}[D_k
OU process	$dX = -\theta(X-\mu)\,dt + \sigma\,dB$ - mean-reverting Gaussian process
Optional Stopping Theorem	$\mathbb{E}[M_\tau] = \mathbb{E}[M_0]$ under appropriate conditions
Poisson process	Counting process with iid exponential inter-arrival times
Quadratic variation	$[B]_t = t$ for BM - central property of stochastic integration
Score function	$\nabla_x \log p_t(x)$ - gradient of log-density
Stationary process	Distribution invariant under time shifts
Stopping time	$\tau$ with $\{\tau \leq t\} \in \mathcal{F}_t$ - no look-ahead
Submartingale	$\mathbb{E}[M_t
Supermartingale	$\mathbb{E}[M_t
Thinning	Poisson process subsampled with prob $p$ is Poisson( $\lambda p$ )
Uniform integrability	$\sup_t\mathbb{E}[
VP-SDE	Variance-preserving SDE - DDPM forward process continuum
Wide-sense stationary	Constant mean + covariance depends only on lag
Wiener measure	Probability measure on $C([0,\infty))$ defining BM paths

Stochastic Processes: Part 3 - Appendix V Numerical Methods For Sdes To Appendix X Glossary

Stochastic Processes: Appendix V: Numerical Methods for SDEs to Appendix X: Glossary

Appendix V: Numerical Methods for SDEs

V.1 Euler-Maruyama Method

V.2 Milstein Method

V.3 DDPM as Euler-Maruyama

Appendix W: Bridge Processes and Conditional Diffusions

W.1 Brownian Bridge

W.2 Conditional Score Function

Appendix X: Glossary

Test this lesson

Which module does this lesson belong to?

Which section is covered in this lesson content?

Which term is most central to this lesson?

What is the best way to use this lesson for real learning?