最小熵

形式陈述 ​

设离散概率分布公理库概率分布Probability distribution · Law定义在可测空间上的概率测度；随机变量的律是由推前得到的一类分布。 $P$ 在可数集合 $\mathcal{X}$ 上的质量函数为 $p(x)$。本页所有对数均以 $2$ 为底，最小熵定义为

$$H_{\mathrm{\infty }}(P)=-{\log }_2\underset{x\in \mathcal{X}}{max}p(x).$$

等价地，若随机变量公理库随机变量Random variable · Random element从概率空间到可测空间的可测映射；实值情形是狭义随机变量。 $X\sim P$，观察者必须在看到任何额外信息前猜一次 $X$，最优策略是输出概率最大的结果，因此

$$p_{\mathrm{guess}}(X)=\underset{x}{max}\text{Pr}[X=x]=2^{-H_{\mathrm{\infty }}(P)}.$$

这项等式赋予最小熵直接的预测含义。$H_{\mathrm{\infty }}(P)\ge k$ 当且仅当每个点的概率都不超过 $2^{-k}$；满足该条件的分布常称为 $k$-source。定义针对整个分布，而不是对某次抽到的 $x$ 计算 $-\log p(x)$：后者是随样本变化的自信息，最小熵则先取最大点概率，再取负对数。后文为讨论条件分布继续写 $H_{\mathrm{\infty }}(X)$，它只是 $X$ 的分布之最小熵的简写。

若支持集有限，便有

$$0\le H_{\mathrm{\infty }}(X)\le {\log }_2|\mathrm{supp}(X)|.$$

右侧等号当且仅当 $X$ 在支持集上均匀，确定变量则取左侧等号。对同一离散分布，Shannon 熵公理库Shannon 熵Shannon entropy · Information entropy随机变量不确定性的平均信息量，以最优编码所需位数为基本解释。满足 $H(X)\ge H_{\mathrm{\infty }}(X)$，因为平均信息量不会小于由最大概率给出的最低信息量；两者可以相差很大，故不能在提取器参数中互换。

存在经典旁信息 $Z$ 时，有两种常见但不同的条件版本。最坏情形条件最小熵为

$$H_{\mathrm{\infty }}(X\mid Z)=\underset{z:\text{Pr}[Z=z]>0}{min}{H}_{\mathrm{\infty }}(X\mid Z=z),$$

它由最泄漏的那个 $z$ 决定。平均条件最小熵通常写作

$${\tilde{H}}_{\mathrm{\infty }}(X\mid Z)=-{\log }_2\sum _z\text{Pr}[Z=z]\underset{x}{max}\text{Pr}[X=x\mid Z=z]=-{\log }_2{p}_{\mathrm{guess}}(X\mid Z).$$

后者允许猜测者先看到 $z$ 再选最佳 $x$，更直接对应平均猜测概率。这两种定义都不是把 Shannon 条件熵公式中的 $H$ 机械替换成 $H_{\mathrm{\infty }}$；量词和平均的顺序决定了不同安全保证。

直觉 ​

Shannon 熵询问长期平均需要多少信息描述样本，最小熵则盯住攻击者最有利的单次猜测。只要有一个结果堆积了很大概率，攻击者就会始终猜它；分布其余部分即使铺得极宽、贡献了很高的平均熵，也不能抵消这个预测捷径。

因此，最小熵把“弱随机源”变成可操作的上界：$k$ bit 最小熵不是说源含有 $k$ 个独立公平 bit，而是说任何单点概率至多 $2^{-k}$。概率质量可以高度不规则，也可以带复杂相关性；提取器必须对所有满足这一点界的源统一工作。

例子与边界 ​

若 $X$ 在恰好 $2^k$ 个点上均匀，则每点概率为 $2^{-k}$，所以 $H_{\mathrm{\infty }}(X)=k$，同时 $H(X)=k$。这类 flat source 是分析一般 $k$-source 的基本图像，但定义并不要求概率相等，也不要求支持集能高效枚举。

考虑字母表 $\{0,1,\dots ,2^k\}$ 上的分布：以概率 $1/2$ 输出 $0$，其余 $2^k$ 个结果各以概率 $2^{-(k+1)}$ 输出。最大点概率为 $1/2$，故 $H_{\mathrm{\infty }}(X)=1$；攻击者始终猜 $0$ 就能成功一半。与此同时，

$$H(X)=1+\frac{k}{2},$$

会随 $k$ 增长。这个例子说明平均不确定性很大，仍可能只有一个 bit 的最小熵。

最小熵不描述典型码长，也不保证各 bit 均匀或独立。一个 $n$ bit 变量可拥有接近 $n$ 的最小熵，却在某个公开谓词上有偏差；反过来，一个变量的边缘分布均匀，在与旁信息联合考虑后也可能完全可预测。做隐私放大或密钥派生时，应使用包含攻击者旁信息的条件或平滑最小熵版本，而不能只计算无条件 $H_{\mathrm{\infty }}(X)$。

统计估计还有样本边界。有限观测中没有见到高概率点，并不能证明真实最大概率小；要从数据给出最小熵下界，需要明确的源模型、置信界和对未见事件的控制。密码协议通常把 min-entropy 下界作为经过验证的假设或由物理模型推出的参数，而非由直方图直接宣告。

推论与应用 ​

最小熵是有种子随机性提取器公理库有种子随机性提取器Seeded randomness extractor · Seeded extractor用独立均匀短种子把任意高最小熵弱源映为统计上接近均匀的输出。、剩余哈希引理、隐私放大和模糊提取器的输入度量。它把攻击者最佳猜测成功率转成 bit 数，使“源还剩多少可提取随机性”可以与输出长度和统计误差放在同一参数式中比较。

旁信息版本尤其适合安全分析：公开 transcript、设备读数或泄漏变量都会改变条件猜测概率。平滑最小熵进一步允许丢弃总概率很小的异常区域，支撑有限块长与量子信息中的精细界；使用时必须声明平滑距离、平滑参数以及旁信息是经典还是量子，不能把不同版本的数值直接互换。

参考资料

• Alfréd Rényi, “On Measures of Entropy and Information,” Proceedings of the Fourth Berkeley Symposium, 1961。
• Yevgeniy Dodis, Leonid Reyzin, and Adam Smith, “Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data,” EUROCRYPT 2004，average min-entropy and extraction。
• Salil P. Vadhan, Pseudorandomness, Foundations and Trends in Theoretical Computer Science 7(1–3), 2012，randomness sources and extractors。