MIStatlE
EN

← 全部笔记信息论推导

Typical Set：高维空间中的概率集中

概率质量为什么不在密度最高的点，而会落在高维空间中的薄壳上？

约 3 分钟

1. 问题设定

假设我们有一组独立同分布 (i.i.d.) 的随机变量 X1,…,XnX_1, \dots, X_n，其联合分布为 p(Xn)=p(x1,…,xn)p(X^n) = p(x_1, \dots, x_n)。

我们的目标是识别出一个“核心子集” A∈XnA \in \mathcal{X}^n，使得绝大多数的采样点都落在这个集合里：

P[Xn∈A]≥1−ϵ\mathbb P[X^n \in A] \geq 1-\epsilon

显然，可以根据大数定律，对于函数 g(x)g(x)：

E[I(∣1n∑i=1ng(Xi)−E[g(X)]∣≤ϵ)]≥1−ϵ\mathbb{E} \left[ \mathbb{I}\left( \left| \frac{1}{n}\sum_{i=1}^n g(X_i) - \mathbb{E}[g(X)] \right| \le \epsilon \right) \right] \ge 1-\epsilon

这定义了一个集合 AϵA_{\epsilon}。下一步：我们需要选择什么样的 g(x)g(x) 才能刻画分布的几何形状？

我们选择 g(x)=−log⁡p(x)g(x)=-\log p(x)。

注 利用独立同分布 (i.i.d.) 的性质，我们将联合分布的概率密度通过对数变换，转化为样本均值的求和形式，从而应用大数定律 (LLN)：

−1nlog⁡p(xn)=−1nlog⁡(∏i=1np(xi))=1n∑i=1n[−log⁡p(xi)]-\frac{1}{n} \log p(x^n) = -\frac{1}{n} \log \left( \prod_{i=1}^n p(x_i) \right) = \frac{1}{n} \sum_{i=1}^n \left[ -\log p(x_i) \right]

当 n→∞n \to \infty 时，根据大数定律，上述样本均值收敛于其期望值，即分布的熵：

1n∑i=1n[−log⁡p(xi)]→PE[−log⁡p(X)]=H(X)\frac{1}{n} \sum_{i=1}^n \left[ -\log p(x_i) \right] \xrightarrow{P} \mathbb{E}[-\log p(X)] = H(X)

2. 渐进均分性 (AEP) 与定义

渐进均分性 (Asymptotic Equipartition Property, AEP) 是大数定律在随机变量对数概率上的体现。

定理 (AEP)

当 n→∞n \to \infty 时，依据大数定律：

−1nlog⁡p(X1,…,Xn)→H(X)in probability-\frac{1}{n} \log p(X_1, \dots, X_n) \to H(X) \quad \text{in probability}

其中 H(X)=E[−log⁡p(X)]H(X) = \mathbb{E}[-\log p(X)] 为熵（对于连续变量则为微分熵）。

这意味着，对于绝大多数“典型”的序列，其联合概率 p(xn)p(x^n) 都在 2−nH(X)2^{-nH(X)} 附近。基于此，我们定义典型集：

定义 (典型集 Aϵ(n)A_\epsilon^{(n)})

典型集 Aϵ(n)A_\epsilon^{(n)} 是满足以下条件的序列集合：

Aϵ(n)={xn∈Xn:∣−1nlog⁡p(xn)−H(X)∣≤ϵ}A_\epsilon^{(n)} = \{ x^n \in \mathcal{X}^n : \left| -\frac{1}{n} \log p(x^n) - H(X) \right| \le \epsilon\}

简单来说，典型集包含了那些“惊奇度”（负对数似然）接近平均熵的样本。

3. 典型集的关键性质

典型集具有两个看似矛盾但至关重要的性质，这解释了采样的本质。

性质 1：概率集中

当 nn 足够大时，典型集几乎包含了所有的概率质量：

P(Aϵ(n))>1−ϵ\mathbb{P}(A_\epsilon^{(n)}) > 1 - \epsilon

这意味着如果你从分布中随机采样，有很高的概率会落在典型集里。

性质 2：体积微小

尽管它包含了几乎所有概率，但在高维空间中，它相对于整个状态空间的体积却微乎其微：

Vol(Aϵ(n))≈2nH(X)\text{Vol}(A_\epsilon^{(n)}) \approx 2^{nH(X)}

如果熵 H(X)<log⁡∣X∣H(X) < \log |\mathcal{X}|（对于均匀分布才相等），则典型集只是整个空间中极小的一个子集。

证明

证明的核心在于利用概率的归一化性质。 根据典型集的定义，对于集合内任意序列 xn∈Aϵ(n)x^n \in A_\epsilon^{(n)}，其概率都有下界：

p(xn)≥2−n(H(X)+ϵ)p(x^n) \ge 2^{-n(H(X) + \epsilon)}

由于全空间的概率之和为 1，典型集的总概率必然小于等于 1：

1≥∑xn∈Aϵ(n)p(xn)≥∑xn∈Aϵ(n)2−n(H(X)+ϵ)(代入下界)=∣Aϵ(n)∣⋅2−n(H(X)+ϵ)(求和转化为体积乘积)\begin{aligned} 1 &\ge \sum_{x^n \in A_\epsilon^{(n)}} p(x^n) \\ &\ge \sum_{x^n \in A_\epsilon^{(n)}} 2^{-n(H(X) + \epsilon)} \quad (\text{代入下界}) \\ &= |A_\epsilon^{(n)}| \cdot 2^{-n(H(X) + \epsilon)} \quad (\text{求和转化为体积乘积}) \end{aligned}

移项整理，即可得到体积的上界：

∣Aϵ(n)∣≤2n(H(X)+ϵ)≈2nH(X)|A_\epsilon^{(n)}| \le 2^{n(H(X) + \epsilon)} \approx 2^{nH(X)}

这表明，只要分布不是完全均匀的（即 H(X)<log⁡∣X∣H(X) < \log |\mathcal{X}|），典型集的体积就会随着 nn 的增加，相对于全空间体积 ∣X∣n=2nlog⁡∣X∣|\mathcal{X}|^n = 2^{n \log |\mathcal{X}|} 指数级地缩小。

4. 实例：高维高斯分布

考虑 dd 维标准高斯分布 X∼N(0,Id)X \sim \mathcal{N}(0, I_d)。尽管其概率密度函数在原点 x=0x=0 处取得最大值，但高维几何的特性使得概率质量并未集中在此处。

对于任意样本 x∈Rdx \in \mathbb{R}^d，其对数似然函数为：

−log⁡p(x)=d2log⁡(2π)+12∑i=1dxi2-\log p(x) = \frac{d}{2}\log(2\pi) + \frac{1}{2} \sum_{i=1}^d x_i^2

为了考察典型集的位置，我们分析归一化的对数概率。由于 XX 的分量 xix_i 独立且服从 N(0,1)\mathcal{N}(0, 1)，则 xi2x_i^2 服从自由度为 1 的卡方分布，且 E[xi2]=1\mathbb{E}[x_i^2]=1。根据弱大数定律 (WLLN)，当维度 d→∞d \to \infty 时，样本的二阶矩依概率收敛于其期望：

1d∥x∥2=1d∑i=1dxi2→PE[x12]=1\frac{1}{d} \|x\|^2 = \frac{1}{d} \sum_{i=1}^d x_i^2 \xrightarrow{P} \mathbb{E}[x_1^2] = 1

这意味着，绝大多数从高维高斯分布中采样的点，都位于以原点为球心、半径为 d\sqrt{d} 的狭窄球壳附近：

∥x∥≈d\|x\| \approx \sqrt{d}