Stochastic Dynamics

A random variable describes one uncertain quantity. A stochastic process $\{X_t\}_{t\geq0}$ describes a collection of random variables indexed by time. One realized sequence $x_0,x_1,\ldots$ is a sample path, while the distribution of $X_t$ describes all values the process could occupy at time $t$.

A random walk makes the idea concrete. Let $X_{t+1}=X_t+\epsilon_{t+1}$, where each increment is $+1$ with probability $0.6$ and $-1$ with probability $0.4$. The increments are random, but their mean and variance still let us summarize where many paths tend to go: $$\mathbb E[X_n]=X_0+n\mathbb E[\epsilon],\qquad \operatorname{Var}(X_n)=n\operatorname{Var}(\epsilon).$$

Time dependence matters because values from the same path are connected. Even when the increments are independent, $X_4$ contains the first four increments and $X_5$ contains those same four plus one more. Stochastic-process models describe both uncertainty at one time and the way uncertainty is carried forward.

A process has the Markov property when the current state contains the information needed to model the next state: $$P(X_{t+1}=j\mid X_t=i,X_{t-1},\ldots,X_0)=P(X_{t+1}=j\mid X_t=i).$$ This does not say the states are independent. It says the past influences the next step through the present state.

For a finite-state chain, $P_{ij}$ is the probability of moving from state $i$ to state $j$, so every row of $P$ sums to $1$. With row-vector distributions, one step is $p_{t+1}=p_tP$ and $n$ steps are $p_{t+n}=p_tP^n$. The identity $P^{m+n}=P^mP^n$ is the discrete Chapman-Kolmogorov relation.

A stationary distribution satisfies $\pi=\pi P$. Starting distributions converge to it only under suitable conditions such as irreducibility and aperiodicity. Unit 20 builds on this foundation by adding actions, rewards, and policies; Unit 19 keeps the transition process uncontrolled.

An ordinary differential equation fixes a path once its initial condition is known. A stochastic differential equation adds continuously arriving noise: $$dX_t=f(X_t,t)\,dt+g(X_t,t)\,dW_t.$$ The drift $f$ describes systematic motion, the diffusion coefficient $g$ controls noise strength, and a Brownian increment over a short interval satisfies $\Delta W\sim\mathcal N(0,\Delta t)$.

Euler-Maruyama turns the continuous equation into small numerical steps. Write $\Delta W_k=\sqrt{\Delta t}\,\epsilon_k$ with $\epsilon_k\sim\mathcal N(0,1)$, then use: $$X_{k+1}=X_k+f(X_k,t_k)\Delta t+g(X_k,t_k)\sqrt{\Delta t}\,\epsilon_k.$$ Smaller time steps usually improve the approximation but require more computation.

Drift can depend on the current state. For example, $dX_t=\theta(\mu-X_t)dt+\sigma dW_t$ pulls the process toward $\mu$ while noise keeps disturbing it. This is mean reversion. We will use the update rule directly rather than developing the proof machinery of Itô calculus.

A diffusion model defines a forward process that adds small amounts of Gaussian noise. If $\alpha_t=1-\beta_t$ and $\bar\alpha_t=\prod_{s=1}^t\alpha_s$, a noisy sample can be drawn directly from the clean input: $$x_t=\sqrt{\bar\alpha_t}x_0+\sqrt{1-\bar\alpha_t}\,\epsilon,\qquad \epsilon\sim\mathcal N(0,I).$$ As $\bar\alpha_t$ decreases, less of $x_0$ remains and the noise term becomes stronger.

The reverse process is learned. A common objective trains a neural network to predict the sampled noise: $$\mathcal L_{noise}=\mathbb E_{x_0,t,\epsilon}\left[\lVert\epsilon-\epsilon_\theta(x_t,t)\rVert_2^2\right].$$ Generation begins with noise and repeatedly applies learned denoising steps. Conventional sampling is iterative because each step depends on the current noisy state.

KL divergence also appears in the diffusion training derivation. At each step, it measures the gap between the forward process's tractable posterior and the learned reverse transition: $$D_{KL}\!\left(q(x_{t-1}\mid x_t,x_0)\,\|\,p_\theta(x_{t-1}\mid x_t)\right).$$ These KL terms form part of the variational bound used to train a DDPM. The noise-prediction loss above is the common simplified, reweighted form of that objective. Unit 12 introduced KL divergence; here it measures how closely a denoising step matches the reverse distribution we want.

A score is the gradient $\nabla_x\log p_t(x)$, pointing toward directions where the log density increases. Score-based models connect diffusion to SDEs, while Langevin sampling combines a score-guided move with fresh Gaussian noise: $$x_{k+1}=x_k+\frac{\eta}{2}\nabla_x\log p(x_k)+\sqrt{\eta}\,\xi_k.$$ Unit 21 compares diffusion with other generative-model families; this unit supplies the stochastic-process mechanics.

Monte Carlo methods replace a difficult expectation with an average over sampled values. For independent samples $x_1,\ldots,x_N\sim p(x)$: $$\mathbb E_p[h(X)]\approx\hat\mu_N=\frac{1}{N}\sum_{i=1}^N h(x_i).$$ The estimate changes from one sample set to another, but the law of large numbers makes it settle toward the true expectation as $N$ grows.

Estimate uncertainty with the sample variance $s_h^2=\frac{1}{N-1}\sum_i(h(x_i)-\hat\mu_N)^2$ and standard error $\operatorname{SE}(\hat\mu_N)=s_h/\sqrt N$. The typical error shrinks like $O(N^{-1/2})$, so reducing it by a factor of ten usually requires about one hundred times as many independent samples.

Sometimes we can evaluate a target density up to a constant but cannot draw independent samples from it. Markov Chain Monte Carlo constructs a chain whose stationary distribution is the target. Metropolis-Hastings proposes $x'$ from $q(x'\mid x)$ and accepts it with probability: $$a(x,x')=\min\left(1,\frac{p(x')q(x\mid x')}{p(x)q(x'\mid x)}\right).$$ For a symmetric proposal, the proposal terms cancel.

At each step, draw $u\sim\operatorname{Uniform}(0,1)$. Move to $x'$ when $u<a$; otherwise repeat the current state. The repeated values are not an error. They preserve the target distribution, although they also make neighboring samples correlated.

Discard an initial warm-up period, inspect trace plots, compare multiple chains, and examine autocorrelation or effective sample size. A chain that barely moves can have thousands of stored values but very little independent information. Thinning reduces storage and correlation between retained draws, but it does not repair poor mixing.