Stochastic Processes — A Guided Tour of Modern Statistics

Notes / Probability Theory and Stochastic Processes

1.4 Stochastic Processes

1.4.1 Markov Chains

Using SLLN, we can easily get the following results.

Example 1.43 (Catalan Number). Consider a simple symmetric random walk $(S_n)$ starting at $S_0=0$. Let $\tau _i = \inf \{n \geq 1: S_n = i\}$. We derive the number of paths of length $2n$ from $0$ to $0$ that stay $\geq 0$.

For $n+i$ even, the set $\{S_n = i\}\setminus \{\tau _i = n\} = \{\tau _i < n,\, S_n = i\}$ consists of paths that visited $i$ before time $n$. Splitting by $S_{n-1}$ and applying reflection at time $\tau _i$, the contributions from $S_{n-1}=i+1$ and $S_{n-1}=i-1$ are equal, giving \[ P(\tau _i < n,\, S_n = i) = P(S_{n-1} = i+1) = \frac {n-i}{n}\,P(S_n = i). \] Therefore \[ P(\tau _i = n) = \frac {i}{n}\,P(S_n = i). \] Set $i=1$ and $n=2k+1$. The event $\{\tau _1 = 2k+1\}$ forces $S_1,\ldots ,S_{2k}\leq 0$ with $S_{2k}=0$ (the last step is necessarily $+1$). The number of such paths of the first $2k$ steps is \[ \frac {1}{2k+1}\binom {2k+1}{k+1}. \] Reflecting $S\mapsto -S$ counts instead the paths from $0$ to $0$ of length $2k$ staying $\geq 0$. Simplifying: \[ \frac {1}{2k+1}\binom {2k+1}{k+1} = \frac {(2k)!}{(k+1)!\,k!} = \frac {1}{k+1}\binom {2k}{k} = C_k. \]

Another interesting topic is Continuous-Time Markov Chains. The continuous-time viewpoint is important in many problems, as it brings in the tools of ordinary differential equations.

Example 1.44 (Poisson Processes). A counting process $(X_t)_{t\ge 0}$ with $X_0=0$ is a Poisson process of rate $\lambda $ if it has independent, stationary increments and \[ \mathbb P\{X_{t+\Delta t} - X_t = 1\} = \lambda \Delta t + o(\Delta t), \qquad \mathbb P\{X_{t+\Delta t} - X_t \ge 2\} = o(\Delta t). \]

Approach 1 (binomial limit) Write $X_t = \sum _{j=1}^{n}(X_{jt/n}-X_{(j-1)t/n})$. For large $n$ the summands are independent $\mathrm {Bernoulli}(\lambda t/n)$, so \[ \mathbb P\{X_t=k\} = \lim _{n\to \infty }\binom {n}{k}\Bigl (\frac {\lambda t}{n}\Bigr )^{\!k}\Bigl (1-\frac {\lambda t}{n}\Bigr )^{\!n-k} = e^{-\lambda t}\frac {(\lambda t)^k}{k!}. \]

Approach 2 (ODE) Set $P_k(t)=\mathbb P\{X_t=k\}$. The defining conditions give \[ P_k'(t)=\lambda P_{k-1}(t)-\lambda P_k(t). \] Substituting $f_k(t)=e^{\lambda t}P_k(t)$ reduces this to $f_k'=\lambda f_{k-1}$, $f_k(0)=0$. Since $f_0\equiv 1$, induction yields $f_k(t)=(\lambda t)^k/k!$.

Approach 3 (interarrival times) Let $T_n$ be the time between the $(n{-}1)$th and $n$th arrival. The $T_i$ are i.i.d. and memoryless: $\mathbb P\{T_i\ge s+t\mid T_i\ge s\}=\mathbb P\{T_i\ge t\}$, so $T_i\sim \mathrm {Exp}(\lambda )$. (Match rates: $\mathbb E[Y_n]=n/\lambda $ should give $\approx \!\lambda t$ arrivals by time $t$; or directly, $\mathbb P\{T_1>t\}=\mathbb P\{X_t=0\}=e^{-\lambda t}$.) Then $Y_n=T_1+\cdots +T_n\sim \mathrm {Gamma}(n,\lambda )$, and \[ \mathbb P\{X_t=k\}=\mathbb P\{Y_k\le t < Y_{k+1}\}=\int _0^t \frac {\lambda ^k s^{k-1}}{(k{-}1)!}e^{-\lambda s}\cdot \lambda e^{-\lambda (t-s)}\,ds = e^{-\lambda t}\frac {(\lambda t)^k}{k!}. \]

1.4.2 Martingale

A useful result (which we also use for the proof of SLLN) is as follows.

1.4.3 Itô Calculus

Remark 1.51 (History of Brownian Motion). Einstein’s derivation (1905). Consider $n$ particles in a fluid. Assume:

1.: particles move independently;
2.: increments over non-overlapping time intervals are independent.

Let $\varphi (\Delta )$ be the symmetric density of displacement over a time interval $\tau $, with $\varphi (\Delta ) = \varphi (-\Delta )$.

Let $f(x,t)$ be the particle density. Then \[ f(x, t+\tau ) = \int _{-\infty }^{+\infty } f(x-\Delta , t)\,\varphi (\Delta )\,\mathrm {d}\Delta . \] Expand both sides: the left in $\tau $, the right in $\Delta $. By symmetry of $\varphi $, odd-order terms vanish. Keeping only leading terms and setting $D = \frac {1}{\tau }\int \frac {\Delta ^2}{2}\,\varphi (\Delta )\,\mathrm {d}\Delta $, we obtain \[ \frac {\partial f}{\partial t} = D\frac {\partial ^2 f}{\partial x^2}. \] With initial condition $f(x,0) = n\,\delta (x)$, the solution is \[ f(x,t) = \frac {n}{\sqrt {4\pi Dt}}\,e^{-\frac {x^2}{4Dt}}. \] The ratio $f(x,t)/n$ is precisely the density of a Brownian motion. In particular, the root-mean-square displacement scales as $\sqrt {2Dt} \sim \sqrt {t}$.

Definition 1.55 (Itô Integral). For a stochastic process $(\phi _t)_{t \geq 0}$ in $\mathscr {L}_T^2$, let $(\phi _t^{(n)})_{t \geq 0}$ be a sequence of predictable simple (step) processes approximating it with respect to $(\mathcal {F}_t)_{t \geq 0}$, satisfying \[ \|\phi ^{(n)} - \phi \|^2 = E \int _0^T \left |\phi _t^{(n)} - \phi _t\right |^2 \mathrm {d}t \to 0, \quad \text {as } n \to \infty . \] (At this point $\int _0^T \phi _t^{(n)} \, \mathrm {d}B_t$ is a Cauchy sequence in $L^2(\Omega )$.) Denote the limit of $\int _0^T \phi _t^{(n)} \, \mathrm {d}B_t$ in $L^2(\Omega )$ by $\int _0^T \phi _t \, \mathrm {d}B_t$, i.e., \[ \int _0^T \phi _t \, \mathrm {d}B_t := L^2(\Omega )\text {-}\lim _{n \to \infty } \int _0^T \phi _t^{(n)} \, \mathrm {d}B_t, \] which is called the Itô stochastic integral of $(\phi _t)_{0 \leq t \leq T}$ with respect to $(B_t)_{t \geq 0}$.

Proposition 1.57 (Properties of Stochastic Integrals). .

1.: If $\tau $ is an $(\mathcal {F}_t)_{t \geq 0}$-stopping time with $\tau \leq T$, then \[ \int _0^{\tau } \phi _t \, \mathrm {d}B_t = \int _0^{T} \phi _t \mathbf {1}_{(0,\tau ]}(t) \, \mathrm {d}B_t. \]
2.: $\left \{\xi _t \overset {\mathrm {def}}{=} \int _0^t \phi _s \, \mathrm {d}B_s\right \}$ is an $(\mathcal {F}_t)_{t \in [0,T]}$-martingale.
3.: $\left \{\eta _t \overset {\mathrm {def}}{=} \left (\int _0^t \phi _s \, \mathrm {d}B_s\right )^2 - \int _0^t \phi _s^2 \, \mathrm {d}s\right \}$ is an $(\mathcal {F}_t)_{t \in [0,T]}$-martingale, and \[ E\left [\left (\int _s^t \phi _u \, \mathrm {d}B_u\right )^2 \bigg | \mathcal {F}_s\right ] = E\left [\int _s^t \phi _u^2 \, \mathrm {d}u \bigg | \mathcal {F}_s\right ]. \]
4.: If $(\phi _t)_{t \in [0,T]}$ is a bounded adapted process with respect to $(\mathcal {F}_t)_{t \in [0,T]}$, i.e., $\forall t$, $|\phi _t| < M < \infty $, then \[ \left \{\zeta _t \overset {\mathrm {def}}{=} e^{\int _0^t \phi _s \, \mathrm {d}B_s - \frac {1}{2}\int _0^t \phi _s^2 \, \mathrm {d}s}\right \} \] is an $(\mathcal {F}_t)_{t \in [0,T]}$-martingale.

1.4.4 Stochastic Differential Equations

At last, we talk about Stochastic Differential Equations (SDE). Consider a general form: \[ \mathrm {d}\xi _t = \mathbf {b}(t, \xi _t) \, \mathrm {d}t + \Sigma (t, \xi _t) \, \mathrm {d}\mathbf {B}_t. \]

Theorem 1.60 (Feynman-Kac Formula). Let \begin{equation} \mathrm {d}\xi _t = \mathbf {b}(\xi _t) \, \mathrm {d}t + \Sigma (\xi _t) \, \mathrm {d}\mathbf {B}_t \end{equation} and denote $\mathcal {L} = \frac {1}{2}\sum _{i,j=1}^{n} a_{ij} \frac {\partial ^2}{\partial x_i \partial x_j} + \sum _{i=1}^{n} b_i(x) \frac {\partial }{\partial x_i}$, where $(a_{ij})_{i,j=1,\cdots ,n} = \Sigma \Sigma ^\top $. Let $f \in C_0^2(\mathbb {R}^n)$, $q(x) \in C(\mathbb {R}^n)$, and $q(x)$ be bounded below.

1.: Let $v(t, x) = E\left (f(\xi _t) \exp \left (-\int _0^t q(\xi _s) \, \mathrm {d}s\right ) \bigg | \xi _0 = x\right )$. Then \begin{equation} \begin {cases} \dfrac {\partial v}{\partial t} = \mathcal {L}v - qv & t > 0, \; x \in \mathbb {R}^n \\[6pt] v(0, x) = f(x) & x \in \mathbb {R}^n \end {cases}. \end{equation}
2.: If $w(t, x) \in C^{1,2}(\mathbb {R} \times \mathbb {R}^n)$ is bounded on $K \times \mathbb {R}^n$, $K \subset \mathbb {R}$, and $w$ is a solution to (4), then $w(t, x) = v(t, x)$.

Example 1.61 (Diffusion Model). Consider the forward OU process \[ \mathrm {d}x_t = -\tfrac {1}{2}x_t\,\mathrm {d}t + \mathrm {d}B_t, \quad x_0 \sim p_0. \] A direct computation gives $x_t | x_0 \sim N(\alpha _t x_0,\, \sigma _t^2 I)$ where $\alpha _t = e^{-t/2}$ and $\sigma _t^2 = 1 - e^{-t}$. As $t \to \infty $, the distribution $p_t$ converges exponentially to $N(0, I)$ — structure is destroyed and replaced by pure noise.

By the Fokker–Planck equation, the density $p(x,t)$ satisfies \[ \frac {\partial p}{\partial t} = \nabla \cdot \left (\tfrac {1}{2}x\, p\right ) + \tfrac {1}{2}\Delta p = \tfrac {1}{2}\nabla \cdot \left (x\, p + \nabla p\right ). \]

Reverse SDE. Anderson (1982) showed that for a general forward SDE $\mathrm {d}x_t = f(x,t)\,\mathrm {d}t + g(t)\,\mathrm {d}B_t$, a reverse process is given by \[ \mathrm {d}\tilde {x}_t = \left [f(\tilde {x}_t, t) - g^2(t)\,\nabla _x \log p(\tilde {x}_t, t)\right ]\mathrm {d}t + g(t)\,\mathrm {d}\bar {B}_t, \quad t: T \to 0, \] where $\bar {B}_t$ is a backward Brownian motion.

Proof. The forward SDE $\mathrm {d}x_t = f\,\mathrm {d}t + g\,\mathrm {d}B_t$ has Fokker–Planck equation \[ \frac {\partial p}{\partial t} = -\nabla \cdot (f\, p) + \tfrac {1}{2}g^2 \Delta p. \] Set $s = T - t$ and $q(x,s) = p(x, T-s)$. Since $\partial q / \partial s = -\partial p / \partial t$, the density $q$ must satisfy \[ \frac {\partial q}{\partial s} = \nabla \cdot (f\,p) - \tfrac {1}{2}g^2 \Delta p. \tag {$\star $} \] Now we verify that the proposed reverse SDE, with drift $h = -f + g^2 \nabla _x \log p$ and diffusion $g$, reproduces $(\star )$. Its Fokker–Planck equation in $s$ reads $\partial q / \partial s = -\nabla \cdot (h\,q) + \tfrac {1}{2}g^2 \Delta q$. Substituting $q = p$ and using $p\,\nabla \log p = \nabla p$: \begin{align*} -\nabla \cdot (h\,p) + \tfrac {1}{2}g^2 \Delta p &= \nabla \cdot (f\,p) - \underbrace {\nabla \cdot (g^2 \nabla p)}_{=\, g^2 \Delta p} + \tfrac {1}{2}g^2 \Delta p = \nabla \cdot (f\,p) - \tfrac {1}{2}g^2 \Delta p, \end{align*}

which matches $(\star )$. □

For our OU process, $f(x,t) = -x/2$ and $g = 1$, so the reverse SDE reads \[ \mathrm {d}\tilde {x}_t = \left [-\tfrac {1}{2}\tilde {x}_t - \nabla _x \log p(\tilde {x}_t, t)\right ]\mathrm {d}t + \mathrm {d}\bar {B}_t. \] If we knew the score function $\nabla _x \log p(x,t)$, we could simulate this backward from $\tilde {x}_T \sim N(0,I)$ and recover samples from $p_0$. The entire problem reduces to learning the score.

Denoising score matching We want to minimize $L_t(\theta ) = \mathbb {E}_{x \sim p_t}\left [\|s_\theta (x,t) - \nabla _x \log p(x,t)\|^2\right ]$, but $\nabla _x \log p(x,t)$ is unknown. The key trick is integration by parts. Expand the square and note that the cross term satisfies \[ \int \langle s_\theta ,\, \nabla _x p\rangle \,\mathrm {d}x = -\int (\nabla \cdot s_\theta )\, p\,\mathrm {d}x. \] Now use $p(x,t) = \int p_t(x|x_0)\,p_0(x_0)\,\mathrm {d}x_0$ and apply integration by parts again on the inner integral. After recombining, we get \[ L_t(\theta ) = \mathbb {E}_{x_0 \sim p_0}\,\mathbb {E}_{x_t | x_0}\left [\|s_\theta (x_t, t) - \nabla _{x_t} \log p_t(x_t | x_0)\|^2\right ] + C, \] where $C$ is independent of $\theta $. The crucial point: the intractable marginal score $\nabla \log p$ has been replaced by the conditional score $\nabla \log p_t(\cdot | x_0)$, which is explicitly computable. Since $x_t | x_0 \sim N(\alpha _t x_0,\, \sigma _t^2 I)$, we have $\nabla _{x_t} \log p_t(x_t|x_0) = -(x_t - \alpha _t x_0)/\sigma _t^2 = -\xi _t/\sigma _t$ where $x_t = \alpha _t x_0 + \sigma _t \xi _t$ and $\xi _t \sim N(0,I)$. The final training objective is therefore \[ \min _\theta \; \mathbb {E}_t\,\mathbb {E}_{x_0}\,\mathbb {E}_{\xi _t}\left [\left \|s_\theta (\alpha _t x_0 + \sigma _t \xi _t,\, t) - \frac {\xi _t}{\sigma _t}\right \|^2\right ], \] which only requires samples from $p_0$ and standard Gaussians.