证明思路

方差可以用任意中心点控制。Theorem 3.1.1 已经说明 $\|X\|_2$ 在 $\sqrt n$ 附近有次高斯尾部，因此只需把尾界积分成二阶矩。

完整证明

令 $Z=\|X\|_2$。因为 $\operatorname{Var}(Z)=\inf_a\mathbb E(Z-a)^2$，所以

$$ \operatorname{Var}(Z)\le \mathbb E(Z-\sqrt n)^2. $$

Theorem 3.1.1 给出

$$ \mathbb P\{|Z-\sqrt n|>t\}\le 2\exp(-ct^2/K^4) $$

在调整绝对常数后可用于积分尾公式。因此

$$ \mathbb E(Z-\sqrt n)^2 = \int_0^\infty 2t\,\mathbb P\{|Z-\sqrt n|>t\}\,dt \le C K^4. $$

于是 $\operatorname{Var}(\|X\|_2)\le CK^4$。

证明思路

先控制平方范数 $S=\|X\|_2^2$ 的方差。再用 $\sqrt{\cdot}$ 的 Lipschitz 型估计把 $S$ 的波动转成 $\|X\|_2$ 的波动。

完整证明

令 $S=\sum_iX_i^2$。由独立性和 $\mathbb EX_i^2=1$，

$$ \mathbb ES=n,\qquad \operatorname{Var}(S)=\sum_i\operatorname{Var}(X_i^2) \le \sum_i\mathbb EX_i^4 \le nK^4. $$

对 $s\ge0$ 有 $|\sqrt s-\sqrt n|\le |s-n|/\sqrt n$，因此

$$ \operatorname{Var}(\|X\|_2) \le \mathbb E(\|X\|_2-\sqrt n)^2 \le \frac{\mathbb E(S-n)^2}{n} \le K^4. $$

上界由 Jensen 不等式得到：

$$ \mathbb E\|X\|_2 \le (\mathbb E\|X\|_2^2)^{1/2} = \sqrt n. $$

又因为 $\mathbb E\|X\|_2^2=n$，

$$ n = \operatorname{Var}(\|X\|_2)+(\mathbb E\|X\|_2)^2 \le K^4+(\mathbb E\|X\|_2)^2. $$

若 $K^4>n$，则 $\sqrt n-K^4/\sqrt n<0$，下界平凡。下面设 $K^4\le n$。由上式得到

$$ \mathbb E\|X\|_2 \ge \sqrt{n-K^4} \ge \sqrt n-\frac{K^4}{\sqrt n}, $$

其中最后一步使用 $\sqrt n-\sqrt{n-a}\le a/\sqrt n$。

证明思路

把 $S=\|X\|_2^2$ 与 $Y=\|X\|_2$ 联系起来。用独立副本写方差：若 $S,S'$ 都落在 $n$ 附近，则 $\sqrt S-\sqrt{S'}$ 与 $(S-S')/\sqrt n$ 同阶；六阶矩只用来说明 $S$ 的尾部不会吞掉主要方差。

完整证明

设 $S=\sum_iX_i^2=\|X\|_2^2$，$Y=\|X\|_2$，并记

$$ T=S-n=\sum_i Z_i,\qquad Z_i=X_i^2-1. $$

由独立性和题设，

$$ \operatorname{Var}(S) = \operatorname{Var}(T) = \sum_i\operatorname{Var}(X_i^2) \ge n\alpha. $$

同时，$\mathbb E|Z_i|^3\le C_\beta$。例如由 $|x^2-1|^3\le C(|x|^6+1)$ 和 $\mathbb EX_i^6\le\beta$ 得到。Rosenthal 不等式给出

$$ \mathbb E|T|^3 \le C_\beta n^{3/2}. $$

令中心事件 $E=\{|T|\le n/2\}$。由 Markov 不等式，$\mathbb P(E^c)\le C_\beta n^{-3/2}$，且

$$ \mathbb E[T^2\mathbf 1_{E^c}] \le \frac{2}{n}\mathbb E|T|^3 \le C_\beta\sqrt n. $$

取 $T'$ 为 $T$ 的独立副本，$E'=\{|T'|\le n/2\}$。由于

$$ \operatorname{Var}(T) = \frac12\mathbb E(T-T')^2, $$

而 $E^c\cup E'^c$ 上的贡献可由上面的三阶矩界控制。事实上，$\mathbb ET^2\le C_\beta n$，并且

$$ \mathbb E[(T-T')^2\mathbf 1_{E^c}] \le 2\mathbb E[T^2\mathbf 1_{E^c}] + 2\mathbb ET^2\,\mathbb P(E^c) \le C_\beta\sqrt n, $$

对 $E'^c$ 同理。因此当 $n\ge n_0(\alpha,\beta)$ 时，

$$ \mathbb E\bigl[(T-T')^2\mathbf 1_{E\cap E'}\bigr] \ge c\alpha n. $$

在 $E\cap E'$ 上，$S=n+T$ 和 $S'=n+T'$ 都位于 $[n/2,3n/2]$。由均值定理，

$$ |\sqrt S-\sqrt{S'}| \ge \frac{c}{\sqrt n}|S-S'| = \frac{c}{\sqrt n}|T-T'|. $$

再次使用独立副本公式，

$$ \operatorname{Var}(\|X\|_2) = \frac12\mathbb E(\sqrt S-\sqrt{S'})^2 \ge \frac{c}{n}\mathbb E\bigl[(T-T')^2\mathbf 1_{E\cap E'}\bigr] \ge c\alpha. $$

最后使用恒等式 $\mathbb EY^2=n$，

$$ (\mathbb EY)^2 = n-\operatorname{Var}(Y) \le n-c\alpha. $$

因此

$$ \mathbb E\|X\|_2 \le \sqrt{n-c\alpha} \le \sqrt n-\frac{c'\alpha}{\sqrt n}, $$

其中最后一步在调整常数并取 $n$ 足够大后成立。方差下界假设必要：若每个 $X_i^2$ 几乎处处等于 $1$，例如 Rademacher 坐标，则 $\|X\|_2\equiv\sqrt n$，方差为 $0$。

证明思路

把 $\mathbb E\|PX\|_2^2$ 写成 $\operatorname{tr}(P\Sigma)$。对 $\Sigma$ 的特征基展开后，问题变成在 $0\le p_i\le1$ 且 $\sum p_i=k$ 下最大化 $\sum \lambda_ip_i$。

完整证明

设 $\Sigma=\operatorname{cov}(X)$，且 $\Sigma v_i=\lambda_i v_i$。对 $P_k$，

$$ \mathbb E\|P_kX\|_2^2 = \sum_{i=1}^k\mathbb E\langle X,v_i\rangle^2 = \sum_{i=1}^k\lambda_i. $$

若 $P$ 是任意秩为 $k$ 的正交投影，则

$$ \mathbb E\|PX\|_2^2 = \operatorname{tr}(P\Sigma) = \sum_{i=1}^n\lambda_i\langle Pv_i,v_i\rangle. $$

令 $p_i=\langle Pv_i,v_i\rangle=\|Pv_i\|_2^2$。则 $0\le p_i\le1$，并且

$$ \sum_i p_i=\operatorname{tr}(P)=k. $$

由于 $\lambda_1\ge\cdots\ge\lambda_n$，在线性规划约束 $0\le p_i\le1$、$\sum p_i=k$ 下，$\sum_i\lambda_ip_i$ 的最大值由 $p_1=\cdots=p_k=1$、其余为 $0$ 取得。因此

$$ \mathbb E\|PX\|_2^2 \le \sum_{i=1}^k\lambda_i = \mathbb E\|P_kX\|_2^2. $$

证明思路

当 $p\le\log n$ 时，直接用次高斯 moment growth 控制 $\sum |X_i|^p$。当 $p\ge\log n$ 时，用 $\ell^\infty$ 范数控制 $\ell^p$ 范数。

完整证明

若 $p<\infty$，由 Jensen 或 Minkowski 型估计，

$$ \mathbb E\|X\|_p \le \left(\mathbb E\|X\|_p^p\right)^{1/p} = \left(\sum_i\mathbb E|X_i|^p\right)^{1/p}. $$

次高斯 moment growth 给出 $\|X_i\|_{L^p}\le CK\sqrt p$，所以当 $p\le\log n$ 时，

$$ \mathbb E\|X\|_p \le CK\sqrt p\,n^{1/p}. $$

当 $p\ge\log n$ 时，$\|x\|_p\le n^{1/p}\|x\|_\infty\le e\|x\|_\infty$。又由次高斯最大值界，

$$ \mathbb E\|X\|_\infty = \mathbb E\max_i|X_i| \le CK\sqrt{\log n}. $$

合并得所需上界。

证明思路

$p\le\log n$ 时，$\sum |g_i|^p$ 由许多同分布项贡献，Paley-Zygmund 给出它不小于其均值的常数概率。$p\ge\log n$ 时，用 Gaussian 最大值下界。

完整证明

先设 $1\le p\le\log n$。由 Gaussian 矩估计，

$$ \mathbb E|g|^p\asymp (\sqrt p)^p. $$

令 $S=\sum_i|g_i|^p$。用 Paley-Zygmund 需要控制 $\mathbb ES^2$。记 $m_p=\mathbb E|g|^p$，则

$$ \mathbb ES=nm_p, \qquad \mathbb ES^2 = n\mathbb E|g|^{2p}+n(n-1)m_p^2. $$

Gaussian 矩公式给出 $\mathbb E|g|^{2p}\le (Cp)^p$ 且 $m_p^2\ge(c p)^p$。由于 $p\le\log n$，可把第一项吸收到 $C n^2m_p^2$ 中，于是 $\mathbb ES^2\le C(\mathbb ES)^2$。Paley-Zygmund 不等式给出

$$ \mathbb P\{S\ge c\,\mathbb ES\}\ge c. $$

因此

$$ \mathbb E\|g\|_p = \mathbb ES^{1/p} \ge c(\mathbb ES)^{1/p} \ge c\sqrt p\,n^{1/p}. $$

若 $p\ge\log n$，则 $\|g\|_p\ge\|g\|_\infty$，而独立 Gaussian 最大值满足

$$ \mathbb E\max_{i\le n}|g_i| \ge c\sqrt{\log n}. $$

于是得到第二个下界。

证明思路

小球概率直接由联合密度上界乘以 Euclidean 球体积得到。倒数期望用 tail integral，把小球概率代入积分。

完整证明

由于坐标独立且每个密度由 $K$ 控制，$X$ 的联合密度由 $K^n$ 控制。因此对任意 $a$，

$$ \mathbb P\{\|X-a\|_2\le\varepsilon\sqrt n\} \le K^n\operatorname{Vol}(\varepsilon\sqrt n B_2^n). $$

利用体积估计 $\operatorname{Vol}(B_2^n)\le (2\pi e/n)^{n/2}$，得到

$$ \mathbb P\{\|X-a\|_2\le\varepsilon\sqrt n\} \le (\sqrt{2\pi e}\,K\varepsilon)^n. $$

对 (b)，用

$$ \mathbb E\frac1{\|X\|_2} = \int_0^\infty \mathbb P\left\{\frac1{\|X\|_2}>s\right\}\,ds. $$

当 $s\le CK/\sqrt n$ 时用平凡界 $1$；当 $s>CK/\sqrt n$ 时，令 $\varepsilon=1/(s\sqrt n)$ 并使用 (a)，积分被

$$ \frac{CK}{\sqrt n} + \int_{CK/\sqrt n}^\infty \left(\frac{CK}{s\sqrt n}\right)^n ds \le \frac{CK}{\sqrt n} $$

控制，其中 $n\ge2$ 保证尾积分收敛。$n=1$ 时若密度在 $0$ 附近为正，则 $\mathbb E(1/|X|)=\infty$。

证明思路

把均值方向作为测试方向，用 Jensen 比较均值投影和二阶投影。

完整证明

令 $\mu=\mathbb EX$。若 $\mu=0$，则 $\|\mu\|_2=0\le1$。否则取 $u=\mu/\|\mu\|_2$。各向同性给出

$$ \mathbb E\langle X,u\rangle^2=1. $$

而 Jensen 给出

$$ \|\mu\|_2^2 = \langle\mathbb EX,u\rangle^2 \le \mathbb E\langle X,u\rangle^2 = 1. $$

所以 $\|\mathbb EX\|_2\le1$。

最优性例子如下：令 $X=(1,\varepsilon_2,\ldots,\varepsilon_n)$，其中 $\varepsilon_j$ 是独立 Rademacher 随机变量。则 $\mathbb EX=e_1$，所以 $\|\mathbb EX\|_2=1$；同时 $\mathbb EXX^{\mathsf T}=I_n$，故 $X$ 各向同性。

证明思路

把 $X_u=\langle X,u\rangle$ 写入二阶矩，直接使用 $\mathbb EXX^{\mathsf T}=I_n$。

完整证明

有

$$ \mathbb E X_uX_v = \mathbb E\langle X,u\rangle\langle X,v\rangle = u^{\mathsf T}\mathbb E(XX^{\mathsf T})v = \langle u,v\rangle. $$

因此

$$ \|X_u-X_v\|_{L^2}^2 = \mathbb E\langle X,u-v\rangle^2 = \|u-v\|_2^2. $$

开平方即得第二个等式。

证明思路

正向直接计算均值和协方差。反向在 $\Sigma$ 可逆时白化；奇异时用 Moore-Penrose 逆处理 range，再在 kernel 上补独立噪声。

完整证明

若 $X=\mu+\Sigma^{1/2}Z$，且 $\mathbb EZ=0$、$\mathbb EZZ^{\mathsf T}=I$，则

$$ \mathbb EX=\mu, \qquad \operatorname{cov}(X) = \Sigma^{1/2}I\Sigma^{1/2} = \Sigma. $$

反过来，若 $X$ 的均值为 $\mu$、协方差为 $\Sigma$。当 $\Sigma$ 可逆时，取

$$ Z=\Sigma^{-1/2}(X-\mu), $$

则 $\mathbb EZ=0$ 且 $\operatorname{cov}(Z)=I$，并且 $X=\mu+\Sigma^{1/2}Z$。

若 $\Sigma$ 奇异，令 $P$ 为 $\operatorname{range}(\Sigma)$ 上的正交投影，取

$$ Z_0=(\Sigma^\dagger)^{1/2}(X-\mu), $$

其中 $\Sigma^\dagger$ 是 Moore-Penrose 逆。则 $\operatorname{cov}(Z_0)=P$。再取一个独立随机向量 $W$，满足 $\mathbb EW=0$、$\operatorname{cov}(W)=I-P$ 且 $W$ 落在 $\ker(\Sigma)$ 中，令 $Z=Z_0+W$。于是 $Z$ 各向同性，并且 $\Sigma^{1/2}W=0$，所以仍有 $X=\mu+\Sigma^{1/2}Z$。

证明思路

每个坐标都等概率取到 $x_1,\ldots,x_n$ 中的任一值；两个不同坐标等概率取到两个不同的原始坐标。

完整证明

对每个 $i$，

$$ \mathbb EX_i=\frac1n\sum_{a=1}^n x_a=0, \qquad \mathbb EX_i^2=\frac1n\sum_{a=1}^n x_a^2=\frac1n. $$

若 $i\ne j$，则 $(X_i,X_j)$ 等概率取所有有序不同对 $(x_a,x_b)$，所以

$$ \mathbb EX_iX_j = \frac1{n(n-1)}\sum_{a\ne b}x_ax_b = \frac{(\sum_a x_a)^2-\sum_a x_a^2}{n(n-1)} = -\frac1{n(n-1)}. $$

因此 $\mathbb EX=0$，协方差矩阵对角元为 $1/n$，非对角元为 $-1/[n(n-1)]$。等价地，

$$ \operatorname{cov}(X) = \frac1{n-1}\left(I_n-\frac1n\mathbf 1\mathbf 1^{\mathsf T}\right). $$

负相关的直觉是：抽样是不放回的。如果某个坐标拿到较大的 $x_a$，剩余坐标可选择的值中较大值少了一个，所以另一个坐标倾向于略小。

证明思路

展开平方。各向同性给出每个向量的二阶矩为 $n$，独立和中心化让交叉项为 $0$。

完整证明

由各向同性，$\mathbb E\|X\|_2^2=\operatorname{tr}(I_n)=n$，同理 $\mathbb E\|Y\|_2^2=n$。又因为 $X,Y$ 独立且均值为零，

$$ \mathbb E\langle X,Y\rangle = \langle \mathbb EX,\mathbb EY\rangle = 0. $$

于是

$$ \mathbb E\|X-Y\|_2^2 = \mathbb E\|X\|_2^2+\mathbb E\|Y\|_2^2-2\mathbb E\langle X,Y\rangle = 2n. $$

证明思路

上界对每个 $X_i$ 使用薄壳尾界，再对 $i$ 做并集界并积分尾概率。下界分别来自单个 Gaussian 向量的长度和第一坐标最大值。

完整证明

当 $N=1$ 时，由 Jensen 不等式，$\mathbb E\|X_1\|_2\le(\mathbb E\|X_1\|_2^2)^{1/2}=\sqrt n$，上界已经成立。下面设 $N\ge2$。

由 Theorem 3.1.1，对每个 $i$ 有

$$ \mathbb P\{\|X_i\|_2>\sqrt n+t\} \le 2\exp(-ct^2/K^4). $$

并集界给出

$$ \mathbb P\left\{\max_{i\le N}\|X_i\|_2>\sqrt n+t\right\} \le 2N\exp(-ct^2/K^4). $$

对尾概率积分，取分界点 $t_0=CK^2\sqrt{\log N}$，得到

$$ \mathbb E\max_{i\le N}\|X_i\|_2 \le \sqrt n+CK^2\sqrt{\log N}. $$

对于下界，若 $X_i\sim N(0,I_n)$ 独立，则

$$ \mathbb E\max_i\|X_i\|_2\ge \mathbb E\|X_1\|_2\ge c\sqrt n. $$

同时 $\|X_i\|_2\ge |X_{i1}|$，所以由一维 Gaussian 最大值下界，

$$ \mathbb E\max_i\|X_i\|_2 \ge \mathbb E\max_i|X_{i1}| \ge c\sqrt{\log N}. $$

两者合并为 $c(\sqrt n+\sqrt{\log N})$，调整常数即可。

证明思路

把 $X$ 写成 $\mu+\Sigma^{1/2}Z$，其中 $Z\sim N(0,I_n)$。线性投影变成独立标准正态的线性组合。

完整证明

令 $X=\mu+\Sigma^{1/2}Z$。则

$$ \langle X,v\rangle = \langle\mu,v\rangle+\langle Z,\Sigma^{1/2}v\rangle. $$

若 $a=\Sigma^{1/2}v$，则 $\langle Z,a\rangle$ 是均值 $0$、方差 $\|a\|_2^2$ 的正态变量。因此

$$ \langle X,v\rangle \sim N\left(\langle\mu,v\rangle,\| \Sigma^{1/2}v\|_2^2\right) = N\left(\langle\mu,v\rangle,v^{\mathsf T}\Sigma v\right). $$

证明思路

先平移到 $\mu=0$，再令 $X=\Sigma^{1/2}Z$。通过线性变量替换把标准正态密度推到 $X$ 的密度。

完整证明

设 $\Sigma$ 正定，$Z\sim N(0,I_n)$，$X=\mu+\Sigma^{1/2}Z$。对 Borel 集 $B$，

$$ \mathbb P\{X\in B\} = \int_{\Sigma^{-1/2}(B-\mu)} \frac1{(2\pi)^{n/2}}e^{-\|z\|_2^2/2}\,dz. $$

作变量替换 $x=\mu+\Sigma^{1/2}z$，则 $dz=(\det\Sigma)^{-1/2}\,dx$，且

$$ \|z\|_2^2 = (x-\mu)^{\mathsf T}\Sigma^{-1}(x-\mu). $$

因此

$$ \mathbb P\{X\in B\} = \int_B \frac1{(2\pi)^{n/2}(\det\Sigma)^{1/2}} \exp\left[-\frac12(x-\mu)^{\mathsf T}\Sigma^{-1}(x-\mu)\right]dx. $$

由密度定义，被积函数就是 $X$ 的密度。

证明思路

正向由 Exercise 3.14。反向用特征函数：多元特征函数在点 $u$ 的值就是一维投影 $\langle X,u\rangle$ 的特征函数。

完整证明

若 $X$ 多元正态，则所有 $\langle X,u\rangle$ 正态，这由 Exercise 3.14 已证。

反过来，假设所有 $\langle X,u\rangle$ 都是正态变量。令 $\mu=\mathbb EX$，$\Sigma=\operatorname{cov}(X)$。对任意 $u$，一维投影的均值和方差分别为 $\langle\mu,u\rangle$ 和 $u^{\mathsf T}\Sigma u$，所以

$$ \varphi_X(u) = \mathbb E e^{i\langle u,X\rangle} = \exp\left(i\langle\mu,u\rangle-\frac12 u^{\mathsf T}\Sigma u\right). $$

这正是 $N(\mu,\Sigma)$ 的特征函数。特征函数唯一确定分布，因此 $X\sim N(\mu,\Sigma)$。

(b) 对 $X=(X_1,\ldots,X_n)$，线性组合 $a_1X_1+\cdots+a_nX_n$ 就是 $\langle a,X\rangle$，所以 (a) 直接给出结论。

证明思路

用随机符号翻转一个正态变量。符号翻转不改变正态边缘，但会让两个变量共享绝对值，从而不独立。

完整证明

令 $Z\sim N(0,1)$，令 $\varepsilon$ 是独立 Rademacher 随机变量。取

$$ X=Z,\qquad Y=\varepsilon Z. $$

因为正态分布关于 $0$ 对称，$\varepsilon Z\sim N(0,1)$。并且

$$ \mathbb E XY = \mathbb E(\varepsilon Z^2) = \mathbb E\varepsilon\,\mathbb EZ^2 = 0, $$

所以 $X,Y$ 不相关。它们不独立，因为 $|Y|=|X|$ 几乎处处成立；若独立且非退化，这种确定性关系不可能成立。

证明思路

左乘正交矩阵作用在每一列上，右乘正交矩阵作用在每一行上。标准 Gaussian 向量在正交变换下不变。

完整证明

设 $G$ 的列为 $g_1,\ldots,g_n$，它们独立且都服从 $N(0,I_n)$。若 $U$ 正交，则 $Ug_j\sim N(0,I_n)$，且各列仍独立。因此 $UG$ 与 $G$ 同分布。

同理，$G$ 的行向量独立且都服从 $N(0,I_n)$。右乘 $U$ 把每一行 $r_i$ 变为 $r_iU$。由于标准 Gaussian 行向量也正交不变，$r_iU\sim N(0,I_n)$，独立性保持，所以 $GU$ 与 $G$ 同分布。

证明思路

对称化后，对角元是 $\sqrt2G_{ii}$，非对角元是两个独立标准正态和的 $1/\sqrt2$ 缩放。共轭不变性来自 Ginibre 的左右正交不变性。

完整证明

(a) 令 $A=(G+G^{\mathsf T})/\sqrt2$。对角元为 $A_{ii}=\sqrt2G_{ii}\sim N(0,2)$。若 $i<j$，则

$$ A_{ij}=\frac{G_{ij}+G_{ji}}{\sqrt2}\sim N(0,1). $$

不同上三角元素依赖于互不相交的 Ginibre 元素集合，因此独立。这正是 GOE 定义。

(b) 对任意正交 $U$，

$$ UAU^{\mathsf T} = \frac{UGU^{\mathsf T}+(UGU^{\mathsf T})^{\mathsf T}}{\sqrt2}. $$

由 Ginibre 左右正交不变性，$UGU^{\mathsf T}$ 与 $G$ 同分布。因此 $UAU^{\mathsf T}$ 与 $(G+G^{\mathsf T})/\sqrt2$ 同分布，也就是与 $A$ 同分布。

证明思路

逐行看。每一行与 $u,v$ 的内积是二维联合正态，协方差为 $\langle u,v\rangle=0$，所以独立。不同的行之间也独立。

完整证明

设 $g_1,\ldots,g_m$ 是 $G$ 的行，它们独立且服从 $N(0,I_n)$。则

$$ Gu=(\langle g_1,u\rangle,\ldots,\langle g_m,u\rangle), \qquad Gv=(\langle g_1,v\rangle,\ldots,\langle g_m,v\rangle). $$

对固定行 $g_r$，随机向量 $(\langle g_r,u\rangle,\langle g_r,v\rangle)$ 是二维正态，均值为 $0$，协方差矩阵为

$$ \begin{bmatrix} \|u\|_2^2&\langle u,v\rangle\\ \langle u,v\rangle&\|v\|_2^2 \end{bmatrix} = I_2. $$

因此这两个坐标独立且均为 $N(0,1)$。不同 $r$ 之间由行独立性可知相互独立，所以 $Gu$ 和 $Gv$ 是独立的 $N(0,I_m)$ 随机向量。

证明思路

把 $(X,Y)$ 看成 $\mathbb R^{2n}$ 中的标准 Gaussian 向量。映射 $(X,Y)\mapsto((X+Y)/\sqrt2,(X-Y)/\sqrt2)$ 是正交变换；标准 Gaussian 在正交变换下分布不变。

完整证明

令

$$ U=\frac{X+Y}{\sqrt2},\qquad V=\frac{X-Y}{\sqrt2}. $$

向量 $(X,Y)\in\mathbb R^{2n}$ 服从 $N(0,I_{2n})$。线性变换

$$ (x,y)\mapsto\left(\frac{x+y}{\sqrt2},\frac{x-y}{\sqrt2}\right) $$

的矩阵为

$$ Q=\frac1{\sqrt2} \begin{bmatrix} I_n&I_n\\ I_n&-I_n \end{bmatrix}, \qquad Q^{\mathsf T}Q=I_{2n}. $$

因此 $(U,V)=Q(X,Y)$ 仍服从 $N(0,I_{2n})$。这说明 $U$ 与 $V$ 的联合协方差矩阵是分块对角矩阵

$$ \begin{bmatrix} I_n&0\\ 0&I_n \end{bmatrix}. $$

联合 Gaussian 向量中，不相关等价于独立，所以 $U$ 和 $V$ 独立，并且各自服从 $N(0,I_n)$。

证明思路

用极坐标写出 Gaussian 密度。密度只依赖半径，Lebesgue 体积元分解为 $r^{n-1}dr\,d\sigma(z)$，于是半径和方向的联合密度分解成两个因子。

完整证明

对 $g\sim N(0,I_n)$，密度为

$$ (2\pi)^{-n/2}\exp(-\|x\|_2^2/2). $$

写 $x=rz$，其中 $r>0$，$z\in S^{n-1}$。极坐标体积元为

$$ dx=r^{n-1}\,dr\,d\sigma(z), $$

其中 $d\sigma$ 是球面面积测度。于是 $(R,Z)=(\|g\|_2,g/\|g\|_2)$ 的联合测度正比于

$$ e^{-r^2/2}r^{n-1}\,dr\,d\sigma(z). $$

右边分解为只含 $r$ 的因子和只含 $z$ 的因子。因此 $R$ 与 $Z$ 独立，并且 $Z$ 在球面上均匀分布。

证明思路

先固定 $g_1$，用 $x=g_1$ 尝试分离它与其他点。典型地 $\|g_1\|_2^2\asymp n$，而条件在 $g_1$ 上，$\langle g_j,g_1\rangle$ 是标准差 $\|g_1\|_2$ 的一维 Gaussian；指数多个点仍很难超过 $\|g_1\|_2^2$。

完整证明

先证明 (a)。取 $x=g_1$。如果

$$ \|g_1\|_2^2>\max_{j\ge2}\langle g_j,g_1\rangle, $$

则 $g_1$ 与其他点被线性泛函 $\langle\cdot,g_1\rangle$ 分离。由 $\chi^2$ 集中，存在绝对常数 $c_1>0$，使

$$ \mathbb P\{\|g_1\|_2^2<n/2\}\le e^{-c_1n}. $$

在事件 $\|g_1\|_2^2\ge n/2$ 上，条件于 $g_1$，每个 $\langle g_j,g_1\rangle$ 都服从 $N(0,\|g_1\|_2^2)$，所以

$$ \mathbb P\{\langle g_j,g_1\rangle\ge \|g_1\|_2^2\mid g_1\} \le \exp(-\|g_1\|_2^2/2) \le e^{-n/4}. $$

对 $j=2,\ldots,N$ 用 union bound，若 $N\le e^{cn}$ 且 $c<1/8$，失败概率至多 $e^{-c_2n}$。因此 (a) 成立。

对 (b)，如果 $g_1\in\operatorname{conv}\{g_2,\ldots,g_N\}$，则对任意 $x$，

$$ \langle g_1,x\rangle \le \max_{j=2,\ldots,N}\langle g_j,x\rangle, $$

因为线性泛函在凸包上的最大值由极点达到。这与 (a) 中的严格分离矛盾。因此 (a) 推出 $g_1$ 不在其余点凸包中。

最后对每个 $i$ 重复同样论证。每个点失败概率至多 $e^{-c_2n}$，于是

$$ \mathbb P\{\exists i:\ g_i\in\operatorname{conv}(g_j:j\ne i)\} \le N e^{-c_2n}. $$

把最初的 $c$ 选得足够小，使 $N\le e^{cn}$ 且 $c<c_2/2$，上式至多为 $e^{-c'n}$。因此这些点以至少 $1-e^{-c'n}$ 的概率处于凸位置。

证明思路

用极坐标计算锥形区域的体积。方向由球面对称性给出均匀性，半径分布由 $r$ 倍缩放体积 $r^n$ 给出。

完整证明

令 $R=\|X\|_2$，$Z=X/\|X\|_2$。对 $0\le t\le1$，

$$ \mathbb P\{R\le t\} = \frac{\operatorname{Vol}(tB_2^n)}{\operatorname{Vol}(B_2^n)} = t^n. $$

因此 $R$ 的密度为 $n r^{n-1}$，$0\le r\le1$。

进一步，若 $A\subset S^{n-1}$ 是可测集合，则锥形区域 $\{rz:0\le r\le t,\ z\in A\}$ 的体积等于半径部分 $t^n$ 乘以方向部分的球面比例。因此

$$ \mathbb P\{R\le t,\ Z\in A\} = t^n\,\sigma(A), $$

其中 $\sigma$ 是球面上的均匀概率测度。这个联合概率分解为 $\mathbb P\{R\le t\}\mathbb P\{Z\in A\}$，故 $R$ 与 $Z$ 独立，且 $Z\sim\operatorname{Unif}(S^{n-1})$。

证明思路

球的中心对称性给出零均值；旋转不变性给出协方差是标量矩阵。标量由 $\mathbb E\|Y\|_2^2$ 决定，而单位球半径平方的期望是 $n/(n+2)$。

完整证明

令 $X$ 均匀分布在单位 Euclidean 球中，则 $Y=\sqrt{n+2}\,X$。由于分布关于原点对称，$\mathbb EY=0$。

由旋转不变性，$\mathbb EYY^{\mathsf T}=\alpha I_n$。取迹得到

$$ n\alpha=\mathbb E\|Y\|_2^2=(n+2)\mathbb E\|X\|_2^2. $$

由 Exercise 3.24，$\|X\|_2=R$ 的密度为 $nr^{n-1}$，所以

$$ \mathbb E R^2 = n\int_0^1 r^{n+1}\,dr = \frac n{n+2}. $$

因此 $\mathbb E\|Y\|_2^2=n$，从而 $\alpha=1$。于是 $\mathbb EYY^{\mathsf T}=I_n$，即 $Y$ 是各向同性的。

证明思路

用表示 $X=g/\|g\|_2$。分子最大坐标的期望是 $\sqrt{\log n}$ 量级；分母以高概率是 $\sqrt n$ 量级。上下界分别用 Gaussian 最大值和 $\chi^2$ 集中。

完整证明

令 $g\sim N(0,I_n)$，则 $X=g/\|g\|_2$ 均匀分布在球面上。

先证上界。设事件 $E=\{\|g\|_2\ge\sqrt{n/2}\}$。在 $E$ 上，

$$ \|X\|_\infty\le \sqrt{\frac2n}\|g\|_\infty. $$

由 Gaussian maximal inequality，$\mathbb E\|g\|_\infty\le C\sqrt{\log n}$。而 $E^c$ 的概率指数小，且 $\|X\|_\infty\le1$，故

$$ \mathbb E\|X\|_\infty \le C\sqrt{\frac{\log n}{n}}+\mathbb P(E^c) \le C'\sqrt{\frac{\log n}{n}}. $$

再证下界。对足够小的绝对常数 $c>0$，独立标准正态最大值满足

$$ \mathbb P\{\|g\|_\infty\ge c\sqrt{\log n}\}\ge c_1 $$

对所有足够大的 $n$ 成立；这可由 Gaussian tail 下界和独立性得到。同时 $\mathbb P\{\|g\|_2\le2\sqrt n\}\ge1-e^{-c_2n}$。两事件同时发生的概率至少为某个绝对常数 $c_3>0$。在交集上，

$$ \|X\|_\infty = \frac{\|g\|_\infty}{\|g\|_2} \ge c\sqrt{\frac{\log n}{n}}. $$

因此 $\mathbb E\|X\|_\infty\ge c'\sqrt{\log n/n}$。上下界合并即得结论。

证明思路

由旋转不变性，只需看第一坐标。球内分布用固定 $x_1=t$ 的截面体积；球面分布用固定 $x_1=t$ 的球面切片面积和 coarea 因子。

完整证明

先看 (a)。设 $Y$ 均匀分布在 $B_2^n$ 中。固定 $Y_1=t\in[-1,1]$ 时，剩余坐标构成 $\mathbb R^{n-1}$ 中半径为 $\sqrt{1-t^2}$ 的 Euclidean 球。因此边缘密度与该截面体积成正比：

$$ f_{Y_1}(t)\propto \operatorname{Vol}\left(\sqrt{1-t^2}\,B_2^{n-1}\right) = (1-t^2)^{(n-1)/2}, \qquad |t|\le1. $$

这证明 (a)。

再看 (b)。设 $X$ 均匀分布在 $S^{n-1}$。固定 $X_1=t$ 时，切片是半径 $\sqrt{1-t^2}$ 的 $(n-2)$ 维球面，面积与

$$ (1-t^2)^{(n-2)/2} $$

成正比。把球面参数化为 $(t,\sqrt{1-t^2}\,u)$，$u\in S^{n-2}$，coarea/弧长因子额外给出 $(1-t^2)^{-1/2}$。因此

$$ f_{X_1}(t)\propto (1-t^2)^{(n-2)/2}(1-t^2)^{-1/2} = (1-t^2)^{(n-3)/2}, \qquad |t|\le1. $$

当 $n=3$ 时指数为 $0$，所以一维边缘确为均匀分布。

证明思路

投影到立方体按坐标独立裁剪。距离平方是 $\sum_i(|g_i|-a)_+^2$，选 $a$ 足够大让单坐标期望很小；另一方面，落入 $[-100a,100a]^n$ 的概率随 $n$ 指数趋零。

完整证明

(a) 到立方体的距离平方为

$$ \sum_{i=1}^n (x_i-y_i)^2 \qquad\text{subject to }y_i\in[-a,a]. $$

这个最小化问题按坐标分离。对每个坐标，区间 $[-a,a]$ 上离 $x_i$ 最近的点就是

$$ y_i= \begin{cases} x_i, & |x_i|\le a,\\ a\,\operatorname{sign}(x_i), & |x_i|>a. \end{cases} $$

因此 metric projection 就是逐坐标裁剪。

(b) 由 (a)，

$$ \operatorname{dist}(g,[-a,a]^n)^2 = \sum_{i=1}^n (|g_i|-a)_+^2. $$

令 $W=(|g_1|-a)_+^2$。因为 Gaussian 尾部可积，$\mathbb EW\to0$ 当 $a\to\infty$。选择固定的 $a$，使 $\mathbb EW<10^{-5}$。由大数定律，存在 $n_0$，使对所有 $n>n_0$，以概率至少 $0.995$ 有

$$ \frac1n\sum_{i=1}^n (|g_i|-a)_+^2<2\cdot10^{-5}. $$

同时由 $\chi^2$ 集中，增大 $n_0$ 后，以概率至少 $0.995$ 有 $\|g\|_2^2\ge n/2$。在这两个事件同时发生时，

$$ \operatorname{dist}(g,[-a,a]^n)^2 < 2\cdot10^{-5}n < 10^{-4}\|g\|_2^2, $$

即 $\operatorname{dist}(g,[-a,a]^n)<0.01\|g\|_2$。

最后，$p_a=\mathbb P\{|g_1|>100a\}>0$ 是固定正数。因此

$$ \mathbb P\{g\in[-100a,100a]^n\} = (1-p_a)^n \to0. $$

再次增大 $n_0$，使这个概率小于 $0.005$。合并三项失败概率，得到题设的至少 $0.99$ 概率结论。

证明思路

把 frame 条件写成矩阵恒等式。若 $U$ 的列是 $u_i$，则 $\sum_i\langle x,u_i\rangle^2=x^{\mathsf T}UU^{\mathsf T}x$。Parseval 条件要求它等于 $\|x\|_2^2$ 对所有 $x$ 成立，也就是 $UU^{\mathsf T}=I_n$。

完整证明

设 $U$ 是以 $u_i$ 为列的 $n\times N$ 矩阵。对任意 $x\in\mathbb R^n$，有

$$ \sum_{i=1}^N \langle x,u_i\rangle^2 = \|U^{\mathsf T}x\|_2^2 = x^{\mathsf T}UU^{\mathsf T}x. $$

向量 $u_1,\ldots,u_N$ 构成 Parseval frame，当且仅当上式对所有 $x$ 等于 $\|x\|_2^2=x^{\mathsf T}x$，也就是

$$ x^{\mathsf T}(UU^{\mathsf T}-I_n)x=0 \qquad\text{for all }x. $$

由于 $UU^{\mathsf T}-I_n$ 是对称矩阵，这等价于 $UU^{\mathsf T}=I_n$。

而 $UU^{\mathsf T}$ 的 $(a,b)$ 元正是 $U$ 第 $a$ 行与第 $b$ 行的内积。因此 $UU^{\mathsf T}=I_n$ 等价于 $U$ 的行向量两两正交且每行长度为 $1$，即行正交归一。

证明思路

用 Exercise 3.29，只需检查以这些点为列的 $2\times N$ 矩阵两行正交归一。等距点的三角函数和由单位根求和给出。

完整证明

这里需要 $N\ge3$；若 $N=1$ 或 $N=2$，这些点张不成 $\mathbb R^2$，不可能构成 $\mathbb R^2$ 的 Parseval frame。设

$$ u_j=\sqrt{\frac2N}\,(\cos\theta_j,\sin\theta_j), \qquad \theta_j=\frac{2\pi j}{N}, \qquad j=0,\ldots,N-1. $$

记 $U=[u_0\ \cdots\ u_{N-1}]$。两行内积分别为

$$ \frac2N\sum_{j=0}^{N-1}\cos^2\theta_j, \qquad \frac2N\sum_{j=0}^{N-1}\sin^2\theta_j, \qquad \frac2N\sum_{j=0}^{N-1}\sin\theta_j\cos\theta_j. $$

由

$$ \sum_{j=0}^{N-1}e^{2i\theta_j}=0, $$

得到 $\sum_j\cos(2\theta_j)=0$ 且 $\sum_j\sin(2\theta_j)=0$。因此

$$ \sum_j\cos^2\theta_j=\sum_j\sin^2\theta_j=\frac N2, \qquad \sum_j\sin\theta_j\cos\theta_j=0. $$

所以 $U$ 的两行正交归一。由 Exercise 3.29，这些点构成 Parseval frame。

证明思路

各向同性条件就是二阶矩矩阵为单位矩阵。有限分布的二阶矩是 $\sum_i p_ix_ix_i^{\mathsf T}$，这正是加权向量的 frame operator。

完整证明

令 $u_i=\sqrt{p_i}x_i$。因为 $X$ 各向同性，

$$ I_n=\mathbb E XX^{\mathsf T} = \sum_{i=1}^N p_i x_ix_i^{\mathsf T} = \sum_{i=1}^N u_iu_i^{\mathsf T}. $$

对任意 $x\in\mathbb R^n$，于是

$$ \sum_{i=1}^N \langle x,u_i\rangle^2 = x^{\mathsf T} \left(\sum_i u_iu_i^{\mathsf T}\right)x = \|x\|_2^2. $$

这正是 Parseval frame 的定义。

证明思路

若 $v\ne0$，把 $v$ 归一化为 $v/\|v\|_2$，再用 $\psi_2$ 范数的齐次性。

完整证明

当 $v=0$ 时，投影恒为 $0$，结论成立。若 $v\ne0$，令 $u=v/\|v\|_2\in S^{n-1}$。则

$$ \langle X,v\rangle = \|v\|_2\langle X,u\rangle. $$

由 $\psi_2$ 范数的齐次性和随机向量次高斯范数定义，

$$ \|\langle X,v\rangle\|_{\psi_2} = \|v\|_2\|\langle X,u\rangle\|_{\psi_2} \le \|v\|_2\|X\|_{\psi_2}. $$

证明思路

任意投影 $\langle UX,v\rangle$ 都等于原向量在方向 $U^{\mathsf T}v$ 上的投影；正交矩阵把单位球面映到自身。

完整证明

对任意 $v\in S^{n-1}$，

$$ \langle UX,v\rangle = \langle X,U^{\mathsf T}v\rangle. $$

由于 $U$ 正交，$U^{\mathsf T}v\in S^{n-1}$。因此

$$ \|UX\|_{\psi_2} = \sup_{v\in S^{n-1}} \|\langle X,U^{\mathsf T}v\rangle\|_{\psi_2} \le \|X\|_{\psi_2}. $$

反过来，对 $X=U^{\mathsf T}(UX)$ 应用同一个不等式，得到 $\|X\|_{\psi_2}\le\|UX\|_{\psi_2}$。两边合并即

$$ \|UX\|_{\psi_2}=\|X\|_{\psi_2}. $$

证明思路

把 $u^{\mathsf T}Av$ 写成独立次高斯变量 $\langle A_i,v\rangle$ 的加权和，然后使用独立次高斯和的范数估计。

完整证明

记 $K=\max_i\|A_i\|_{\psi_2}$。由行表示，

$$ u^{\mathsf T}Av = \sum_{i=1}^m u_i\langle A_i,v\rangle. $$

每个 $\langle A_i,v\rangle$ 均值为零且次高斯，并由 Exercise 3.32 满足

$$ \|\langle A_i,v\rangle\|_{\psi_2} \le \|A_i\|_{\psi_2}\|v\|_2 \le K\|v\|_2. $$

由于各行独立，变量 $u_i\langle A_i,v\rangle$ 独立、均值为零。独立次高斯和的估计给出

$$ \|u^{\mathsf T}Av\|_{\psi_2}^2 \le C\sum_{i=1}^m u_i^2 \|\langle A_i,v\rangle\|_{\psi_2}^2 \le CK^2\|u\|_2^2\|v\|_2^2. $$

开平方即得所需不等式。

如果假设改为列独立，则写成

$$ u^{\mathsf T}Av = \sum_{j=1}^n v_j\langle A^{(j)},u\rangle, $$

其中 $A^{(j)}$ 是第 $j$ 列。完全相同的论证给出同样结论。

证明思路

对任意单位方向 $v$ 投影，问题化为一维独立次高斯变量和；最后对所有 $v$ 取上确界。

完整证明

令 $S=\sum_{i=1}^N X_i$。对任意 $v\in S^{n-1}$，

$$ \langle S,v\rangle = \sum_{i=1}^N\langle X_i,v\rangle. $$

这些变量独立、均值为零且次高斯。一维和的估计给出

$$ \|\langle S,v\rangle\|_{\psi_2}^2 \le C\sum_{i=1}^N \|\langle X_i,v\rangle\|_{\psi_2}^2 \le C\sum_{i=1}^N \|X_i\|_{\psi_2}^2. $$

右侧与 $v$ 无关，对 $v\in S^{n-1}$ 取上确界，得到

$$ \left\|\sum_{i=1}^N X_i\right\|_{\psi_2}^2 \le C\sum_{i=1}^N \|X_i\|_{\psi_2}^2. $$

证明思路

下界取坐标方向。上界用三角不等式和 $\|v\|_1\le\sqrt n\|v\|_2$。最优性分别由单坐标例子和完全相关坐标例子给出。

完整证明

先证下界。对每个坐标方向 $e_i$，

$$ \|X_i\|_{\psi_2} = \|\langle X,e_i\rangle\|_{\psi_2} \le \|X\|_{\psi_2}. $$

取最大值得

$$ \max_i\|X_i\|_{\psi_2}\le\|X\|_{\psi_2}. $$

再证上界。令 $K=\max_i\|X_i\|_{\psi_2}$。对任意 $v\in S^{n-1}$，由 Orlicz 范数的三角不等式，

$$ \|\langle X,v\rangle\|_{\psi_2} = \left\|\sum_{i=1}^n v_iX_i\right\|_{\psi_2} \le \sum_{i=1}^n |v_i|\,\|X_i\|_{\psi_2} \le K\|v\|_1 \le K\sqrt n. $$

对 $v$ 取上确界即得上界。

下界的最优性可取 $X=(Z,0,\ldots,0)$，其中 $Z$ 是非零次高斯随机变量，此时 $\|X\|_{\psi_2}=\max_i\|X_i\|_{\psi_2}$。上界的最优性可取 $X=Z(1,\ldots,1)$，其中 $Z$ 是 Rademacher 随机变量。此时每个坐标的 $\psi_2$ 范数为常数，而沿 $v=(1,\ldots,1)/\sqrt n$ 投影得到 $\sqrt n\,Z$，所以 $\|X\|_{\psi_2}\ge c\sqrt n\max_i\|X_i\|_{\psi_2}$。

证明思路

让向量以固定正概率等于零，再以互补概率取放大的 Rademacher 向量，使协方差仍为单位矩阵。这样一维投影仍次高斯，但长度有两个相距 $\asymp\sqrt n$ 的取值。

完整证明

令 $B$ 是 Bernoulli 随机变量，$\mathbb P\{B=1\}=1/2$，令 $\varepsilon=(\varepsilon_1,\ldots,\varepsilon_n)$ 为独立 Rademacher 向量，并令 $B$ 与 $\varepsilon$ 独立。定义

$$ X=\sqrt2\,B\,\varepsilon. $$

因为 $\mathbb E\varepsilon=0$ 且 $B$ 与 $\varepsilon$ 独立，所以 $\mathbb EX=0$。并且

$$ \mathbb EXX^{\mathsf T} = 2\mathbb EB^2\,\mathbb E\varepsilon\varepsilon^{\mathsf T} = 2\cdot\frac12\cdot I_n = I_n. $$

所以 $X$ 各向同性。对任意 $v\in S^{n-1}$，

$$ \langle X,v\rangle = \sqrt2\,B\sum_i v_i\varepsilon_i. $$

Rademacher 和 $\sum_i v_i\varepsilon_i$ 的次高斯范数由绝对常数控制，乘以 $\sqrt2B$ 不会破坏这一点，因此 $\|X\|_{\psi_2}\le C$。

但是

$$ \|X\|_2 = \begin{cases} 0, & B=0,\\ \sqrt{2n}, & B=1. \end{cases} $$

它以概率 $1/2$ 等于 $0$、以概率 $1/2$ 等于 $\sqrt{2n}$，不可能以常数尺度集中在 $\sqrt n$ 附近。这说明坐标独立性不能从 Theorem 3.1.1 中简单删除。

证明思路

任意一维投影仍是正态随机变量，方差为 $v^{\mathsf T}\Sigma v$。再对单位方向取最大值。

完整证明

若 $X\sim N(0,\Sigma)$，则对任意 $v\in S^{n-1}$，

$$ \langle X,v\rangle \sim N(0,v^{\mathsf T}\Sigma v). $$

由 Exercise 2.24(c)，

$$ \|\langle X,v\rangle\|_{\psi_2} = \sqrt{\frac83}\, (v^{\mathsf T}\Sigma v)^{1/2}. $$

因此

$$ \|X\|_{\psi_2} = \sup_{v\in S^{n-1}} \|\langle X,v\rangle\|_{\psi_2} = \sqrt{\frac83}\, \sup_{v\in S^{n-1}} (v^{\mathsf T}\Sigma v)^{1/2}. $$

Rayleigh quotient 的最大值为 $\|\Sigma\|$，所以

$$ \|X\|_{\psi_2} = \sqrt{\frac83}\, \|\Sigma\|^{1/2}. $$

证明思路

用 $\psi_2$ 的矩刻画。对 $p\ge2$，$L^p(\ell_2)$ 的 Minkowski 不等式把向量范数的 $L^p$ 控制为坐标 $L^p$ 范数的平方和。

完整证明

(a) 原题无常数形式对应精确的矩刻画范数

$$ \|Z\|_{\psi_2,m}:=\sup_{p\ge1}\frac{\|Z\|_{L^p}}{\sqrt p}. $$

对 $p\ge2$，由 Minkowski 不等式在 Banach 空间 $L^p$ 中的形式，

$$ \left\| \left(\sum_{i=1}^nX_i^2\right)^{1/2} \right\|_{L^p} \le \left(\sum_{i=1}^n\|X_i\|_{L^p}^2\right)^{1/2}. $$

使用矩范数定义 $\|X_i\|_{L^p}\le \sqrt p\,\|X_i\|_{\psi_2,m}$，得到

$$ \left\| \left(\sum_iX_i^2\right)^{1/2} \right\|_{L^p} \le \sqrt p \left(\sum_i\|X_i\|_{\psi_2,m}^2\right)^{1/2}. $$

再对 $p\ge2$ 取 $p^{-1/2}L^p$ 上确界，即得到题设形式。若换回本站前文使用的 Orlicz 型 $\psi_2$ 范数，不等式会多出一个绝对常数，这是等价范数造成的，不影响本章后续尺度。

(b) 对随机向量 $X=(X_1,\ldots,X_n)$，每个坐标满足

$$ \|X_i\|_{\psi_2} = \|\langle X,e_i\rangle\|_{\psi_2} \le \|X\|_{\psi_2}. $$

把 (a) 应用于坐标，得到

$$ \bigl\|\|X\|_2\bigr\|_{\psi_2} \le C \left(\sum_{i=1}^n\|X_i\|_{\psi_2}^2\right)^{1/2} \le C\sqrt n\,\|X\|_{\psi_2}. $$

若采用本书归一化的矩范数定义，可把常数吸收入定义中；关键缩放是 $\sqrt n$。

这个因子一般不能改进。令 $X$ 在离散立方体 $\{-1,1\}^n$ 上均匀分布，则 $\|X\|_{\psi_2}\le C$，但 $\|X\|_2\equiv\sqrt n$。非零常数 $a$ 的 $\psi_2$ 范数与 $a$ 同阶，所以 $\bigl\|\|X\|_2\bigr\|_{\psi_2}\asymp\sqrt n$。

证明思路

(a) 分别控制内积 $\langle X,Y\rangle$ 和两个长度 $\|X\|_2,\|Y\|_2$。(b) 取高概率为零、低概率为放大 Rademacher 向量的分布，使两个独立样本很可能同时等于零。

完整证明

(a) 令 $Y$ 是 $X$ 的独立副本。坐标独立和均值零给出

$$ \langle X,Y\rangle=\sum_{i=1}^n X_iY_i, $$

其中 $X_iY_i$ 独立、均值为零且次指数范数由 $C(K)$ 控制。Bernstein 不等式给出

$$ |\langle X,Y\rangle|\le C(K)\sqrt n $$

以概率至少 $0.995$ 成立。另一方面，Theorem 3.1.1 或其平方范数版本给出

$$ \|X\|_2\ge c\sqrt n, \qquad \|Y\|_2\ge c\sqrt n $$

以概率至少 $0.995$ 成立。三件事同时发生的概率至少 $0.99$。在该事件上，

$$ |\langle\theta,\eta\rangle| = \frac{|\langle X,Y\rangle|} {\|X\|_2\|Y\|_2} \le \frac{C(K)\sqrt n}{c^2n} \le \frac{C'(K)}{\sqrt n}. $$

(b) 取一个很小的固定 $q>0$，例如 $q=10^{-3}$。令 $B\sim\operatorname{Ber}(q)$，令 $\varepsilon\in\{-1,1\}^n$ 为 Rademacher 向量，二者独立，并定义

$$ X=q^{-1/2}B\varepsilon. $$

则 $\mathbb EX=0$ 且

$$ \mathbb EXX^{\mathsf T} = q^{-1}\mathbb EB^2\,\mathbb E\varepsilon\varepsilon^{\mathsf T} = I_n, $$

所以 $X$ 各向同性。由于 $q$ 是固定常数，任意一维投影 $q^{-1/2}B\langle\varepsilon,v\rangle$ 的次高斯范数由绝对常数控制。若 $Y$ 是独立副本，则

$$ \mathbb P\{X=Y\} \ge \mathbb P\{X=0,\ Y=0\} = (1-q)^2 \ge 0.99 $$

只要 $q$ 取得足够小。这说明没有坐标独立性时结论会失败。

证明思路

随机取点。固定一对点的内积由球面一维边缘控制，失败概率为 $e^{-cn}$；再对所有点对做 union bound。

完整证明

(a) 条件在 $Y$ 上。由旋转不变性，$\langle X,Y\rangle$ 与 $\langle X,e_1\rangle$ 同分布。由 Theorem 3.4.5 的双边尾界，

$$ \mathbb P\{|\langle X,Y\rangle|>0.01\} \le 4\exp(-c_0n) $$

其中 $c_0>0$ 是绝对常数。

(b) 独立取 $X_1,\ldots,X_N\sim\operatorname{Unif}(S^{n-1})$。由 union bound，存在某对 $i<j$ 违反 $|\langle X_i,X_j\rangle|\le0.01$ 的概率至多

$$ \binom N2\,4e^{-c_0n} \le 2N^2e^{-c_0n}. $$

若 $N\le e^{cn}$ 且 $c<c_0/4$，则该上界小于 $1$（对所有足够大的 $n$；小维数可调小常数处理）。因此好事件以正概率发生。于是至少存在一组点满足

$$ |\langle X_i,X_j\rangle|\le0.01 \qquad(i\ne j). $$

证明思路

把球内均匀点写成 $Y=RU$，其中 $U$ 在球面均匀分布、$0\le R\le1$。投影绝对值被球面投影控制。

完整证明

由球内均匀分布的极坐标分解，可写

$$ Y=RU, $$

其中 $U\sim\operatorname{Unif}(S^{n-1})$，$R\in[0,1]$，且 $R$ 与 $U$ 独立。对任意 $v\in S^{n-1}$，

$$ |\langle Y,v\rangle| = R|\langle U,v\rangle| \le |\langle U,v\rangle|. $$

因此

$$ \mathbb P\{|\langle Y,v\rangle|\ge t\} \le \mathbb P\{|\langle U,v\rangle|\ge t\} \le 4\exp(-cnt^2) $$

对所有 $t\ge0$ 成立。于是 $Y$ 的一维边缘满足与 Theorem 3.4.5 同阶的次高斯尾界，特别地 $\|Y\|_{\psi_2}\le C/\sqrt n$。

证明思路

对任意单位方向 $v$，投影等于随机选取一个坐标 $v_I$。上界用 $\sum_i v_i^2=1$ 控制指数矩；下界取 $v=e_1$。

完整证明

设 $X$ 在 $\{e_1,\ldots,e_n\}$ 上均匀分布。对 $v\in S^{n-1}$，

$$ \langle X,v\rangle=v_I, \qquad I\sim\operatorname{Unif}\{1,\ldots,n\}. $$

令 $K=C/\sqrt{\log n}$，其中 $C$ 足够大。记 $s_i=v_i^2$，则 $s_i\ge0$ 且 $\sum_i s_i=1$。函数 $s\mapsto e^{s/K^2}$ 是凸函数，因此在 simplex 上，$\sum_i e^{s_i/K^2}$ 的最大值出现在极点。于是

$$ \mathbb E\exp\left(\frac{\langle X,v\rangle^2}{K^2}\right) = \frac1n\sum_{i=1}^n e^{v_i^2/K^2} \le \frac{e^{1/K^2}+n-1}{n} \le 2 $$

只要 $C$ 取得足够大。这给出 $\|X\|_{\psi_2}\le C/\sqrt{\log n}$。

下界取 $v=e_1$。此时 $\langle X,e_1\rangle$ 以概率 $1/n$ 等于 $1$，以概率 $1-1/n$ 等于 $0$。若它的 $\psi_2$ 范数为 $K$，则必须有

$$ \frac{e^{1/K^2}+n-1}{n}\le2, $$

从而 $e^{1/K^2}\le n+1$，即 $K\ge c/\sqrt{\log n}$。上下界合并得到

$$ \|X\|_{\psi_2} \asymp \frac1{\sqrt{\log n}}. $$

证明思路

坐标密度由切片体积给出。二阶矩由该密度积分得到。次高斯下界来自坐标的极端尾部：虽然概率约 $2^{-n}$，但幅度约 $r\asymp n$，强迫 $\psi_2$ 范数至少为 $r/\sqrt n\asymp\sqrt n$。

完整证明

(a) 固定 $t\in[-r,r]$。切片 $\{x\in K:x_1=t\}$ 是 $\mathbb R^{n-1}$ 中半径 $r-|t|$ 的 $\ell^1$ 球，其体积为

$$ \frac{2^{n-1}(r-|t|)^{n-1}}{(n-1)!}. $$

而 $K$ 的体积为 $2^nr^n/n!$。所以 $X_1$ 的密度是

$$ f(t) = \frac{n}{2r} \left(1-\frac{|t|}{r}\right)^{n-1}, \qquad |t|\le r. $$

(b) 由对称性，$\mathbb EX_i=0$，且不同坐标的协方差为 $0$。计算二阶矩：

$$ \mathbb EX_1^2 = \frac nr\int_0^r t^2\left(1-\frac tr\right)^{n-1}dt = nr^2\int_0^1 s^2(1-s)^{n-1}ds = \frac{2r^2}{(n+1)(n+2)}. $$

取

$$ r=\sqrt{\frac{(n+1)(n+2)}2}\asymp n $$

即可使 $\mathbb EX_1^2=1$，从而 $X$ 各向同性。

(c) 对这个 $r$，由 (a)，

$$ \mathbb P\{X_1\ge r/2\} = \int_{r/2}^r \frac{n}{2r} \left(1-\frac tr\right)^{n-1}dt = \frac12\left(\frac12\right)^n = 2^{-n-1}. $$

若 $\|X\|_{\psi_2}=K$，则坐标投影给出 $\|X_1\|_{\psi_2}\le K$，从而尾界要求

$$ 2^{-n-1} \le 2\exp\left(-c\frac{r^2}{K^2}\right). $$

因此 $K^2\ge c'r^2/n\ge c''n$，也就是 $\|X\|_{\psi_2}\ge c\sqrt n$。

证明思路

若 $X=x$，则在方向 $v=x/\|x\|_2$ 上的投影至少为 $\|x\|_2$。因此单点事件被一个一维尾事件包含。

完整证明

当 $x=0$ 时，不等式右侧为 $2$，而左侧至多为 $1$。设 $x\ne0$，令 $v=x/\|x\|_2$。若 $X=x$，则

$$ \langle X,v\rangle=\|x\|_2. $$

因此

$$ \mathbb P\{X=x\} \le \mathbb P\{\langle X,v\rangle\ge\|x\|_2\}. $$

又 $\|\langle X,v\rangle\|_{\psi_2}\le K$，次高斯尾界给出

$$ \mathbb P\{\langle X,v\rangle\ge\|x\|_2\} \le 2\exp\left(-\frac{\|x\|_2^2}{K^2}\right), $$

得到所需结论。

证明思路

上界 $H(X)\le\ln N$ 是熵的最大化性质。下界用 Exercise 3.45 控制每个原子概率，再对 $X$ 的取值取期望。

完整证明

(a) 若 $X$ 只取 $N$ 个值，概率为 $p_1,\ldots,p_N$，则由 Jensen 不等式或 KL 散度非负性，熵在均匀分布处最大：

$$ H(X) = -\sum_i p_i\ln p_i \le \ln N. $$

(b) 设 $X$ 取值为 $x_i$，概率为 $p_i$。由 Exercise 3.45，

$$ p_i \le 2\exp\left(-\frac{\|x_i\|_2^2}{K^2}\right). $$

于是

$$ -\ln p_i \ge \frac{\|x_i\|_2^2}{K^2}-\ln2. $$

乘以 $p_i$ 后求和，得到

$$ H(X) = \sum_i p_i(-\ln p_i) \ge \frac{\mathbb E\|X\|_2^2}{K^2}-\ln2. $$

若 $X$ 各向同性，则 $\mathbb E\|X\|_2^2=\operatorname{tr}(\mathbb EXX^{\mathsf T})=n$。因此

$$ H(X)\ge \frac n{K^2}-\ln2. $$

(c) 若 $X$ 的支撑大小为 $N$，由 (a) 和 (b)，

$$ \ln N \ge H(X) \ge \frac n{K^2}-\ln2. $$

指数化得到

$$ N \ge \frac12\exp(K^{-2}n). $$

证明思路

双线性函数在立方体上的最大值出现在顶点；齐次形式通过把任意向量除以 $\ell_\infty$ 范数得到。绝对值由同时允许符号翻转得到。

完整证明

(a) 推出 (b)：固定 $y\in[-1,1]^n$ 时，$x\mapsto x^{\mathsf T}Ay$ 是线性函数，因此它在 $[-1,1]^m$ 上的最大值在某个顶点 $x\in\{-1,1\}^m$ 取得。再固定这个顶点 $x$，函数 $y\mapsto x^{\mathsf T}Ay$ 也在线性立方体的顶点达到最大值。因此 (a) 控制了整个连续立方体。

(b) 推出 (a) 是直接的，因为符号立方体包含在连续立方体中。

(b) 推出 (c)：若 $x=0$ 或 $y=0$，则两边都为 $0$，结论成立。否则令

$$ \tilde x=\frac{x}{\|x\|_\infty}, \qquad \tilde y=\frac{y}{\|y\|_\infty}. $$

则 $\tilde x\in[-1,1]^m$、$\tilde y\in[-1,1]^n$。由 (b)，

$$ \tilde x^{\mathsf T}A\tilde y\le1. $$

乘回尺度得到

$$ x^{\mathsf T}Ay \le \|x\|_\infty\|y\|_\infty. $$

(c) 推出 (b) 也直接成立，因为连续立方体内的向量满足 $\|x\|_\infty,\|y\|_\infty\le1$。

最后说明绝对值形式。以 (a) 为例，若 $x^{\mathsf T}Ay\le1$ 对所有符号 $x,y$ 成立，则把 $x$ 替换为 $-x$ 得到 $-x^{\mathsf T}Ay\le1$，所以 $x^{\mathsf T}Ay\ge-1$。因此 $|x^{\mathsf T}Ay|\le1$。反向蕴含由 $x^{\mathsf T}Ay\le |x^{\mathsf T}Ay|$ 得到。其余两个形式同理。

证明思路

保留原证明结构，但不用 $\|G\mathbf1_{\{|G|>R\}}\|_2<2/R$。精确记下 Gaussian 尾部二阶矩 $q(R)^2$，并在最后优化 $R$。

完整证明

沿用 Theorem 3.5.1 第一种证明中的记号。令 $G\sim N(0,1)$，并记

$$ q(R)^2 := \mathbb E\left[G^2\mathbf1_{\{|G|>R\}}\right] = 2\left(R\varphi(R)+\mathbb P\{G>R\}\right), $$

其中 $\varphi(R)=(2\pi)^{-1/2}e^{-R^2/2}$。于是

$$ \|U_i^+\|_2=\|V_j^+\|_2=q(R), \qquad \|U_i^-\|_2=\|V_j^-\|_2=\sqrt{1-q(R)^2}. $$

截断后的主项仍满足

$$ S_-\le R^2. $$

对交叉项，把 $U_i^+$ 与 $V_j^-$ 看作 Hilbert 空间 $L^2$ 中的向量，并使用 $K=K(A)$ 的定义，得到

$$ S_{\pm} \le K\,q(R)\sqrt{1-q(R)^2}, \qquad S_{\mp} \le K\,q(R)\sqrt{1-q(R)^2}. $$

尾尾项同理满足

$$ S_+\le Kq(R)^2. $$

因此

$$ K \le R^2+ K\left( 2q(R)\sqrt{1-q(R)^2}+q(R)^2 \right). $$

只要括号中的系数小于 $1$，即可整理为

$$ K \le \frac{R^2} {1-2q(R)\sqrt{1-q(R)^2}-q(R)^2}. $$

取 $R=3.1$ 时，直接计算得 $q(R)\approx0.149$，从而

$$ \frac{R^2} {1-2q(R)\sqrt{1-q(R)^2}-q(R)^2} <14.1. $$

这就得到 $K\le14.1$。数值上，最优 $R$ 约为 $3.14$，但 $R=3.1$ 已足够给出书中声明的常数。

证明思路

先用 polarization identity 把双线性型写成两个二次型之差。PSD 保证二次型凸，因此在立方体上的最大值由顶点控制。

完整证明

(a) 由 $A=A^{\mathsf T}$，展开得

$$ \begin{aligned} \bar x^{\mathsf T}A\bar x-\bar y^{\mathsf T}A\bar y &= \frac14(x+y)^{\mathsf T}A(x+y) - \frac14(x-y)^{\mathsf T}A(x-y)\\ &= \frac14(2x^{\mathsf T}Ay+2y^{\mathsf T}Ax) = x^{\mathsf T}Ay. \end{aligned} $$

(b) 设 $q(z)=z^{\mathsf T}Az$。因为 $A\succeq0$，$q$ 是凸函数。凸函数在紧凸多面体 $[-1,1]^n$ 上的最大值可在极点取得，所以题设推出

$$ q(z)\le1 \qquad\text{for all }z\in[-1,1]^n. $$

对任意符号向量 $x,y\in\{-1,1\}^n$，令 $\bar x=(x+y)/2$、$\bar y=(x-y)/2$。它们都属于 $[-1,1]^n$。由 (a)，

$$ |x^{\mathsf T}Ay| \le q(\bar x)+q(\bar y) \le2. $$

因此矩阵 $A/2$ 满足 Grothendieck 不等式的双线性假设。对任意单位向量 $u_i,v_j$，

$$ \left| \sum_{i,j}\frac{a_{ij}}2\langle u_i,v_j\rangle \right| \le K. $$

乘以 $2$ 得到所需的 $2K$ 界。

(c) 若没有 PSD 假设，结论可能失败。取 $A=-MI_n$，其中 $M>0$ 可任意大。对任意符号 $x$，

$$ x^{\mathsf T}Ax=-Mn\le1, $$

所以题设成立。但取 $u_i=v_i$ 为同一个单位向量，得到

$$ \left| \sum_{i,j}a_{ij}\langle u_i,v_j\rangle \right| = Mn, $$

可随 $M$ 任意大，不可能由绝对常数控制。

证明思路

逐个坐标把点推到端点，separate convexity 保证函数值不下降。零对角二次型对每个坐标 separately affine，因此可把立方体内二次型控制还原到顶点控制。

完整证明

(a) 例子：$f(x,y)=xy$ 在每个单独变量上都是线性的，因此 separately convex，但它不是凸函数。

现在证明最大值结论。取任意 $x\in[-1,1]^n$。固定除 $x_1$ 外的所有坐标，函数作为 $x_1\in[-1,1]$ 的一元凸函数，其最大值可在 $x_1=\pm1$ 之一取得。因此可以把第一坐标推到端点且不降低函数值。依次对 $x_2,\ldots,x_n$ 做同样操作，最终得到某个顶点 $\varepsilon\in\{-1,1\}^n$，满足 $f(\varepsilon)\ge f(x)$。所以最大值可在顶点取得。

(b) 这里应把题目理解为对称零对角矩阵；如果 $A$ 非对称，二次型 $x^{\mathsf T}Ax$ 只能看见对称部分 $(A+A^{\mathsf T})/2$，无法控制斜对称部分。令

$$ q(z)=z^{\mathsf T}Az. $$

由于 $A$ 零对角，$q$ 对每个单独坐标都是仿射函数；因此 $q$ 和 $-q$ 都 separately convex。由 (a) 和题设，

$$ |q(z)|\le1 \qquad\text{for all }z\in[-1,1]^n. $$

对任意符号向量 $x,y$，由 polarization identity，

$$ x^{\mathsf T}Ay = q\left(\frac{x+y}{2}\right) - q\left(\frac{x-y}{2}\right). $$

两个参数都在 $[-1,1]^n$ 中，所以

$$ |x^{\mathsf T}Ay|\le2. $$

于是 $A/2$ 满足普通 Grothendieck 双线性假设。应用 Grothendieck 不等式并乘回 $2$，得到

$$ \left| \sum_{i,j}a_{ij}\langle u_i,v_j\rangle \right| \le 2K. $$

这也说明对称性不是无关细节：若允许非对称矩阵，则题设的二次型只控制对称部分，不能控制斜对称部分；上述双线性结论需要对称零对角假设或额外假设。

证明思路

Gram 矩阵的二次型是一个向量范数平方；反向用 Cholesky 分解或谱分解把 PSD 矩阵写成 $B^{\mathsf T}B$。

完整证明

(a) 设 $G_{ij}=\langle v_i,v_j\rangle$。由内积对称性可知 $G_{ij}=G_{ji}$。对任意 $c\in\mathbb R^n$，

$$ c^{\mathsf T}Gc = \sum_{i,j}c_ic_j\langle v_i,v_j\rangle = \left\|\sum_i c_iv_i\right\|_2^2 \ge0. $$

所以 $G\succeq0$。

(b) 反过来，若 $G\succeq0$，由谱分解可写

$$ G=Q\Lambda Q^{\mathsf T}, \qquad \Lambda\ge0. $$

令 $B=\Lambda^{1/2}Q^{\mathsf T}$，则 $G=B^{\mathsf T}B$。取 $v_i$ 为 $B$ 的第 $i$ 列，就有

$$ \langle v_i,v_j\rangle = (B^{\mathsf T}B)_{ij} = G_{ij}. $$

因此任意对称正半定矩阵都是某组向量的 Gram 矩阵。

证明思路

把所有 $X_i,Y_j$ 合并为一组单位向量，变量改为它们的 Gram 矩阵。PSD 与对角线为 $1$ 正好刻画单位向量 Gram 矩阵。

完整证明

(a) 令 $W_1,\ldots,W_{m+n}$ 表示合并后的向量，其中 $W_i=X_i$，$W_{m+j}=Y_j$。令

$$ Z_{\alpha\beta}=\langle W_\alpha,W_\beta\rangle. $$

由 Exercise 3.51，$Z\succeq0$，且单位长度约束等价于 $Z_{\alpha\alpha}=1$。目标函数为

$$ \sum_{i=1}^m\sum_{j=1}^n A_{ij}Z_{i,m+j}. $$

因此可写成 SDP：

$$ \begin{aligned} \operatorname{maximize}\quad& \sum_{i,j}A_{ij}Z_{i,m+j}\\ \text{subject to}\quad& Z\succeq0,\qquad Z_{\alpha\alpha}=1 \quad(\alpha=1,\ldots,m+n). \end{aligned} $$

(b) 记整数问题最优值为 $\operatorname{int}(A)$，SDP 最优值为 $\operatorname{sdp}(A)$。把符号解嵌入一维单位向量，得

$$ \operatorname{int}(A)\le\operatorname{sdp}(A). $$

另一方面，由于同时翻转所有 $x_i$ 会改变目标符号，$\operatorname{int}(A)$ 也控制绝对值最大值：

$$ \left| \sum_{i,j}A_{ij}x_iy_j \right| \le \operatorname{int}(A) \qquad(x_i,y_j=\pm1). $$

Grothendieck 不等式给出，对任意 SDP 可行向量，

$$ \left| \sum_{i,j}A_{ij}\langle X_i,Y_j\rangle \right| \le K\,\operatorname{int}(A). $$

取上确界即

$$ \operatorname{sdp}(A) \le K\,\operatorname{int}(A). $$

因此该松弛在绝对常数因子内近似原问题。

证明思路

只需看 $u,v$ 张成的二维平面。标准 Gaussian 的方向在圆上均匀，两个符号不同当且仅当方向落在两个夹角为 $\theta=\arccos\langle u,v\rangle$ 的楔形区域中。

完整证明

令 $\rho=\langle u,v\rangle$，并令 $\theta=\arccos\rho\in[0,\pi]$。由于只涉及 $u,v$ 张成的二维子空间，可把问题化到平面中。标准 Gaussian $g$ 的方向在单位圆上均匀。

符号 $\operatorname{sign}\langle g,u\rangle$ 与 $\operatorname{sign}\langle g,v\rangle$ 不同，恰好表示方向 $g/\|g\|_2$ 被两条过原点、法向分别为 $u,v$ 的直线分到不同半平面。这样的方向总角度为 $2\theta$，因此

$$ \mathbb P\{\text{signs differ}\} = \frac{2\theta}{2\pi} = \frac{\theta}{\pi}. $$

于是

$$ \begin{aligned} \mathbb E \operatorname{sign}\langle g,u\rangle \operatorname{sign}\langle g,v\rangle &= \mathbb P\{\text{same}\} - \mathbb P\{\text{different}\}\\ &= 1-\frac{2\theta}{\pi} = 1-\frac{2\arccos\rho}{\pi}\\ &= \frac{2}{\pi}\arcsin\rho. \end{aligned} $$

这就是 Grothendieck identity。

证明思路

重复独立随机超平面舍入，直到割值超过已知阈值 $(0.878-\varepsilon)\operatorname{sdp}(G)$。期望保证和割值上界给出每轮成功概率的正下界。

完整证明

先求解最大割 SDP，记其值为 $S$。反复执行 Goemans-Williamson 随机超平面舍入，得到割值 $W$。Theorem 3.6.4 给出

$$ \mathbb EW\ge\alpha S, \qquad \alpha=0.878. $$

同时任何割值都不超过 $\operatorname{maxcut}(G)\le S$，所以 $0\le W\le S$。令

$$ p=\mathbb P\{W\ge(\alpha-\varepsilon)S\}. $$

若失败，则 $W<(\alpha-\varepsilon)S$；若成功，则至多为 $S$。因此

$$ \alpha S \le \mathbb EW \le pS+(1-p)(\alpha-\varepsilon)S. $$

整理得

$$ p \ge \frac{\varepsilon}{1-\alpha+\varepsilon}. $$

算法每轮检查割值是否达到 $(\alpha-\varepsilon)S$，达到就输出。输出一定是一个有效割，并且因为 $S\ge\operatorname{maxcut}(G)$，它是 $(0.878-\varepsilon)$ 近似。重复次数服从成功概率至少为 $p$ 的几何型随机变量，所以期望重复次数至多

$$ \frac1p \le \frac{1-\alpha+\varepsilon}{\varepsilon} \le \frac{1}{\varepsilon}. $$

证明思路

对每个幂 $x^k$ 使用张量特征 $u^{\otimes k}$。正系数放同号，负系数在 $\Psi$ 中放一个负号。无限级数用 $\ell^2$ 直和承载。

完整证明

设

$$ f(x)=\sum_{k=0}^{\infty}a_kx^k. $$

因为幂级数对所有实数收敛，其收敛半径为无穷大，特别地 $\sum_k|a_k|<\infty$。令 Hilbert 空间为张量空间的 Hilbert 直和

$$ H=\bigoplus_{k=0}^{\infty}(\mathbb R^n)^{\otimes k}, $$

其中 $k=0$ 项理解为一维实数空间。定义

$$ \Phi(u) = \bigoplus_{k=0}^{\infty} \sqrt{|a_k|}\,u^{\otimes k}, \qquad \Psi(v) = \bigoplus_{k=0}^{\infty} \operatorname{sign}(a_k)\sqrt{|a_k|}\,v^{\otimes k}. $$

这里 $a_k=0$ 时对应分量取 $0$。由于

$$ \langle u^{\otimes k},v^{\otimes k}\rangle = \langle u,v\rangle^k, $$

得到

$$ \langle\Phi(u),\Psi(v)\rangle = \sum_{k=0}^{\infty} a_k\langle u,v\rangle^k = f(\langle u,v\rangle). $$

若 $\|u\|_2=1$，则

$$ \|\Phi(u)\|_2^2 = \sum_{k=0}^{\infty}|a_k|\|u^{\otimes k}\|_2^2 = \sum_{k=0}^{\infty}|a_k|, $$

同理 $\|\Psi(u)\|_2^2=\sum_k|a_k|$。这证明了 Lemma 3.7.7。

证明思路

对二元 Gaussian 使用条件期望：$\mathbb E[\langle g,u\rangle\mid\langle g,v\rangle]=\langle u,v\rangle\langle g,v\rangle$。然后展开 $Z_uZ_v$。

完整证明

(a) 令 $X=\langle g,u\rangle$、$Y=\langle g,v\rangle$，则 $(X,Y)$ 是标准二元正态，相关系数 $\rho=\langle u,v\rangle$。Gaussian 条件期望给出

$$ \mathbb E[X\mid Y]=\rho Y. $$

因此

$$ \mathbb E X\operatorname{sign}(Y) = \mathbb E\left[\mathbb E[X\mid Y]\operatorname{sign}(Y)\right] = \rho\,\mathbb E|Y| = \sqrt{\frac2\pi}\rho. $$

这就是 (a)。

(b) 记 $a=\sqrt{2/\pi}$。展开

$$ Z_uZ_v = (aX-\operatorname{sign}X) (aY-\operatorname{sign}Y). $$

取期望，并使用 (a) 及 $\mathbb EXY=\rho$，得到

$$ \begin{aligned} \mathbb E Z_uZ_v &= a^2\rho - a\,\mathbb E X\operatorname{sign}Y - a\,\mathbb E Y\operatorname{sign}X + \mathbb E\operatorname{sign}X\operatorname{sign}Y\\ &= \frac2\pi\rho - \frac2\pi\rho - \frac2\pi\rho + \mathbb E\operatorname{sign}X\operatorname{sign}Y. \end{aligned} $$

整理即

$$ \mathbb E \operatorname{sign}\langle g,u\rangle \operatorname{sign}\langle g,v\rangle = \frac2\pi\langle u,v\rangle + \mathbb E[Z_uZ_v]. $$

证明思路

对单位向量 $u_i$ 做随机超平面舍入。Exercise 3.56 把符号相关写成线性项加上一个 Gram 型误差项；PSD 矩阵与 Gram 矩阵的内积非负，因此可丢掉误差项。

完整证明

设

$$ S=\sum_{i,j}a_{ij}\langle u_i,u_j\rangle. $$

取标准 Gaussian 向量 $g$，令 $x_i=\operatorname{sign}\langle g,u_i\rangle$。对每个 $g$，$x_i\in\{-1,1\}$，所以题设给出

$$ \sum_{i,j}a_{ij}x_ix_j\le1. $$

取期望并用 Exercise 3.56(b)，

$$ \begin{aligned} 1 &\ge \mathbb E\sum_{i,j}a_{ij}x_ix_j\\ &= \frac2\pi \sum_{i,j}a_{ij}\langle u_i,u_j\rangle + \sum_{i,j}a_{ij}\mathbb E[Z_{u_i}Z_{u_j}]\\ &= \frac2\pi S + \sum_{i,j}a_{ij}\langle Z_{u_i},Z_{u_j}\rangle_{L^2}. \end{aligned} $$

矩阵 $(\langle Z_{u_i},Z_{u_j}\rangle_{L^2})$ 是 Gram 矩阵，因此正半定。由于 $A\succeq0$，两个正半定矩阵的 Frobenius 内积非负，所以最后一项非负。于是

$$ 1\ge\frac2\pi S, $$

即

$$ \sum_{i,j}a_{ij}\langle u_i,u_j\rangle \le \frac{\pi}{2}. $$

证明思路

上界直接把 Exercise 3.57 应用于归一化矩阵 $A/\operatorname{int}(A)$。算法仍用随机超平面舍入；Exercise 3.56 的误差项非负，给出期望值至少为 $(2/\pi)$ 倍 SDP 值。

完整证明

(a) 记 $\alpha=\operatorname{int}(A)$。任意整数解 $x_i=\pm1$ 可嵌入为一维单位向量 $X_i=x_i$，所以

$$ \operatorname{int}(A)\le\operatorname{sdp}(A). $$

若 $\alpha=0$，由于 $A\succeq0$，所有符号向量都满足 $x^{\mathsf T}Ax\ge0$，所以实际上 $x^{\mathsf T}Ax=0$。PSD 二次型在立方体上的最大值可在顶点取得，因此 $z^{\mathsf T}Az=0$ 对所有 $z\in[-1,1]^n$ 成立，进而由齐次性和极化可得 $A=0$，所以 $\operatorname{sdp}(A)=0$。下面设 $\alpha>0$。矩阵 $A/\alpha$ 满足 Exercise 3.57 的假设。于是对任意 SDP 可行单位向量 $X_i$，

$$ \sum_{i,j}\frac{a_{ij}}{\alpha} \langle X_i,X_j\rangle \le \frac{\pi}{2}. $$

乘回 $\alpha$ 并对所有 SDP 可行解取上确界，得到

$$ \operatorname{sdp}(A) \le \frac{\pi}{2}\operatorname{int}(A). $$

(b) 设 $(X_i)$ 是 SDP 最优解，令 $S=\operatorname{sdp}(A)$。抽取标准 Gaussian 向量 $g$，并输出

$$ x_i=\operatorname{sign}\langle g,X_i\rangle. $$

由 Exercise 3.56(b)，

$$ \mathbb E x_ix_j = \frac2\pi\langle X_i,X_j\rangle + \mathbb E[Z_{X_i}Z_{X_j}]. $$

因此

$$ \begin{aligned} \mathbb E\sum_{i,j}a_{ij}x_ix_j &= \frac2\pi \sum_{i,j}a_{ij}\langle X_i,X_j\rangle + \sum_{i,j}a_{ij}\mathbb E[Z_{X_i}Z_{X_j}]\\ &\ge \frac2\pi S, \end{aligned} $$

因为第二项是 PSD 矩阵 $A$ 与一个 Gram 矩阵的内积，非负。由于 $S\ge\operatorname{int}(A)$，该随机舍入在期望意义下给出至少 $(2/\pi)\operatorname{int}(A)$ 的目标值，也就是 $\pi/2$ 近似。