信息论安全与概率论

目录

一. Markov不等式

二. 选择引理

三. Chebyshev不等式

四. Chernov上限

4.1 变量大于

4.2 变量小于

---

信息论安全中会用到很多概率论相关的上界，本文章将梳理几个论文中常用的定理，重点关注如何理解这些定理以及怎么用。

一. Markov不等式

假定X为非负且为实数的随机变量，令为该变量的数学期望，可得：

理解：代表事件的集合，该定理用来描述概率的上界，且该上界与数学期望相关。

二. 选择引理

令，左边的代表随机变量，右边代表该随机变量取值的字母集。假定某函数，将这些函数集中在一起形成函数集，另外该函数集内函数的个数与n无关。给定如下条件：

一定存在该变量中一个具体的数，满足：

理解：如果经过函数变化后的随机变量的数学期望有上界，那么该函数的某些取值也有上界。

证明：

先做一个简单的改写，令，可以把看成一个常数，根据联合界定理(union bound)，来看一个很有意思的概率：

马上使用刚才谈到的Markov不等式，右边不就是某个变量大于某个数的概率，可得：

条件告诉我们：

直接带入可得：

推导这么久，无非是想说

翻译成人话就是。事件的概率小于1，也就是存在。接下来就是计算复杂性理论很喜欢用到的一些转化。定理条件说是有限的，也就是一个常数，并且该常数与n无关，常数在计算复杂性中可以忽略，所以可将等效为。

证明完毕。

简化理解：以上推导只是严格按照概率论格式来推导，所以看起来可能有点复杂。让我们来简化下。该定理说明当期望有上限时，至少存在一个变量的值也是这个上限（是不是很简单）。只不是今天的上限满足，（安全领域很喜欢研究渐近性）。

三. Chebyshev不等式

令X为随机变量，可得：

理解：变量的值与期望值不会相差太大，该上限与方差相关。

四. Chernov上限

4.1 变量大于

令X为随机变量，可得：

理解：将s看成一个常数，代表变量大于等于a的概率；代表对变量操作指数变换后，求数学期望；该定理反映了变量大于某值时对应的概率有上限，该上限与数学期望有关。与Markov不等式相比，多了一个s，在实际信息论安全推导时，可以设定任何自己想要的参数。

4.2 变量小于

令X为随机变量，可得：

该定理的理解与4.1类似，就不重复描述了。