信息论安全与概率论

发布时间:2023年12月21日

目录

一. Markov不等式

二. 选择引理

三. Chebyshev不等式

四. Chernov上限

4.1 变量大于

4.2 变量小于


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

一. Markov不等式

假定X为非负且为实数的随机变量,令E_X[X]为该变量的数学期望,可得:

\forall a>0\quad P[X\geq a]\leq \frac{E_X[X]}{a}

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

二. 选择引理

X_n\in \mathcal{X}_n,左边的X_n代表随机变量,右边\mathcal{X}_n代表该随机变量取值的字母集。假定某函数f:\mathcal{X}_n\to R^+,将这些函数集中在一起形成函数集\mathcal{F},另外该函数集内函数的个数|\mathcal{F}|与n无关。给定如下条件:

\forall f\in \mathcal{F}\quad E_{X_n}[f(X_n)]\leq \delta(n)

一定存在该变量X_n中一个具体的数x_n,满足:

\forall f\in \mathcal{F}\quad f(x_n)\leq \delta(n)

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

证明

先做一个简单的改写,令\epsilon_n=\delta(n),可以把|\mathcal{F}|,\epsilon_n看成一个常数,根据联合界定理(union bound),来看一个很有意思的概率:

P_{X_n}[\cup_{f\in\mathcal{F}}\lbrace f(X_n)\geq(|\mathcal{F}|+1)\epsilon_n]\leq \sum_{f\in\mathcal{F}}P_{X_n}[f(X_n)\geq(|\mathcal{F}|+1)\epsilon_n]

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

\sum_{f\in\mathcal{F}}P_{X_n}[f(X_n)\geq(|\mathcal{F}|+1)\epsilon_n]\leq \sum_{f\in\mathcal{F}}\frac{E_{X_n}[f(X_n)]}{(|\mathcal{F}|+1)\epsilon_n}

条件告诉我们:

E_{X_n}[f(X_n)]\leq \epsilon_n

直接带入可得:

\sum_{f\in\mathcal{F}}\frac{E_{X_n}[f(X_n)]}{(|\mathcal{F}|+1)\epsilon_n}\leq \frac{|\mathcal{F}|}{|\mathcal{F}|+1}<1

推导这么久,无非是想说

P_{X_n}[\cup_{f\in\mathcal{F}}\lbrace f(X_n)\geq(|\mathcal{F}|+1)\epsilon_n]<1

翻译成人话就是。事件f(X_n)\geq(|\mathcal{F}|+1)\epsilon_n的概率小于1,也就是存在f(X_n)<(|\mathcal{F}|+1)\epsilon_n。接下来就是计算复杂性理论很喜欢用到的一些转化。定理条件说|\mathcal{F}|是有限的,也就是一个常数,并且该常数与n无关,常数在计算复杂性中可以忽略,所以可将(|\mathcal{F}|+1)\epsilon_n等效为\delta(n)

证明完毕。

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

三. Chebyshev不等式

令X为随机变量,可得:

\forall a>0\quad P[|X-E[X]\geq a]\leq \frac{Var(x)}{a^2}

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

四. Chernov上限

4.1 变量大于

令X为随机变量,可得:

\forall s>0\quad P[X\geq a]\leq E[e^{sX}]e^{-sa}

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

4.2 变量小于

令X为随机变量,可得:

\forall s<0\quad P[X\leq a]\leq E[e^{sX}]e^{-sa}

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

文章来源:https://blog.csdn.net/forest_LL/article/details/131277165
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。