证明思路

先把乘积事件转成指数变量之和的小偏差事件。下界使用事件 $\{X_i\ge1/2,\ \forall i\}$，它包含在 $\{Y_n\ge \mathbb EY_n\}$ 中；上界用指数矩方法处理 $\sum_i-\log X_i$。

完整证明

由于 $X_i\sim\operatorname{Unif}[0,1]$ 且相互独立，

$$ \mathbb E Y_n=\prod_{i=1}^n\mathbb E X_i=2^{-n}. $$

若所有 $X_i\ge1/2$，则 $Y_n\ge2^{-n}$，因此

$$ \mathbb P\{Y_n\ge\mathbb EY_n\}\ge\mathbb P\{X_i\ge1/2\ \forall i\}=2^{-n}. $$

令 $Z_i=-\log X_i$。则 $Z_i$ 独立且服从参数为 $1$ 的指数分布，并且

$$ \{Y_n\ge2^{-n}\}=\left\{\sum_{i=1}^n Z_i\le n\log2\right\}. $$

对任意 $\lambda>0$，Markov 不等式给出

$$ \mathbb P\left\{\sum_iZ_i\le n\log2\right\} = \mathbb P\left\{e^{-\lambda\sum_iZ_i}\ge e^{-\lambda n\log2}\right\} \le \left(\frac{2^\lambda}{1+\lambda}\right)^n. $$

取 $\lambda=1/\log2-1$，括号中的常数约为 $0.942<0.95$。于是

$$ \mathbb P\{Y_n\ge\mathbb EY_n\}\le(0.95)^n. $$

证明思路

把“左边减右边”看成 $t$ 的函数，证明它单调下降到 $0$。这样每个有限 $t$ 处函数值都非负。

完整证明

记标准正态密度为 $f(t)=(2\pi)^{-1/2}e^{-t^2/2}$，并令

$$ F(t)=\mathbb P\{g\ge t\}-\frac{t}{t^2+1}f(t). $$

当 $t\to\infty$ 时，Gaussian tail 和 $\frac{t}{t^2+1}f(t)$ 都趋于 $0$，所以 $F(t)\to0$。下面求导。由 $f'(t)=-tf(t)$，

$$ F'(t) = -f(t) - \left(\frac{t}{t^2+1}f(t)\right)' = -\frac{2f(t)}{(t^2+1)^2}<0. $$

所以 $F$ 单调递减且极限为 $0$。因此对所有 $t>0$，$F(t)\ge0$，即

$$ \mathbb P\{g\ge t\}\ge \frac{t}{t^2+1}f(t). $$

证明思路

把上尾积分写成标准正态密度 $f(t)$ 乘上一个修正因子。因为 $f'(x)=-xf(x)$，每次分部积分都会从尾积分中剥离一个 $1/t$、$1/t^3$、$1/t^5$ 等项。

完整证明

设

$$ f(x)=\frac1{\sqrt{2\pi}}e^{-x^2/2}, \qquad \overline\Phi(t)=\mathbb P\{g>t\}=\int_t^\infty f(x)\,dx. $$

Mills ratio 是

$$ R(t)=\frac{\overline\Phi(t)}{f(t)}. $$

第一次分部积分使用 $f(x)=-f'(x)/x$：

$$ \overline\Phi(t) = -\int_t^\infty \frac1x f'(x)\,dx = \frac{f(t)}{t} - \int_t^\infty \frac{f(x)}{x^2}\,dx. $$

这已经说明 $R(t)=t^{-1}+O(t^{-3})$。第二次对余项做同样处理：

$$ \int_t^\infty \frac{f(x)}{x^2}\,dx = -\int_t^\infty x^{-3}f'(x)\,dx = \frac{f(t)}{t^3} - 3\int_t^\infty \frac{f(x)}{x^4}\,dx. $$

代回得到

$$ \overline\Phi(t) = f(t)\left(\frac1t-\frac1{t^3}\right) + 3\int_t^\infty \frac{f(x)}{x^4}\,dx. $$

余项为正，所以

$$ \frac1t-\frac1{t^3} \le R(t) \le \frac1t. $$

继续递推。令 $I_m(t)=\int_t^\infty x^{-2m}f(x)\,dx$。同样分部积分得到

$$ I_m(t) = \frac{f(t)}{t^{2m+1}}-(2m+1)I_{m+1}(t). $$

把这个递推代回 $I_0(t)$，得到

$$ \frac{\mathbb P\{g>t\}}{f(t)} = \frac1t-\frac1{t^3}+\frac{1\cdot3}{t^5}-\cdots +(-1)^m\frac{1\cdot3\cdots(2m-1)}{t^{2m+1}} +R_m(t), $$

其中余项 $R_m(t)$ 的符号与下一项一致，因为它是正数 $I_{m+1}(t)$ 乘上显式符号。于是任意两个相邻部分和把真实 Mills ratio 夹住。特别地，取前三项就得到 (2.30)。

证明思路

两问都只用 $f'(x)=-xf(x)$。一阶矩直接积分，二阶矩分部积分后套 Gaussian tail 上界。

完整证明

对 $t>0$，

$$ \mathbb E[g\mathbf1_{\{g>t\}}] = \int_t^\infty xf(x)\,dx = \int_t^\infty -f'(x)\,dx = f(t). $$

再计算二阶截断矩：

$$ \mathbb E[g^2\mathbf1_{\{g>t\}}] = \int_t^\infty x^2f(x)\,dx = \int_t^\infty x[-f'(x)]\,dx = tf(t)+\int_t^\infty f(x)\,dx. $$

由 Proposition 2.1.2 的上界，$\int_t^\infty f(x)\,dx\le f(t)/t$。因此

$$ \mathbb E[g^2\mathbf1_{\{g>t\}}]\le\left(t+\frac1t\right)f(t). $$

证明思路

比较两个偶函数的 Taylor 展开即可。指数函数每个偶次项的系数都不小于 $\cosh$ 的对应系数。

完整证明

展开得到

$$ \cosh x=\sum_{k=0}^\infty\frac{x^{2k}}{(2k)!}, \qquad e^{x^2/2}=\sum_{k=0}^\infty\frac{x^{2k}}{2^kk!}. $$

对每个 $k\ge0$，有

$$ (2k)!=1\cdot2\cdots(2k)\ge 2\cdot4\cdots(2k)=2^kk!. $$

所以 $1/(2k)!\le1/(2^kk!)$。逐项比较非负级数，得到 $\cosh x\le e^{x^2/2}$。

证明思路

这和 Hoeffding 的证明完全同型：指数化尾事件，套 Markov，再优化参数。

完整证明

对任意 $\lambda>0$，

$$ \mathbb P\{g\ge t\} = \mathbb P\{e^{\lambda g}\ge e^{\lambda t}\} \le e^{-\lambda t}\mathbb E e^{\lambda g}. $$

标准正态的 MGF 为 $\mathbb E e^{\lambda g}=e^{\lambda^2/2}$，因此

$$ \mathbb P\{g\ge t\}\le\exp\left(-\lambda t+\frac{\lambda^2}{2}\right). $$

右侧在 $\lambda=t$ 处最小，得到 $\mathbb P\{g\ge t\}\le e^{-t^2/2}$。

证明思路

小球事件是下尾事件，对 $e^{-\lambda\sum X_i}$ 使用 Markov。密度有界给出 Laplace transform 的统一控制。

完整证明

对 $\lambda>0$，

$$ \mathbb P\left\{\sum_{i=1}^NX_i\le\varepsilon N\right\} \le e^{\lambda\varepsilon N}\prod_{i=1}^N\mathbb E e^{-\lambda X_i}. $$

因为 $X_i$ 非负且密度 $f_i$ 满足 $f_i\le K$，

$$ \mathbb E e^{-\lambda X_i} = \int_0^\infty e^{-\lambda x}f_i(x)\,dx \le \frac K\lambda. $$

所以概率不超过 $e^{\lambda\varepsilon N}(K/\lambda)^N$。取 $\lambda=1/\varepsilon$，得到

$$ \mathbb P\left\{\sum_iX_i\le\varepsilon N\right\}\le(eK\varepsilon)^N. $$

证明思路

指数函数是凸函数，区间上凸函数位于端点弦线之下。取期望后，端点权重只由均值决定。

完整证明

对 $x\in[a,b]$，凸性给出

$$ e^{\lambda x} \le \frac{b-x}{b-a}e^{\lambda a} + \frac{x-a}{b-a}e^{\lambda b}. $$

取 $X$ 的期望，得到

$$ \mathbb E e^{\lambda X} \le \frac{b-\mathbb EX}{b-a}e^{\lambda a} + \frac{\mathbb EX-a}{b-a}e^{\lambda b}. $$

若 $Y$ 取值于 $\{a,b\}$ 且 $\mathbb EY=\mathbb EX$，则 $\mathbb P\{Y=b\}=(\mathbb EX-a)/(b-a)$，上式正是 $\mathbb E e^{\lambda Y}$。

证明思路

先平移缩放到均值为 $0$、区间长度为 $1$，再用 Exercise 2.8 化到两点分布。两点分布的 cumulant 二阶导数是 Bernoulli 方差，最多为 $1/4$。

完整证明

平移不会改变 $X-\mathbb EX$，缩放只把 $\lambda$ 改成 $\lambda(b-a)$，所以只需证明 $\mathbb EX=0$ 且 $b-a=1$ 的情形。由 Exercise 2.8，可进一步假设 $X$ 只取端点 $a,b$。

设 $K(\lambda)=\log\mathbb E e^{\lambda X}$。因为 $\mathbb EX=0$，$K(0)=K'(0)=0$。在指数倾斜分布下，

$$ K''(\lambda)=\operatorname{Var}_\lambda(X)\le\frac{(b-a)^2}{4}=\frac14. $$

Taylor 公式给出

$$ K(\lambda)=\int_0^\lambda(\lambda-s)K''(s)\,ds\le\frac{\lambda^2}{8}. $$

还原尺度，得到

$$ \mathbb E e^{\lambda(X-\mathbb EX)} \le \exp\left(\frac{\lambda^2(b-a)^2}{8}\right). $$

证明思路

对中心化和使用 Chernoff bound；独立性分解 MGF；每项用 Hoeffding lemma 控制；最后优化 $\lambda$ 并对左右尾合并。

完整证明

令 $S=\sum_i(X_i-\mathbb EX_i)$。对 $\lambda>0$，

$$ \mathbb P\{S\ge t\} \le e^{-\lambda t}\prod_i\mathbb E e^{\lambda(X_i-\mathbb EX_i)} \le \exp\left(-\lambda t+\frac{\lambda^2}{8}\sum_i(b_i-a_i)^2\right). $$

右侧对 $\lambda$ 最小化，取 $\lambda=4t/\sum_i(b_i-a_i)^2$，得到

$$ \mathbb P\{S\ge t\} \le \exp\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right). $$

把 $X_i$ 换成 $-X_i$ 得到左尾同样的界。合并左右尾即为 Theorem 2.2.6。

证明思路

左尾用负的指数参数。因为 $\lambda<0$ 时 $e^{\lambda x}$ 是递减函数，事件 $S_N\le t$ 会变成上尾事件。

完整证明

对 $\lambda<0$，

$$ \mathbb P\{S_N\le t\} = \mathbb P\{e^{\lambda S_N}\ge e^{\lambda t}\} \le e^{-\lambda t}\mathbb E e^{\lambda S_N}. $$

Bernoulli 和满足

$$ \mathbb E e^{\lambda S_N} = \prod_i(1-p_i+p_ie^\lambda) \le \exp\{\mu(e^\lambda-1)\}. $$

令 $e^\lambda=t/\mu$，也就是 $\lambda=\log(t/\mu)\le0$，得到

$$ \mathbb P\{S_N\le t\} \le \exp\{-\mu+t-t\log(t/\mu)\} = e^{-\mu}\left(\frac{e\mu}{t}\right)^t. $$

证明思路

直接估计二项分布质量函数。组合数给出 $(N/t)^t$，剩下的 $(1-\mu/N)^{N-t}$ 用一个基础对数不等式下界为 $e^{-\mu}$。

完整证明

对整数 $t\in[\mu,N]$，

$$ \mathbb P\{S_N=t\} = \binom Nt\left(\frac{\mu}{N}\right)^t \left(1-\frac{\mu}{N}\right)^{N-t}. $$

使用 $\binom Nt\ge(N/t)^t$，前两项给出 $(\mu/t)^t$。令 $x=\mu/N$。由于 $t\ge\mu$，有 $N-t\le N(1-x)$，且 $0\le x\le1$，于是

$$ (1-x)^{N-t}\ge (1-x)^{N(1-x)}. $$

函数 $(1-x)\log(1-x)+x$ 在 $[0,1)$ 上非负，所以 $(1-x)^{N(1-x)}\ge e^{-Nx}=e^{-\mu}$。因此

$$ \mathbb P\{S_N=t\}\ge e^{-\mu}\left(\frac{\mu}{t}\right)^t. $$

证明思路

Poisson 的 MGF 与 Bernoulli 和的 Chernoff 上界有相同形式，因此右尾和左尾优化完全相同。点概率直接用 $t!\le t^t$。

完整证明

若 $X\sim\operatorname{Pois}(\mu)$，则

$$ \mathbb E e^{\lambda X}=\exp\{\mu(e^\lambda-1)\}. $$

右尾中取 $\lambda>0$，Markov 给出

$$ \mathbb P\{X\ge t\}\le \exp\{-\lambda t+\mu(e^\lambda-1)\}. $$

当 $t\ge\mu$ 时取 $e^\lambda=t/\mu$，得到 $e^{-\mu}(e\mu/t)^t$。左尾同理取 $\lambda<0$，当 $0<t\le\mu$ 时同样得到 $e^{-\mu}(e\mu/t)^t$。

小偏差形式由 Exercise 2.14 的数值不等式直接推出。最后，若 $t$ 是正整数，

$$ \mathbb P\{X=t\}=e^{-\mu}\frac{\mu^t}{t!}\ge e^{-\mu}\left(\frac{\mu}{t}\right)^t, $$

因为 $t!\le t^t$。

证明思路

右尾从 Chernoff 精确指数化简；左尾使用负参数版本。关键只剩两个一元函数不等式。

完整证明

右尾由 Theorem 2.3.1 得到

$$ \mathbb P\{S_N\ge(1+\delta)\mu\} \le \exp\{-\mu[(1+\delta)\log(1+\delta)-\delta]\}. $$

直接求导可验证，对所有 $\delta\ge0$，

$$ (1+\delta)\log(1+\delta)-\delta\ge\frac{\delta^2}{2+\delta}. $$

所以右尾不超过 $\exp[-\delta^2\mu/(2+\delta)]$。

当 $0\le\delta<1$ 时，左尾由 Exercise 2.11 得到

$$ \mathbb P\{S_N\le(1-\delta)\mu\} \le \exp\{-\mu[\delta+(1-\delta)\log(1-\delta)]\}. $$

同样的微积分给出 $\delta+(1-\delta)\log(1-\delta)\ge\delta^2/2$，这强于所需界。$\delta=1$ 由极限得到，若 $\delta>1$，左尾事件为空。合并左右尾即得

$$ \mathbb P\{|S_N-\mu|\ge\delta\mu\} \le 2\exp\left(-\frac{\delta^2\mu}{2+\delta}\right). $$

证明思路

把 $e^{\lambda x}$ 在 $[0,1]$ 上用端点弦控制。这样每个 $X_i$ 的 MGF 都不超过同均值 Bernoulli 变量的 MGF。

完整证明

若 $X_i\in[0,1]$ 且 $\mathbb EX_i=p_i$，则对 $\lambda\in\mathbb R$，凸性给出

$$ e^{\lambda X_i}\le 1-X_i+X_i e^\lambda. $$

取期望得

$$ \mathbb E e^{\lambda X_i}\le1-p_i+p_ie^\lambda. $$

这正是 $\operatorname{Ber}(p_i)$ 的 MGF 上界。由于 Chernoff、左尾和小偏差证明只用到了独立性和这个 MGF 控制，三种结论对独立 $[0,1]$ 变量原样成立。

证明思路

把分组数取为与 $t^2$ 同阶的整数，丢弃少量样本或允许最后一组不用。所有估计只损失绝对常数。

完整证明

若 $t$ 很小，例如 $t<4$，结论可通过调小指数常数平凡保证。下面设 $t\ge4$，并取

$$ B=\left\lfloor\frac{t^2}{16}\right\rfloor, \qquad m=\left\lfloor\frac NB\right\rfloor. $$

此时 $1\le B\asymp t^2$。因为 $t\le\sqrt N$，有 $B\le N/16$，所以 $m\ge N/(2B)$。使用前 $mB$ 个样本分成 $B$ 组，每组均值为 $Z_j$。Chebyshev 给出

$$ \mathbb P\{|Z_j-\mu|>t\sigma/\sqrt N\} \le \frac{\sigma^2/m}{t^2\sigma^2/N} \le \frac{2B}{t^2} \le \frac18. $$

于是坏组数被 $\operatorname{Binom}(B,1/8)$ 随机变量支配。Chernoff 或 Hoeffding 不等式给出坏组至少一半的概率不超过 $e^{-cB}\le e^{-c't^2}$。中位数落出区间只能在坏组至少一半时发生，证明完成。这里 $c'$ 与原定理中的绝对常数合并。

证明思路

选择两个均值相距 $\mu$ 的 Laplace 平移族。假设估计量在两个模型下都给出过强置信界，再用似然比比较把第二个模型的高概率事件转移到第一个模型下，最后得到两个互斥事件同时高概率发生的矛盾。

完整证明

设 $X_i\sim\operatorname{Lap}(0,1)$，$Y_i\sim\operatorname{Lap}(\mu,1)$ 独立。Laplace 密度满足

$$ \frac{f_0(x)}{f_\mu(x)} = \exp(|x-\mu|-|x|) \le e^\mu. $$

坐标独立，所以对任意可测 $B\subset\mathbb R^N$，

$$ \mathbb P\{\mathbf X\in B\}\le e^{N\mu}\mathbb P\{\mathbf Y\in B\}. $$

反设断言成立。Laplace 分布方差为绝对常数 $2$。令 $t=\mu\sqrt N/(2\sqrt2)$，则断言给出

$$ \mathbb P_{\mathbf X}\{|\widehat\mu|\ge\mu/2\}\le 2e^{-c\mu^2N/8}, $$

且

$$ \mathbb P_{\mathbf Y}\{|\widehat\mu-\mu|\ge\mu/2\}\le 2e^{-c\mu^2N/8}. $$

由似然比比较，

$$ \mathbb P_{\mathbf X}\{|\widehat\mu-\mu|\ge\mu/2\} \le 2\exp(N\mu-c\mu^2N/8). $$

选取足够大的绝对常数 $\mu$，可使上面两个失败概率之和小于 $1$。于是同一个 $\mathbf X$ 下，事件 $|\widehat\mu|<\mu/2$ 和 $|\widehat\mu-\mu|<\mu/2$ 同时发生的概率为正。但这两个严格事件由三角不等式互斥，矛盾。因此断言不成立。

证明思路

固定顶点度数是二项变量，Chernoff 控制一个顶点异常的概率。再对异常顶点个数取期望，用 Markov 控制异常比例。

完整证明

固定顶点 $v$，其度数 $D_v\sim\operatorname{Binom}(n-1,p)$，均值为 $d$。Chernoff 小偏差给出

$$ \mathbb P\{|D_v-d|>0.1d\}\le2e^{-cd} $$

其中 $c>0$ 为绝对常数。令 $Z$ 为异常顶点个数，则

$$ \mathbb EZ=\sum_v\mathbb P\{v\text{ 异常}\}\le2ne^{-cd}. $$

选择 $C$ 足够大，使 $d\ge C$ 时 $2e^{-cd}\le10^{-4}$。于是 $\mathbb EZ\le10^{-4}n$。由 Markov 不等式，

$$ \mathbb P\{Z>0.01n\}\le\frac{10^{-4}n}{0.01n}=0.01. $$

因此至少以 $0.99$ 的概率，异常顶点不超过 $1\%$，也就是至少 $99\%$ 顶点的度数位于 $[0.9d,1.1d]$。

证明思路

上界用固定顶点二项尾界加并集界。下界把顶点分成两半，只看一半顶点到另一半的度数；这些度数独立，再用二项点概率下界和独立重复。

完整证明

审校注：原题/OCR 的字面条件只写了 $d\le c(\log n)^{0.99}$。若允许 $d=0$，则图没有边，$\Delta(G)=0$，题中正的下界不可能成立。因此下界证明必须在通常的非退化稀疏情形下理解，例如假设 $d\ge d_0>0$ 为绝对常数。上界不需要这个下界。

记 $L=A\log n/\log\log n$。对固定顶点，Chernoff 粗界给出

$$ \mathbb P\{D_v\ge L\}\le\left(\frac{ed}{L}\right)^L. $$

若 $A$ 足够大且 $c$ 足够小，则由 $d\le c(\log n)^{0.99}$ 可得 $(ed/L)^L\le n^{-3}$。并集界给出 $\Delta(G)\le L$ 的概率至少 $1-n^{-2}$，特别大于 $0.995$。

下界取 $L=a\log n/\log\log n$，其中 $a>0$ 足够小。把顶点分成两个大小至少 $n/3$ 的集合 $U,W$。对每个 $v\in U$，令 $D_v^W$ 为 $v$ 到 $W$ 的边数。变量 $D_v^W$ 在 $v\in U$ 上相互独立，且 $D_v^W\sim\operatorname{Binom}(|W|,p)$，均值与 $d$ 同阶；在 $d\ge d_0$ 时，这个均值也有绝对正下界。

由二项点概率下界，

$$ \mathbb P\{D_v^W\ge L\} \ge \mathbb P\{D_v^W=L\} \ge \exp[-o(\log n)]\left(\frac{c'd}{L}\right)^L. $$

在 $d\le c(\log n)^{0.99}$ 且 $a,c$ 足够小时，右侧至少为 $n^{-1/2}$（把常数留足即可）。于是期望个数

$$ \mathbb E\#\{v\in U:D_v^W\ge L\}\ge c n^{1/2}. $$

这些事件独立，所以没有任何一个发生的概率至多 $\exp(-c n^{1/2})$。因此以概率至少 $0.995$，存在顶点 $v$ 满足 $D_v^W\ge L$，从而 $\Delta(G)\ge L$。合并上下界并调整绝对常数，即得题设的 $0.99$ 概率结论。

证明思路

固定 $S,T$ 时，边数是 Bernoulli 和；Chernoff 给出指数为 $p|S||T|$ 的失败概率。条件 $|S||T|\ge Cn/p$ 让这个指数压过所有集合对的数量。

完整证明

固定互不相交的 $S,T$，令 $s=|S|,t=|T|$。则

$$ e(S,T)\sim\operatorname{Binom}(st,p), \qquad \mathbb E e(S,T)=pst. $$

Chernoff 小偏差给出

$$ \mathbb P\{|e(S,T)-pst|>0.1pst\}\le2e^{-cpst}. $$

所有有序不交对 $(S,T)$ 的数量不超过 $3^n$，因为每个顶点有三种选择：进 $S$、进 $T$ 或都不进。若 $st\ge Cn/p$，则 $pst\ge Cn$。对所有满足条件的集合对取并集界，失败概率至多

$$ 2\cdot3^n e^{-cCn}. $$

选择 $C$ 足够大，使该值不超过 $2^{-n}$。补事件上对所有这样的 $S,T$ 同时有

$$ 0.9p\le\frac{e(S,T)}{|S||T|}\le1.1p. $$

证明思路

把每次运行是否正确记为 Bernoulli 变量。多数投票失败就是 Bernoulli 和低于其均值 $\varepsilon N$，直接套 Hoeffding。

完整证明

令 $Y_i$ 表示第 $i$ 次运行正确，则 $\mathbb EY_i=1/2+\varepsilon$。多数投票失败意味着

$$ \sum_{i=1}^NY_i\le\frac N2 = \mathbb E\sum_{i=1}^NY_i-\varepsilon N. $$

Hoeffding 不等式给出

$$ \mathbb P\{\text{多数投票失败}\} \le \exp(-2\varepsilon^2N). $$

若 $N\ge(2\varepsilon^2)^{-1}\log(1/\delta)$，右侧至多为 $\delta$。因此多数投票至少以 $1-\delta$ 的概率正确。

证明思路

偶对称性把积分化到正半轴；换元 $u=x^2/2$ 得到 Gamma 函数。渐近用 Stirling 公式。

完整证明

对 $p\ge1$，

$$ \mathbb E|g|^p = \frac{2}{\sqrt{2\pi}}\int_0^\infty x^p e^{-x^2/2}\,dx. $$

令 $u=x^2/2$，即 $x=(2u)^{1/2}$，$dx=(2u)^{-1/2}du$，得到

$$ \mathbb E|g|^p = \frac{2^{p/2}}{\sqrt\pi}\Gamma\left(\frac{p+1}{2}\right). $$

令 $z=(p-1)/2$。由 Stirling 公式 $\Gamma(z+1)=\sqrt{2\pi z}(z/e)^z(1+o(1))$，取 $p$ 次方根后，多项式因子贡献趋于 $1$，于是

$$ \|g\|_{L^p} = \left(\mathbb E|g|^p\right)^{1/p} = \sqrt{\frac pe}\,(1+o(1)). $$

证明思路

在 $\lambda=0$ 附近比较一阶项。正参数给出 $\mathbb EX\le0$，负参数给出 $\mathbb EX\ge0$。

完整证明

若对所有 $\lambda\in\mathbb R$，

$$ \mathbb E e^{\lambda X}\le e^{K^2\lambda^2}, $$

则对 $\lambda>0$，

$$ \frac{\mathbb E e^{\lambda X}-1}{\lambda} \le \frac{e^{K^2\lambda^2}-1}{\lambda}. $$

令 $\lambda\downarrow0$ 得 $\mathbb EX\le0$。对 $\lambda<0$ 作同样处理，或者令 $\lambda=-s$ 后让 $s\downarrow0$，得到 $\mathbb EX\ge0$。因此 $\mathbb EX=0$。

证明思路

全部从定义出发：求使 $\mathbb E\exp(X^2/K^2)\le2$ 成立的最小 $K$。

完整证明

若 $X=c$ a.s.，条件为 $e^{c^2/K^2}\le2$，故 $\|X\|_{\psi_2}=|c|/\sqrt{\log2}$。若 $|X|\le\|X\|_\infty$，则由单调性

$$ \|X\|_{\psi_2}\le\frac{\|X\|_\infty}{\sqrt{\log2}}. $$

Rademacher 变量满足 $X^2=1$，所以范数为 $1/\sqrt{\log2}$。

若 $X\sim N(0,\sigma^2)$，则对 $K^2>2\sigma^2$，

$$ \mathbb E e^{X^2/K^2} = \left(1-\frac{2\sigma^2}{K^2}\right)^{-1/2}. $$

令该值等于 $2$，得 $1-2\sigma^2/K^2=1/4$，即 $K=\sigma\sqrt{8/3}$。

若 $X\sim\operatorname{Ber}(p)$，则 $X^2=X$，条件为

$$ 1-p+p e^{1/K^2}\le2. $$

等号给出 $e^{1/K^2}=1+1/p$，故

$$ \|X\|_{\psi_2}=\frac1{\sqrt{\log(1+1/p)}}. $$

证明思路

次高斯变量必须满足 Gaussian 型尾界 $2e^{-ct^2/K^2}$。只要某个分布的尾部比这个慢，就不可能次高斯。

完整证明

若 $X$ 是次高斯，则存在 $c,K>0$ 使

$$ \mathbb P\{|X|>t\}\le2e^{-ct^2/K^2}. $$

exponential、geometric、Gamma 和 chi-squared 的尾部至多是 $e^{-ct}$ 量级；Poisson 右尾是 Poisson/Chernoff 型，固定分布下也比 $e^{-ct^2}$ 慢。Cauchy 和 Pareto 的尾部是多项式量级。上述尾部都不能被某个 Gaussian 型 $e^{-ct^2}$ 在所有大 $t$ 上控制。因此这些分布都不是次高斯。

证明思路

正向用 Orlicz 定义和 Hölder/Jensen 的幂次缩放；反向在端点 $\lambda=1/K$ 处取值得到 Orlicz 控制。

完整证明

设 $K_0=\|X\|_{\psi_2}$，则 $\mathbb E e^{X^2/K_0^2}\le2$。若 $|\lambda|\le1/K_0$，记 $\alpha=\lambda^2K_0^2\in[0,1]$，则

$$ \mathbb E e^{\lambda^2X^2} = \mathbb E\left(e^{X^2/K_0^2}\right)^\alpha \le \left(\mathbb E e^{X^2/K_0^2}\right)^\alpha \le 2^\alpha \le e^{\lambda^2K_0^2}. $$

这证明了正向。

反过来，若 (2.31) 对某个 $K$ 成立，取 $\lambda=1/K$ 得

$$ \mathbb E e^{X^2/K^2}\le e. $$

用同样的幂次缩放，

$$ \mathbb E e^{X^2/(2K)^2} = \mathbb E\left(e^{X^2/K^2}\right)^{1/4} \le e^{1/4}<2. $$

所以 $\|X\|_{\psi_2}\le2K$。

证明思路

正向比较两个尾界：次高斯尾和 Gaussian tail 下界。反向直接把 Gaussian tail 上界传回 $X$。因子 $2$ 的必要性由非零常数变量给出。

完整证明

若 $X$ 次高斯，令 $K_0=\|X\|_{\psi_2}$。存在绝对常数 $c,C$ 使

$$ \mathbb P\{|X|\ge t\}\le2e^{-ct^2/K_0^2}, \qquad \mathbb P\{|g|\ge u\}\ge c_0e^{-C_0u^2}\quad(u\ge1). $$

选择足够大的绝对常数 $A$，可使对 $t\ge AK_0$ 有

$$ \mathbb P\{|X|\ge t\}\le2\mathbb P\{AK_0|g|\ge t\}. $$

对 $t<AK_0$，右侧是一个正的绝对常数量级；继续增大 $A$ 即可覆盖这一区间。因此 $|X|\preceq AK_0|g|$。

反过来，若 $|X|\preceq K|g|$，则

$$ \mathbb P\{|X|\ge t\}\le2\mathbb P\{K|g|\ge t\} \le4e^{-t^2/(2K^2)}. $$

由尾部刻画，$X$ 是次高斯且 $\|X\|_{\psi_2}\le CK$。

若把定义中的因子 $2$ 换成 $1$，取 $X\equiv1$。它是次高斯，但不存在有限 $K$ 使 $1\le K|g|$ 在随机支配意义下成立；例如 $0<t<1$ 时左尾概率为 $1$，而 $\mathbb P\{K|g|\ge t\}<1$。

证明思路

凸支配到次高斯很直接：测试指数型凸函数。次高斯到凸支配可由尾支配和 layer-cake 表示推出，常数通过放大 Gaussian 尺度吸收。

完整证明

先设 $|X|\precsim K|g|$。取非负、凸、递增函数 $\Phi(u)=e^{u^2/L^2}$ 在 $u\ge0$ 上的截断平滑版本，再令截断趋于无穷，可得

$$ \mathbb E e^{X^2/L^2}\le \mathbb E e^{K^2g^2/L^2}. $$

取 $L=CK$ 足够大，右侧至多为 $2$，所以 $\|X\|_{\psi_2}\le CK$。

反过来，若 $X$ 次高斯，由 Exercise 2.27，$|X|\preceq K_0|g|$，其中 $K_0\le C\|X\|_{\psi_2}$。对任意非负凸递增 $\Phi$，可先令 $\Phi(0)=0$；常数项不影响比较。由 layer-cake 公式，

$$ \mathbb E\Phi(|X|) = \int_0^\infty \mathbb P\{|X|\ge t\}\,d\Phi(t) \le 2\int_0^\infty \mathbb P\{K_0|g|\ge t\}\,d\Phi(t). $$

凸性和单调性给出 $2\Phi(u)\le\Phi(2u)$（在 $\Phi(0)=0$ 后成立）。因此

$$ \mathbb E\Phi(|X|)\le\mathbb E\Phi(2K_0|g|). $$

这就是 $|X|\precsim K|g|$，其中 $K\le C\|X\|_{\psi_2}$。

证明思路

有界中心化变量是次高斯变量，尺度由区间长度控制。把次高斯 Hoeffding 套到中心化和即可。

完整证明

若 $X_i\in[a_i,b_i]$，则由 Exercise 2.9 或有界变量的 Orlicz 控制，

$$ \|X_i-\mathbb EX_i\|_{\psi_2}\le C(b_i-a_i). $$

把 Theorem 2.7.3 用于独立中心化变量 $X_i-\mathbb EX_i$，得到

$$ \mathbb P\left\{\left|\sum_i(X_i-\mathbb EX_i)\right|\ge t\right\} \le 2\exp\left(-\frac{ct^2}{\sum_i(b_i-a_i)^2}\right). $$

这就是 Theorem 2.2.6 的形式，只是指数中的绝对常数可能与原来不同。

证明思路

先用独立性和单位方差算二阶矩，再用次高斯 Khintchine 控制四阶矩，最后对 $Z^2$ 使用 Paley-Zygmund。

完整证明

令 $Z=\sum_i a_iX_i$，$\sigma^2=\sum_i a_i^2$。由于 $X_i$ 独立、均值为零、方差为一，

$$ \mathbb EZ^2=\sigma^2. $$

由次高斯 Khintchine 或 Proposition 2.7.1 的矩形式，

$$ \|Z\|_{L^4}\le CK\sqrt4\,\sigma, $$

从而 $\mathbb EZ^4\le CK^4\sigma^4$。对非负随机变量 $W=Z^2$ 用 Paley-Zygmund，

$$ \mathbb P\left\{W\ge\frac14\mathbb EW\right\} \ge (1-1/4)^2\frac{(\mathbb EW)^2}{\mathbb EW^2} \ge \frac{c}{K^4}. $$

这等价于

$$ \mathbb P\left\{|Z|\ge\frac12\sigma\right\}\ge\frac c{K^4}. $$

证明思路

取平均系数 $a_i=1/N$。Hoeffding 型界迫使样本均值以高概率趋近 $0$；大数定律又让它趋近真实均值。

完整证明

令 $a_i=1/N$。假设存在 $c>0$ 使

$$ \mathbb P\left\{\left|\frac1N\sum_{i=1}^NX_i\right|\ge t\right\} \le 2\exp(-cNt^2) $$

对所有 $N,t$ 成立。固定任意 $t>0$，右侧随 $N\to\infty$ 趋于 $0$，所以样本均值依概率收敛到 $0$。另一方面，由大数定律，样本均值依概率收敛到 $\mathbb EX_1$。依概率极限唯一，因此 $\mathbb EX_1=0$。

证明思路

上界是 Orlicz 范数三角不等式。下界用矩刻画：条件化后由 Jensen 得到 $\|X+Y\|_{L^p}$ 同时控制 $\|X\|_{L^p}$ 和 $\|Y\|_{L^p}$。

完整证明

上界直接由三角不等式给出：

$$ \|X+Y\|_{\psi_2}\le\|X\|_{\psi_2}+\|Y\|_{\psi_2}. $$

下界使用等价刻画

$$ \|Z\|_{\psi_2}\asymp\sup_{p\ge1}\frac{\|Z\|_{L^p}}{\sqrt p}. $$

固定 $p\ge1$，由于 $y\mapsto|x+y|^p$ 是凸函数且 $\mathbb EY=0$，

$$ \mathbb E_Y|x+Y|^p\ge |x+\mathbb EY|^p=|x|^p. $$

再对 $X$ 取期望，得 $\|X+Y\|_{L^p}\ge\|X\|_{L^p}$。同理 $\|X+Y\|_{L^p}\ge\|Y\|_{L^p}$。取上确界可得

$$ \|X+Y\|_{\psi_2}\ge c\max(\|X\|_{\psi_2},\|Y\|_{\psi_2}) \ge \frac c2(\|X\|_{\psi_2}+\|Y\|_{\psi_2}). $$

证明思路

上界是 Proposition 2.7.1。下界用 exact subgaussian norm：对 i.i.d. 中心化变量，和的 MGF 是单个 MGF 的 $N$ 次方，因此 exact subgaussian variance 对和精确按 $N$ 缩放。最后用 exact norm 与标准 $\psi_2$ norm 的等价性。

完整证明

上界由 Proposition 2.7.1 立即得到：

$$ \left\|\sum_{i=1}^NX_i\right\|_{\psi_2}\le C\sqrt N\|X\|_{\psi_2}. $$

为证明下界，引入 Exercise 2.40 中的 exact subgaussian variance。对中心化变量 $Z$，记

$$ \operatorname{Var}_G(Z) = \inf\left\{\sigma^2:\mathbb E e^{\lambda Z}\le e^{\sigma^2\lambda^2/2}\ \text{for all }\lambda\in\mathbb R\right\}. $$

设 $S_N=\sum_{i=1}^NX_i$。若 $\sigma^2>\operatorname{Var}_G(X)$，则

$$ \mathbb E e^{\lambda S_N} = \left(\mathbb E e^{\lambda X}\right)^N \le e^{N\sigma^2\lambda^2/2}, $$

所以 $\operatorname{Var}_G(S_N)\le N\operatorname{Var}_G(X)$。反过来，若 $\tau^2>\operatorname{Var}_G(S_N)$，则

$$ \left(\mathbb E e^{\lambda X}\right)^N = \mathbb E e^{\lambda S_N} \le e^{\tau^2\lambda^2/2}. $$

两边取 $N$ 次方根，得到

$$ \mathbb E e^{\lambda X}\le e^{(\tau^2/N)\lambda^2/2}. $$

因此 $\operatorname{Var}_G(X)\le\tau^2/N$。令 $\tau^2\downarrow\operatorname{Var}_G(S_N)$，得到 $\operatorname{Var}_G(S_N)\ge N\operatorname{Var}_G(X)$。于是

$$ \operatorname{Var}_G(S_N)=N\operatorname{Var}_G(X). $$

因为 $X$ 和 $S_N$ 都中心化，exact norm 满足 $\|Z\|_G^2=\operatorname{Var}_G(Z)$，所以

$$ \|S_N\|_G=\sqrt N\,\|X\|_G. $$

Exercise 2.40 证明 $\|Z\|_G\asymp\|Z\|_{\psi_2}$，常数为绝对常数。因此

$$ \left\|\sum_{i=1}^NX_i\right\|_{\psi_2} \asymp \sqrt N\,\|X\|_{\psi_2}. $$

这证明了 (a)。

对 (b)，令 $X_i=\operatorname{Ber}(p)-p$。则 $S_N-Np=\sum_iX_i$。先计算单个中心化 Bernoulli 的尺度。若 $p\le1/2$，则 $|X_i|\le1$ 给出上界；更精确地取 $K=C/\sqrt{\log(2/p)}$，可直接验证

$$ \mathbb E e^{X_i^2/K^2} = p e^{(1-p)^2/K^2}+(1-p)e^{p^2/K^2} \le2 $$

当 $C$ 足够大时成立。下界由 $\mathbb P\{|X_i|\ge1/2\}\ge p$ 给出：若 $\mathbb E e^{X_i^2/K^2}\le2$，则 $p e^{1/(4K^2)}\le2$，所以 $K\ge c/\sqrt{\log(2/p)}$。当 $p>1/2$ 时，$\log(2/p)$ 为绝对常数量级，且 $X_i$ 有有界非退化波动，因此范数也是绝对常数量级。综上

$$ \|X_i\|_{\psi_2}\asymp\frac1{\sqrt{\log(2/p)}}. $$

代入 (a)，得到

$$ \|S_N-Np\|_{\psi_2} \asymp \sqrt{\frac N{\log(2/p)}}. $$

证明思路

用越来越稀有、越来越大的对称尖峰变量。每个变量本身的 $\psi_2$ 范数同阶，但由于尖峰幅度超指数分离，任意有限和的尾部由最大的活跃尖峰主导。

完整证明

取 $b_i=4^i$。令 $\eta_i$ 是 Bernoulli 变量，$\mathbb P\{\eta_i=1\}=e^{-b_i^2}$；令 $\varepsilon_i$ 是独立 Rademacher 变量，并设

$$ X_i=\varepsilon_i b_i\eta_i. $$

则 $\mathbb EX_i=0$，且

$$ \mathbb E e^{X_i^2} = 1-e^{-b_i^2}+e^{-b_i^2}e^{b_i^2}<2, $$

而若把常数缩小则指数矩爆炸。因此 $\|X_i\|_{\psi_2}\asymp1$。

设 $\|a\|_\infty\le1$，$S=\sum_{i=1}^Na_iX_i$。由于 $b_i=4^i$，任意一组活跃尖峰的总绝对值至多为最大活跃 $b_i$ 的绝对常数倍。因此若 $|S|\ge t$，必有某个 $i$ 满足 $\eta_i=1$ 且 $b_i\ge ct$。于是

$$ \mathbb P\{|S|\ge t\} \le \sum_{i:b_i\ge ct}e^{-b_i^2} \le C e^{-c't^2}. $$

所以 $\|S\|_{\psi_2}\le C$。缩放得到一般上界 $\|S\|_{\psi_2}\le C\|a\|_\infty$。

反向下界取 $j$ 使 $|a_j|=\|a\|_\infty$。条件化其它变量并用 Exercise 2.32 中的 Jensen/moment 下界，可得 $\|S\|_{\psi_2}\ge c|a_j|\|X_j\|_{\psi_2}\ge c\|a\|_\infty$。因此

$$ \left\|\sum_{i=1}^Na_iX_i\right\|_{\psi_2}\asymp\|a\|_\infty. $$

取 $a_i=1$ 时，右侧为 $1$，而 $\left(\sum_i\|X_i\|_{\psi_2}^2\right)^{1/2}\asymp\sqrt N$，所以 Proposition 2.7.1 的不等式不能一般反向。

证明思路

先用矩插值 $\|X\|_{L^p}\le a^{1/p}b^{1-1/p}$，再用 $\psi_2$ 的矩刻画优化 $p$。紧性由两点变量给出。

完整证明

设 $\mathbb E|X|=a$ 且 $|X|\le b$。由插值或 Hölder，

$$ \|X\|_{L^p}\le a^{1/p}b^{1-1/p}=b\left(\frac ab\right)^{1/p}. $$

令 $L=\log(2b/a)$。由矩刻画，

$$ \|X\|_{\psi_2}\le C\sup_{p\ge1}\frac{b e^{-L/p}}{\sqrt p}. $$

函数 $e^{-L/p}/\sqrt p$ 的最大值在 $p\asymp L$ 处，最大量级为 $1/\sqrt L$。因此

$$ \|X\|_{\psi_2}\le\frac{Cb}{\sqrt{\log(2b/a)}}. $$

紧性取 $X=b$ 的概率为 $a/b$、$X=0$ 的概率为 $1-a/b$。此时

$$ \mathbb E e^{X^2/K^2}=1-\frac ab+\frac ab e^{b^2/K^2}, $$

从等于 $2$ 解得 $K\asymp b/\sqrt{\log(2b/a)}$。

证明思路

先证明一个 $L^1,L^2,L^3$ 插值式。然后对线性组合 $Z$ 用 $L^2$ 的精确方差和 $L^3$ 的次高斯上界推出 $L^1$ 下界；最后由 $L^p$ 单调性扩展到 $[1,2]$。

完整证明

(a) 由 log-convexity，若 $1/2=(1-\theta)/1+\theta/3$，则 $\theta=3/4$，所以

$$ \|Z\|_{L^2}\le\|Z\|_{L^1}^{1/4}\|Z\|_{L^3}^{3/4}. $$

(b) 令 $Z=\sum_i a_iX_i$，$\sigma=(\sum_i a_i^2)^{1/2}$。由独立、零均值、单位方差，$\|Z\|_{L^2}=\sigma$。由 Theorem 2.7.5 或次高斯矩界，

$$ \|Z\|_{L^3}\le CK\sigma. $$

代入 (a)：

$$ \sigma\le\|Z\|_{L^1}^{1/4}(CK\sigma)^{3/4}, $$

整理得 $\|Z\|_{L^1}\ge cK^{-3}\sigma$。上界由 Jensen/Cauchy 得 $\mathbb E|Z|\le\|Z\|_{L^2}=\sigma$。

(c) 对 $p\in[1,2]$，$L^p$ 范数随 $p$ 增大而增大，所以下界由 $L^1$ 给出，上界由 $L^2$ 给出：

$$ cK^{-3}\sigma\le\|Z\|_{L^p}\le\sigma. $$

证明思路

对上确界做 union bound。归一化让第 $k$ 项的尾概率变成 $(2k)^{-A}$，从而级数可求和。

完整证明

令 $K=\sup_k\|X_k\|_{\psi_2}$，并设

$$ M=\sup_k\frac{|X_k|}{\sqrt{\log(2k)}}. $$

由次高斯尾界，

$$ \mathbb P\{M>t\} \le \sum_{k\ge1}\mathbb P\{|X_k|>t\sqrt{\log(2k)}\} \le 2\sum_{k\ge1}\exp\left(-\frac{ct^2\log(2k)}{K^2}\right). $$

当 $t\ge CK$ 时，级数被 $C\exp(-c't^2/K^2)$ 控制；当 $t<CK$ 时可调大常数使尾界平凡成立。因此 $M$ 有次高斯尾，等价地

$$ \|M\|_{\psi_2}\le CK. $$

证明思路

上界用指数矩和 Jensen。独立情形的下界用 Gaussian tail 下界证明最大值超过 $(1-o(1))\sqrt{2\log N}$ 的概率趋于 $1$。

完整证明

(a) 对任意 $\lambda>0$，Jensen 与 union bound 给出

$$ e^{\lambda\mathbb E\max_i g_i} \le \mathbb E e^{\lambda\max_i g_i} \le \sum_{i=1}^N\mathbb E e^{\lambda g_i} = Ne^{\lambda^2/2}. $$

取对数并优化 $\lambda$，得到 $\mathbb E\max_i g_i\le\sqrt{2\log N}$。对绝对值，把 $g_i$ 和 $-g_i$ 视作 $2N$ 个 Gaussian，得到 $\mathbb E\max_i|g_i|\le\sqrt{2\log(2N)}$。

(b) 设 $u_N=(1-\varepsilon)\sqrt{2\log N}$。由 Gaussian tail 下界，

$$ \mathbb P\{g_1>u_N\}\ge N^{-(1-\varepsilon)^2+o(1)}. $$

独立性给出

$$ \mathbb P\{\max_{i\le N}g_i\le u_N\} = (1-\mathbb P\{g_1>u_N\})^N\to0. $$

因此 $\max_i g_i\ge(1-\varepsilon)\sqrt{2\log N}$ 以高概率发生，期望下界同阶；令 $\varepsilon\downarrow0$ 得到渐近。绝对值版本同理，或由 $\max_i|g_i|\ge\max_i g_i$ 给下界、由 (a) 给上界。

证明思路

若尾概率 $p=\mathbb P\{|X|>t\}$ 不小，则取 $N\asymp1/p$ 个副本，最大值超过 $t$ 的概率为常数量级。最大值期望上界迫使 $t\lesssim K\sqrt{\log(1/p)}$，这就是 Gaussian 尾。

完整证明

设 $p(t)=\mathbb P\{|X|>t\}$。若 $p(t)>0$，取整数 $N\ge2$ 使 $1/N\le p(t)\le2/N$。则

$$ \mathbb P\{\max_{i\le N}|X_i|>t\} = 1-(1-p(t))^N \ge c. $$

于是

$$ c t \le \mathbb E\max_{i\le N}|X_i| \le K\sqrt{\log N}. $$

因为 $N\le2/p(t)$，得到

$$ t\le CK\sqrt{\log(2/p(t))}. $$

等价变形即

$$ p(t)\le2\exp(-ct^2/K^2). $$

由尾部刻画，$X$ 是次高斯且 $\|X\|_{\psi_2}\le CK$。

证明思路

定义基于中心化 MGF。范数三角不等式用 Hölder；等价性用 Proposition 2.6.1；方差比较由 MGF 在零点二阶展开；独立和由 MGF 分解。

完整证明

(a) 齐次性来自替换 $\lambda$：$\operatorname{Var}_G(aX)=a^2\operatorname{Var}_G(X)$。非退化性由 $\|X\|_G=0$ 推出 $\operatorname{Var}(X)=0$ 且 $\mathbb EX=0$，所以 $X=0$ a.s.。三角不等式如下。设 $\sigma_X^2>\operatorname{Var}_G(X)$、$\sigma_Y^2>\operatorname{Var}_G(Y)$，并取 $p,q>1$，$1/p+1/q=1$。Hölder 给出

$$ \mathbb E e^{\lambda[(X-\mathbb EX)+(Y-\mathbb EY)]} \le \exp\left(\frac{p\lambda^2\sigma_X^2+q\lambda^2\sigma_Y^2}{2}\right). $$

优化 $p,q$ 得 $\operatorname{Var}_G(X+Y)^{1/2}\le \operatorname{Var}_G(X)^{1/2}+\operatorname{Var}_G(Y)^{1/2}$，再与均值部分的三角不等式合并。

(b) Proposition 2.6.1 的 MGF 刻画给出 $\operatorname{Var}_G(X)^{1/2}\asymp\|X-\mathbb EX\|_{\psi_2}$；再用 $\|X\|_{\psi_2}\asymp\|X-\mathbb EX\|_{\psi_2}+|\mathbb EX|$，得到 $\|X\|_G\asymp\|X\|_{\psi_2}$。

(c) 若 $\mathbb Ee^{\lambda(X-\mathbb EX)}\le e^{\sigma^2\lambda^2/2}$，比较 $\lambda=0$ 处二阶项得 $\operatorname{Var}(X)\le\sigma^2$。取下确界得 $\operatorname{Var}(X)\le\operatorname{Var}_G(X)$，从而 $\|X\|_{L^2}\le\|X\|_G$。正态变量的 MGF 精确等于 $e^{\operatorname{Var}(X)\lambda^2/2}$，故取等号。

(d) 若 $X_i$ 独立且中心化，则

$$ \mathbb E e^{\lambda\sum_iX_i} = \prod_i\mathbb E e^{\lambda X_i} \le \exp\left(\frac{\lambda^2}{2}\sum_i\operatorname{Var}_G(X_i)\right). $$

所以 $\operatorname{Var}_G(\sum_iX_i)\le\sum_i\operatorname{Var}_G(X_i)$。均值为零时这就是 $\|\sum_iX_i\|_G^2\le\sum_i\|X_i\|_G^2$。

(e) 中心化后均值项消失，且 $\operatorname{Var}_G(X-\mathbb EX)=\operatorname{Var}_G(X)$，所以 $\|X-\mathbb EX\|_G\le\|X\|_G$。

证明思路

完全平行于次高斯证明，只把 $\sqrt p$ 换成 $p$，把 $e^{-ct^2}$ 换成 $e^{-ct}$。

完整证明

若 $\mathbb P\{|X|>t\}\le2e^{-ct/K}$，则由尾积分公式，

$$ \mathbb E|X|^p = p\int_0^\infty t^{p-1}\mathbb P\{|X|>t\}\,dt \le 2p\int_0^\infty t^{p-1}e^{-ct/K}\,dt \le (CKp)^p. $$

所以 $\|X\|_{L^p}\le CKp$。若 moment growth 成立，则展开指数级数，取足够大的 $C$ 得

$$ \mathbb E e^{|X|/(CK)} = \sum_{m=0}^\infty\frac{\mathbb E|X|^m}{(CK)^m m!} \le2. $$

这就是 $\psi_1$ Orlicz 控制。最后若 $\mathbb E e^{|X|/K}\le2$，Markov 给出

$$ \mathbb P\{|X|>t\}\le2e^{-t/K}. $$

三种性质互相推出，参数只差绝对常数。

证明思路

齐次性直接来自定义；三角不等式用 $\psi$ 的凸性；非退化性需要 $\psi(t)>0$ 对 $t>0$。例子由具体 $\psi$ 代入。

完整证明

设 $\|X\|_\psi\le K$、$\|Y\|_\psi\le L$。则由凸性和 $|X+Y|\le|X|+|Y|$，

$$ \psi\left(\frac{|X+Y|}{K+L}\right) \le \frac K{K+L}\psi\left(\frac{|X|}{K}\right) + \frac L{K+L}\psi\left(\frac{|Y|}{L}\right). $$

取期望得 $\|X+Y\|_\psi\le K+L$，再取下确界得到三角不等式。齐次性由

$$ \mathbb E\psi\left(\frac{|aX|}{K}\right) = \mathbb E\psi\left(\frac{|X|}{K/|a|}\right) $$

立即得到。若 $\|X\|_\psi=0$，则对任意 $K>0$ 有 $\mathbb E\psi(|X|/K)\le1$；令 $K\downarrow0$ 并用 $\psi(t)>0$，得到 $X=0$ a.s.。

取 $\psi(t)=t^p$ 时，该范数与 $L^p$ 范数一致。取 $\psi(t)=e^{t^2}-1$ 得次高斯范数的等价版本；取 $\psi(t)=e^t-1$ 得次指数范数的等价版本。

证明思路

把次高斯的 $2$ 和次指数的 $1$ 统一成一般幂次 $\alpha$。证明仍然是 tail 积分、指数级数和 Markov 三步。注意：这里统一的是 tail、moment、Orlicz 三种刻画，不把普通 MGF $\mathbb E e^{\lambda X}$ 当作所有 $\alpha$ 下的统一条件；相关大偏差尺度见 概率论背景补充附录。

完整证明

定义

$$ \|X\|_{\psi_\alpha} = \inf\left\{K>0:\mathbb E\exp(|X|^\alpha/K^\alpha)\le2\right\}. $$

等价刻画为：存在绝对常数调整后的 $K$，使

$$ \mathbb P\{|X|>t\}\le2\exp(-ct^\alpha/K^\alpha), $$

以及

$$ \|X\|_{L^p}\le CKp^{1/\alpha}\qquad(p\ge1). $$

tail 到 moment：用

$$ \mathbb E|X|^p=p\int_0^\infty t^{p-1}\mathbb P\{|X|>t\}\,dt $$

并换元 $u=ct^\alpha/K^\alpha$。moment 到 Orlicz：展开 $\exp(|X|^\alpha/(CK)^\alpha)$ 的级数并用 $\Gamma(m+1)$ 量级吸收。Orlicz 到 tail：直接对 $\exp(|X|^\alpha/K^\alpha)$ 用 Markov。$\alpha=2$ 和 $\alpha=1$ 分别回到次高斯和次指数。

如果想把 $\exp(-ct^\alpha)$ 尾部和 log MGF 的凸共轭联系起来，必须区分 $\lambda\to0$ 与 $|\lambda|\to\infty$ 两个尺度；这部分已经单独放入附录，避免把高级旁注混进本题证明。

证明思路

把次高斯论证中的 $\sqrt{\log N}$ 换成 $\log N$，把 Gaussian 支配变量换成 exponential 型变量。

完整证明

(a) 中心化：由 Orlicz 范数三角不等式和 Jensen，

$$ \|X-\mathbb EX\|_{\psi_1} \le \|X\|_{\psi_1}+|\mathbb EX| \le C\|X\|_{\psi_1}. $$

(b) 最大不等式：若 $K=\max_i\|X_i\|_{\psi_1}$，则 union bound 给出

$$ \mathbb P\{\max_i|X_i|>t\} \le 2N e^{-ct/K}. $$

这等价于 $\|\max_i|X_i|\|_{\psi_1}\le CK\log(2N)$。

(c) 凸支配：设 $E$ 为均值为绝对常数的指数变量。次指数尾界等价于 $|X|\preceq K E$。再用 Exercise 2.28 的 layer-cake/凸性放大论证，把近似尾支配转为凸支配：存在绝对常数 $C$ 使 $|X|\precsim CK E$。反向用 $\Phi(u)=e^{u/L}$ 的截断版本即可。

证明思路

从 `min(二次项, 一次项)` 尾界出发，选择 $t=C(\sigma\sqrt u+Ku)$，使两个分母项都至少为常数倍 $u$。

完整证明

由 Theorem 2.9.1，

$$ \mathbb P\{|S|\ge t\} \le 2\exp\left[-c\min\left(\frac{t^2}{\sigma^2},\frac tK\right)\right]. $$

令 $t=C_0(\sigma\sqrt u+Ku)$。则

$$ \frac{t^2}{\sigma^2}\ge C_0^2u, \qquad \frac tK\ge C_0u. $$

选 $C_0$ 足够大，使 $c\min(C_0^2u,C_0u)\ge u$。于是

$$ \mathbb P\{|S|\ge C_0(\sigma\sqrt u+Ku)\}\le2e^{-u}. $$

证明思路

先对线性组合应用 Bernstein 得到混合尾，再用尾积分公式计算 $L^p$。二次尾贡献 $\sqrt p\|a\|_2$，一次尾贡献 $p\|a\|_\infty$。

完整证明

令 $S=\sum_i a_iX_i$，$K=\max_i\|X_i\|_{\psi_1}$。由 Bernstein 不等式，

$$ \mathbb P\{|S|>t\} \le 2\exp\left[ -c\min\left( \frac{t^2}{K^2\|a\|_2^2}, \frac{t}{K\|a\|_\infty} \right)\right]. $$

利用尾积分公式

$$ \|S\|_{L^p}^p=p\int_0^\infty t^{p-1}\mathbb P\{|S|>t\}\,dt. $$

把右侧分别用两个尾界控制。Gaussian 型部分给出 $CK\sqrt p\|a\|_2$，指数型部分给出 $CKp\|a\|_\infty$。合并即

$$ \left\|\sum_i a_iX_i\right\|_{L^p} \le CK\left(\sqrt p\|a\|_2+p\|a\|_\infty\right). $$

证明思路

MGF 用 Taylor 展开，利用 $|X|^k\le K^{k-2}X^2$ 把高阶矩都压到二阶矩上。然后指数矩方法优化参数。

完整证明

因为 $\mathbb EX=0$，

$$ \mathbb E e^{\lambda X} = 1+\sum_{k\ge2}\frac{\lambda^k\mathbb EX^k}{k!} \le 1+\mathbb EX^2\sum_{k\ge2}\frac{|\lambda|^kK^{k-2}}{k!}. $$

由 $k!\ge2\cdot3^{k-2}$，当 $|\lambda|<3/K$ 时，

$$ \sum_{k\ge2}\frac{|\lambda|^kK^{k-2}}{k!} \le \frac{\lambda^2/2}{1-|\lambda|K/3} = g(\lambda). $$

再用 $1+u\le e^u$，得到

$$ \mathbb E e^{\lambda X}\le\exp(g(\lambda)\mathbb EX^2). $$

对独立和 $S=\sum_iX_i$，令 $\sigma^2=\sum_i\mathbb EX_i^2$，则

$$ \mathbb E e^{\lambda S}\le e^{g(\lambda)\sigma^2}. $$

Markov 给出 $\mathbb P\{S\ge t\}\le\exp[-\lambda t+g(\lambda)\sigma^2]$。取 $\lambda=t/(\sigma^2+Kt/3)$（它小于 $3/K$），得到右尾 Bernstein；对 $-S$ 重复并合并，得到 Theorem 2.9.5。

证明思路

先用一条二次插值不等式控制单个有界变量的 MGF；再对和分解 MGF 并精确优化 $\lambda$。最后分析 $h(u)$ 在 $0$ 附近和无穷远的行为。

完整证明

(a) 对 $|x|\le K$，凸性可验证

$$ e^{\lambda x} \le 1+\lambda x+\frac{x^2}{K^2}(e^{\lambda K}-1-\lambda K). $$

令 $x=X$ 并取期望，利用 $\mathbb EX=0$ 和 $1+u\le e^u$，得到

$$ \mathbb E e^{\lambda X} \le \exp\left[ \frac{\mathbb EX^2}{K^2}(e^{\lambda K}-1-\lambda K) \right]. $$

(b) 对 $S=\sum_iX_i$，独立性给出

$$ \mathbb E e^{\lambda S} \le \exp\left[ \frac{\sigma^2}{K^2}(e^{\lambda K}-1-\lambda K) \right]. $$

Markov 不等式给出

$$ \mathbb P\{S\ge t\} \le \exp\left[ -\lambda t+\frac{\sigma^2}{K^2}(e^{\lambda K}-1-\lambda K) \right]. $$

优化条件为 $e^{\lambda K}=1+Kt/\sigma^2$。令 $u=Kt/\sigma^2$，代回得

$$ \mathbb P\{S\ge t\}\le \exp\left[-\frac{\sigma^2}{K^2}h(u)\right], \quad h(u)=(1+u)\log(1+u)-u. $$

对 $-S$ 重复并合并，得到 (2.36)。

(c) Taylor 展开给出 $h(u)=u^2/2+O(u^3)$，所以小偏差时指数为 $-ct^2/\sigma^2$，即 Gaussian 型。

(d) 当 $u\ge1$ 时，微积分可验证 $h(u)\ge\frac12u\log u$；当 $0<u<1$ 时右侧为负，结论平凡。因此大偏差时

$$ \exp\left[-\frac{\sigma^2}{K^2}h(u)\right] \le \left(\frac{\sigma^2}{Kt}\right)^{t/(2K)}. $$

加上双侧因子 $2$，得到题中 Poisson 型尾界。