翻译状态说明
本页为第 7 章的精校翻译，覆盖正文、Notes、Exercises 7.1-7.27、原书 Figure 7.1-7.5，并为原文明确证明、正文隐藏验证和习题加入学习笔记证明跳转。
第 7 章 随机过程
本章转向随机过程，即一族定义在同一概率空间上的随机变量 $(X_t)_{t\in T}$。这些随机变量可以彼此相关。在经典例子 Brownian motion 中，$t$ 表示时间，$T\subset\mathbb R$；但在高维概率中，$T$ 可以是抽象集合。最重要的例子是 canonical Gaussian process：
$$ X_t=\langle g,t\rangle,\qquad t\in T, $$
其中 $T\subset\mathbb R^n$，$g\sim N(0,I_n)$。
第 7.2 节介绍 Gaussian processes 的比较不等式：Slepian、Sudakov-Fernique 和 Gordon inequality。证明的新工具是 Gaussian interpolation。第 7.3 节用这些工具给出 Gaussian random matrices 的 sharp operator norm 界。
第 7.4 节用 covering numbers 给出 Gaussian width 的下界，也就是 Sudakov inequality。第 7.5 节系统解释 Gaussian width、spherical width、Gaussian complexity 与 effective dimension。第 7.6 节则说明任意有界集合在随机投影下的直径如何由 Gaussian width 决定。
7.1 基本概念与例子
随机过程就是一族随机变量 $(X_t)_{t\in T}$，它们定义在同一概率空间上，并由集合 $T$ 中的元素索引。
当 $T=\{1,\dots,n\}$ 时，随机过程就是随机向量 $(X_1,\dots,X_n)$。当 $T=\mathbb N$ 时，随机过程是一个随机变量序列。典型例子是 random walk：
$$ X_n=\sum_{i=1}^n Z_i, $$
其中 $Z_i$ 独立且均值为 $0$。
标准 Brownian motion $(X_t)_{t\ge0}$ 又称 Wiener process，可由两条性质刻画：样本路径几乎处处连续；并且对 $t\ge s$，增量独立且
$$ X_t-X_s\sim N(0,t-s). $$
当 $T\subset\mathbb R^n$ 时，随机过程也称为空间随机过程或随机场。
7.1.1 协方差与增量
为简化讨论，先假设 $\mathbb EX_t=0$。随机过程的协方差函数定义为
$$ \Sigma(t,s)=\operatorname{cov}(X_t,X_s)=\mathbb EX_tX_s. $$
过程的增量定义为
$$ d(t,s)=\|X_t-X_s\|_{L^2} =\bigl(\mathbb E(X_t-X_s)^2\bigr)^{1/2}. \tag{7.1} $$
Brownian motion 的增量满足 $d(t,s)=\sqrt{t-s}$，$t\ge s$。若 random walk 的增量满足 $\mathbb EZ_i^2=1$，则
$$ d(n,m)=\sqrt{n-m},\qquad n\ge m. $$
即使索引集合 $T$ 本身没有几何结构，增量 $d(t,s)$ 也会在 $T$ 上定义一个度量，从而自动把 $T$ 变成一个 metric space。不过这个度量未必等于 $T\subset\mathbb R^n$ 时的 Euclidean 距离。
协方差和增量携带的信息大致相同。展开平方得
$$ d(t,s)^2=\Sigma(t,t)-2\Sigma(t,s)+\Sigma(s,s). $$
如果过程包含零随机变量，则也可以由增量恢复协方差，见 Exercise 7.1。
7.1.2 Gaussian processes
随机过程 $(X_t)_{t\in T}$ 称为 Gaussian process，如果任意有限子集 $T_0\subset T$ 上的随机向量 $(X_t)_{t\in T_0}$ 都服从正态分布。等价地，任意有限线性组合 $\sum_{t\in T_0}a_tX_t$ 都是正态随机变量。
均值为 $0$ 的 Gaussian process 的分布由协方差函数决定；如果过程包含零随机变量，也可由增量决定。
设 $(X_t)_{t\in T}$ 是 Gaussian process，且 $T$ 有限。那么
$$ \left\| \sup_{t\in T}X_t-\mathbb E\sup_{t\in T}X_t \right\|_{\psi_2} \le C\sup_{t\in T}\sqrt{\operatorname{Var}(X_t)}. $$ 查看学习笔记：Theorem 7.1.11 完整证明canonical Gaussian process 定义为
$$ X_t=\langle g,t\rangle,\qquad t\in T\subset\mathbb R^n,\quad g\sim N(0,I_n). \tag{7.2} $$
它的增量就是 Euclidean 距离：
$$ \|X_t-X_s\|_{L^2}=\|t-s\|_2. $$
查看学习笔记：canonical process 的增量计算
设 $X$ 是 $\mathbb R^n$ 中均值为 $0$ 的 Gaussian random vector。那么存在点 $t_1,\dots,t_n\in\mathbb R^n$，使得
$$ X\stackrel{d}{=}(\langle g,t_i\rangle)_{i=1}^n, \qquad g\sim N(0,I_n). $$ 查看学习笔记：Lemma 7.1.12 完整证明7.2 Slepian、Sudakov-Fernique 与 Gordon 不等式
很多应用需要控制随机过程的统一上界：
$$ \mathbb E\sup_{t\in T}X_t. $$
为避免可测性问题，本章把 $\mathbb E\sup_{t\in T}X_t$ 理解为所有有限子集 $T_0\subset T$ 上 $\mathbb E\max_{t\in T_0}X_t$ 的上确界。
设 $(X_t)_{t\in T}$ 与 $(Y_t)_{t\in T}$ 是两个均值为 $0$ 的 Gaussian processes。假设对所有 $t,s\in T$，
$$ \mathbb EX_t^2=\mathbb EY_t^2, \qquad \mathbb E(X_t-X_s)^2\le\mathbb E(Y_t-Y_s)^2. \tag{7.3} $$那么 $\sup_tX_t$ 被 $\sup_tY_t$ 随机支配：对任意 $\tau\in\mathbb R$，
$$ \mathbb P\{\sup_{t\in T}X_t\ge\tau\} \le \mathbb P\{\sup_{t\in T}Y_t\ge\tau\}. \tag{7.4} $$从而
$$ \mathbb E\sup_{t\in T}X_t \le \mathbb E\sup_{t\in T}Y_t. \tag{7.5} $$ 查看学习笔记：Slepian inequality 完整证明7.2.1 Gaussian interpolation
证明 Slepian inequality 的工具是 Gaussian interpolation。有限 $T$ 时，把 $X=(X_t)_{t\in T}$ 与 $Y=(Y_t)_{t\in T}$ 看成 $\mathbb R^n$ 中的 Gaussian random vectors，并可假设它们独立。
定义插值向量
$$ Z(u)=\sqrt u\,X+\sqrt{1-u}\,Y,\qquad u\in[0,1]. \tag{7.8} $$
其协方差矩阵满足
$$ \Sigma(Z(u))=u\Sigma(X)+(1-u)\Sigma(Y). $$
设 $X\sim N(0,1)$。对可微函数 $f:\mathbb R\to\mathbb R$，在期望存在时有
$$ \mathbb EXf(X)=\mathbb Ef'(X). $$ 查看学习笔记：Lemma 7.2.3 完整证明设 $X\sim N(0,\Sigma)$。对可微函数 $f:\mathbb R^n\to\mathbb R$，有
$$ \mathbb EX_i f(X) = \sum_{j=1}^n\Sigma_{ij}\mathbb E\frac{\partial f}{\partial x_j}(X), \qquad i=1,\dots,n. \tag{7.7} $$ 查看学习笔记：Lemma 7.2.4 完整证明设 $X\sim N(0,\Sigma^X)$、$Y\sim N(0,\Sigma^Y)$ 独立，并定义 $Z(u)$ 如 (7.8)。对二阶可微函数 $f:\mathbb R^n\to\mathbb R$，
$$ \frac{d}{du}\mathbb Ef(Z(u)) = \frac12 \sum_{i,j=1}^n (\Sigma^X_{ij}-\Sigma^Y_{ij}) \mathbb E \frac{\partial^2f}{\partial x_i\partial x_j}(Z(u)). \tag{7.9} $$ 查看学习笔记：Lemma 7.2.5 完整证明7.2.2 Slepian inequality 的证明
设 $X,Y$ 是 $\mathbb R^n$ 中均值为 $0$ 的 Gaussian random vectors，满足同方差和增量支配条件。若二阶可微函数 $f$ 满足对所有 $i\ne j$，
$$ \frac{\partial^2 f}{\partial x_i\partial x_j}\ge0, $$则 $\mathbb Ef(X)\ge\mathbb Ef(Y)$。
查看学习笔记：Lemma 7.2.6 完整证明为了证明 Slepian inequality，取一个二阶可微、非增的函数 $h:\mathbb R\to[0,1]$，它近似 $\mathbf 1_{(-\infty,\tau)}$。
令
$$ f(x)=h(x_1)\cdots h(x_n). $$
则 $f$ 近似 $\mathbf 1_{\{\max_i x_i<\tau\}}$。对 $i\ne j$，
$$ \frac{\partial^2 f}{\partial x_i\partial x_j} =h'(x_i)h'(x_j)\prod_{k\notin\{i,j\}}h(x_k)\ge0. $$
应用 Lemma 7.2.6 并取平滑近似极限，得到 Slepian inequality。期望结论由 integrated tail formula 推出。
7.2.3 Sudakov-Fernique 与 Gordon inequalities
设 $(X_t)_{t\in T}$ 与 $(Y_t)_{t\in T}$ 是均值为 $0$ 的 Gaussian processes。若对所有 $t,s\in T$，
$$ \mathbb E(X_t-X_s)^2\le\mathbb E(Y_t-Y_s)^2, $$则
$$ \mathbb E\sup_{t\in T}X_t \le \mathbb E\sup_{t\in T}Y_t. $$ 查看学习笔记：Theorem 7.2.8 完整证明证明使用 soft maximum
$$ f(x)=\frac1\beta\log\sum_{i=1}^n e^{\beta x_i}. \tag{7.12} $$
当 $\beta\to\infty$ 时，$f(x)\to\max_i x_i$。把它代入 Gaussian interpolation formula 后，导数非正，故 $\mathbb Ef(Z(u))$ 随 $u$ 下降。
设 $(X_{ut})_{u\in U,t\in T}$ 与 $(Y_{ut})_{u\in U,t\in T}$ 是在 $U\times T$ 上索引的两个均值为 $0$ 的 Gaussian processes。若对所有 $u,t,s$，
$$ \mathbb E(X_{ut}-X_{us})^2 \le \mathbb E(Y_{ut}-Y_{us})^2, $$并且对所有 $u\ne v$ 与所有 $t,s$，
$$ \mathbb E(X_{ut}-X_{vs})^2 \ge \mathbb E(Y_{ut}-Y_{vs})^2, $$则对任意 $\tau\ge0$，
$$ \mathbb P\left\{\inf_{u\in U}\sup_{t\in T}X_{ut}\ge\tau\right\} \le \mathbb P\left\{\inf_{u\in U}\sup_{t\in T}Y_{ut}\ge\tau\right\}, $$从而相应的期望也满足同向比较。
查看学习笔记：Gordon inequality 的证明入口7.3 应用：Gaussian matrices 的 sharp bounds
设 $A$ 是 $m\times n$ 矩阵，元素独立且服从 $N(0,1)$。那么
$$ \mathbb E\|A\|\le\sqrt m+\sqrt n. $$ 查看学习笔记：Theorem 7.3.1 完整证明证明把算子范数写成 Gaussian process 的上确界：
$$ \|A\|=\sup_{u\in S^{n-1},v\in S^{m-1}}\langle Au,v\rangle. $$
定义 $X_{uv}=\langle Au,v\rangle$，再与更简单的过程
$$ Y_{uv}=\langle g,u\rangle+\langle h,v\rangle $$
比较。Sudakov-Fernique 允许把 $\mathbb E\sup X_{uv}$ 控制为 $\mathbb E\sup Y_{uv}=\mathbb E\|g\|_2+\mathbb E\|h\|_2\le\sqrt n+\sqrt m$。
查看学习笔记：rank-one Frobenius 距离计算
在 Theorem 7.3.1 的假设下，对所有 $t\ge0$，
$$ \mathbb P\{\|A\|\ge\sqrt m+\sqrt n+t\} \le 2\exp(-ct^2). $$ 查看学习笔记：Corollary 7.3.2 完整证明查看学习笔记：为什么 $A\mapsto\|A\|$ 是 1-Lipschitz
7.4 Sudakov inequality
对一般均值为 $0$ 的 Gaussian process，canonical metric 为
$$ d(t,s)=\|X_t-X_s\|_{L^2}. \tag{7.13} $$
这个度量决定协方差，协方差又决定 Gaussian process 的分布。因此可以把概率问题转成 metric geometry 问题。
设 $(X_t)_{t\in T}$ 是均值为 $0$ 的 Gaussian process，$d$ 为其 canonical metric。那么对任意 $\varepsilon\ge0$，
$$ \mathbb E\sup_{t\in T}X_t \ge c\varepsilon\sqrt{\log\mathcal N(T,d,\varepsilon)}. $$ 查看学习笔记：Theorem 7.4.1 完整证明证明取 maximal $\varepsilon$-separated subset $\mathcal N$，并把 $X_t$ 限制到 $\mathcal N$。再与独立 Gaussian 过程
$$ Y_t=\frac{\varepsilon}{\sqrt2}g_t $$
比较。由于 $\mathcal N$ 中不同点距离至少 $\varepsilon$，Sudakov-Fernique 给出 $\mathbb E\sup X_t\ge\mathbb E\sup Y_t\gtrsim\varepsilon\sqrt{\log|\mathcal N|}$。
7.4.1 $\mathbb R^n$ 中 covering numbers 的应用
设 $T\subset\mathbb R^n$。对任意 $\varepsilon>0$，
$$ \mathbb E\sup_{t\in T}\langle g,t\rangle \ge c\varepsilon\sqrt{\log\mathcal N(T,\varepsilon)}. $$ 查看学习笔记：Corollary 7.4.2 完整证明设 $P\subset\mathbb R^n$ 是有 $N$ 个顶点的 polytope，且包含在 Euclidean 单位球中。那么对所有 $\varepsilon>0$，
$$ \mathcal N(P,\varepsilon)\le N^{C/\varepsilon^2}. $$ 查看学习笔记：Corollary 7.4.3 完整证明7.5 Gaussian width
集合 $T\subset\mathbb R^n$ 的 Gaussian width 定义为
$$ w(T)=\mathbb E\sup_{x\in T}\langle g,x\rangle, \qquad g\sim N(0,I_n). $$Gaussian width 具有有限性、正交不变性、凸包不变性、Minkowski 加法、对称化、直径比较和线性映射下的控制。特别地，
$$ w(T)=\frac12 w(T-T) = \frac12\mathbb E\sup_{x,y\in T}\langle g,x-y\rangle, $$且
$$ \frac1{\sqrt{2\pi}}\operatorname{diam}(T) \le w(T) \le \frac{\sqrt n}{2}\operatorname{diam}(T). $$ 查看学习笔记：Proposition 7.5.2 完整证明7.5.1 Width 的几何意义
Gaussian width 描述集合在随机方向上看起来有多宽。方向 $\theta\in S^{n-1}$ 上的宽度是包含 $T$ 的最窄 slab 的宽度，可写为
$$ \sup_{x,y\in T}\langle \theta,x-y\rangle. \tag{7.16} $$
集合 $T\subset\mathbb R^n$ 的 spherical width 定义为
$$ w_s(T)=\mathbb E\sup_{x\in T}\langle\theta,x\rangle, \qquad \theta\sim\operatorname{Unif}(S^{n-1}). $$Gaussian width 大约是 $\sqrt n$ 倍的 spherical width：
$$ \left(\sqrt n-\frac C{\sqrt n}\right)w_s(T) \le w(T) \le \sqrt n\,w_s(T). $$ 查看学习笔记：Lemma 7.5.5 完整证明7.5.2 例子
Euclidean ball 和 sphere 的 Gaussian width 为
$$ w(S^{n-1})=w(B_2^n)=\mathbb E\|g\|_2 =\sqrt n\pm \frac C{\sqrt n}. \tag{7.17} $$
Cube $B_\infty^n=[-1,1]^n$ 的 Gaussian width 为
$$ w(B_\infty^n)=\mathbb E\|g\|_1 =\sqrt{\frac2\pi}\,n. \tag{7.18} $$
Cross-polytope $B_1^n$ 的 Gaussian width 满足
$$ w(B_1^n)=\mathbb E\|g\|_\infty \asymp \sqrt{\log n}. \tag{7.19} $$
有限点集 $T$ 满足
$$ w(T)\le C\sqrt{\log|T|}\operatorname{diam}(T). $$
7.5.3 Gaussian complexity 与 effective dimension
Gaussian width 的两个近亲是
$$ \gamma(T)=\mathbb E\sup_{x\in T}|\langle g,x\rangle|, \qquad h(T)=\left(\mathbb E\sup_{x\in T}\langle g,x\rangle^2\right)^{1/2}. $$
对任意有界集合 $T\subset\mathbb R^n$：
(a) $\gamma(T-T)=2w(T)$。
(b) 对任意 $y\in T$，$h(T)\asymp\gamma(T)\asymp w(T)+\|y\|_2$。特别地，若 $0\in T$，则
$$ h(T)\asymp\gamma(T)\asymp w(T). $$ 查看学习笔记：Lemma 7.5.11 完整证明有界集合 $T\subset\mathbb R^n$ 的 effective dimension 定义为
$$ d(T)= \frac{h(T-T)^2}{\operatorname{diam}(T)^2} \asymp \frac{w(T)^2}{\operatorname{diam}(T)^2}. $$它总是被线性代数维数控制：
$$ d(T)\le \dim(T), $$
且当 $T$ 是某个子空间中的 Euclidean ball 时取等号。
7.6 应用：集合的随机投影
对有限集合，Johnson-Lindenstrauss lemma 说明，当 $m\gtrsim\log|T|$ 时，随机投影会把所有距离约缩小为 $\sqrt{m/n}$ 倍：
$$ \operatorname{diam}(PT)\approx \sqrt{\frac mn}\operatorname{diam}(T). \tag{7.20} $$
若 $T$ 过大或无限，这会失败。一般情况下，random projection 不能把集合缩得低于 spherical width。
设 $T\subset\mathbb R^n$ 有界，$P$ 是到随机 $m$ 维子空间 $E\sim\operatorname{Unif}(G_{n,m})$ 的正交投影。那么
$$ \mathbb E\operatorname{diam}(PT) \asymp w_s(T)+\sqrt{\frac mn}\operatorname{diam}(T). $$ 查看学习笔记：Theorem 7.6.1 完整证明上界证明先把随机子空间模型改写为固定 $E=\mathbb R^m$ 后随机旋转集合。令 $Q$ 为 Haar orthogonal matrix 的前 $m$ 行，则
$$ \operatorname{diam}(QT) = \sup_{x\in T-T}\|Qx\|_2. $$
取 $S^{m-1}$ 的 $1/2$-net $\mathcal N$，得到
$$ \operatorname{diam}(QT) \le 2\max_{z\in\mathcal N} \sup_{x\in T-T}\langle Q^{\mathsf T}z,x\rangle. \tag{7.22} $$
对固定 $z$，$Q^{\mathsf T}z$ 均匀分布在 $S^{n-1}$，上式中的期望是 $2w_s(T)$。再用球面集中和 union bound，得到上界。
查看学习笔记：为什么可归一化 $\operatorname{diam}(T)\le1$ 查看学习笔记：为什么 $Q^{\mathsf T}z$ 均匀分布在球面 查看学习笔记：球面函数的 Lipschitz 范数 查看学习笔记：由尾界推出期望界
Theorem 7.6.1 可以写成
$$ \operatorname{diam}(PT) \asymp \max\left[ w_s(T), \sqrt{\frac mn}\operatorname{diam}(T) \right]. $$两项相等时，$m\asymp d(T)$。因此，当 $m\ge d(T)$ 时，随机投影大致按 $\sqrt{m/n}$ 缩小；当 $m<d(T)$ 时，缩小停止，直径停在 spherical width 尺度。
7.7 Notes
Slepian inequality 源于 D. Slepian。Sudakov-Fernique inequality 归功于 V. N. Sudakov 和 X. Fernique。本章采用 Gaussian interpolation 和 smoothing argument 的证明路线。
Gaussian comparison inequalities 与随机矩阵理论之间的联系由 Szarek 等人注意到；第 7.3 节的应用来自 Gordon 型论证。Sudakov inequality 是用 metric entropy 控制 Gaussian process 的基本下界。Gaussian width 起源于 geometric functional analysis 和 asymptotic convex geometry，并在 signal processing 与 high-dimensional statistics 中成为核心量。
Effective dimension 有多个相关版本，例如 convex cones 的 statistical dimension。Theorem 7.6.1 关于随机投影直径的结果属于 Milman 的理论。Exercise 7.18 中的 nuclear norm 是 Schatten norms 的特例。
Exercises
这些题训练从 covariance/increments 到 random process symmetrization，再到 Rademacher contraction 的过程观点。
Exercise 7.1 Exercise 7.2 Exercise 7.3 Exercise 7.4这些题补完 canonical representation、Gaussian integration by parts、soft maximum 计算、Gaussian contraction 与 Gordon inequality。
Exercise 7.5 Exercise 7.6 Exercise 7.7 Exercise 7.8 Exercise 7.9这些题补齐 Gaussian matrix 范数证明中的 Frobenius 计算、GOE 范数、Gaussian vector norm、smallest singular value 与非紧集合 Sudakov 下界。
Exercise 7.10 Exercise 7.11 Exercise 7.12 Exercise 7.13 Exercise 7.14这些题系统计算 Gaussian width 的性质、$\ell^p$ balls、operator norm ball、Gaussian complexity、effective dimension、ellipsoids 和球面模型。
Exercise 7.15 Exercise 7.16 Exercise 7.17 Exercise 7.18 Exercise 7.19 Exercise 7.20 Exercise 7.21 Exercise 7.22 Exercise 7.23 Exercise 7.24这些题把 Theorem 7.6.1 推广到 Gaussian projections，补随机投影下界，并应用到 matrix sketching。
Exercise 7.25 Exercise 7.26 Exercise 7.27