高维几何与测度集中

测度集中描述随机量围绕均值聚集的速度,高维几何则展示高维空间的“反直觉”。三大集中不等式: Markov(非负 $X$、$a>0$): $P(X \ge a) \le \frac{\mathbb{E}[X]}{a}$;Chebyshev($k>0$): $P(|X-\mu| \ge k\sigma) \le \frac{1}{k^2}$;Hoeffding(独立 $X_i \in [0,1]$): $P(\bar{X}_n - \mu \ge t) \le e^{-2nt^2}$,概率随 $n$ 指数衰减。Thin Shell 直觉: $d$ 维单位球体积 $\propto r^d$,半径 $1-\frac{1}{d}$ 的球只含约 $(1-\frac{1}{d})^d \approx e^{-1} \approx 37\%$ 的体积,即约 63% 的体积集中在厚度 $O(1/d)$ 的球壳内;随机单位向量 $u,v \in \mathbb{R}^d$ 的点积方差约 $1/d$、量级 $O(1/\sqrt{d})$ — 高维向量几乎两两正交,这也正是 $\frac{QK^T}{\sqrt{d_k}}$ 归一化的原因。

泛化界的证明(ERM 一致收敛、PAC 界)、随机投影 (Johnson-Lindenstrauss)、高维初始化与梯度方差分析、差分隐私机制;面试“证明 Hoeffding”“高维里发生了什么”从这里出。

Chebyshev 只需二阶矩但界松($1/k^2$),无法回答“随样本量收敛多快”;Hoeffding 等指数界在独立有界条件下给出 $e^{-2nt^2}$ 的指数衰减,把“概率收敛”变成可操作的速率。Markov 条件最弱(只需非负与一阶矩),是 Chebyshev 及其他一切集中不等式的源头。

写出 Markov、Chebyshev、Hoeffding 三个不等式并说明各自需要的条件?

如何由 Markov 不等式推出 Chebyshev 不等式?为什么 Chebyshev 更紧?

Hoeffding 为什么能给出指数衰减?证明泛化界(ERM/PAC)时用哪一个?

Thin Shell 现象是什么?为什么高维单位球的体积集中在球壳附近?

为什么高维随机单位向量几乎正交?点积的量级是多少?与注意力缩放的联系?