跳到主要内容

文章 | 密码学基础：前置知识

提示

新学期选修密码学，第一节课记了这些笔记，于是退课。

离散随机变量​

对于给定的有限集合 Ω={a1,a2,⋯ ,an}\Omega=\{a_1,a_2,\cdots,a_n\}，如果变量 XX 满足 ∀a∈Ω,Pr[X=a]=p(a)\forall a\in\Omega,\mathrm{Pr}[X=a]=p(a)，其中 p(x)p(x) 是映射 p(x):Ω→[0,1]p(x): \Omega\to [0,1]，且满足 ∑a∈Ωp(a)=1\sum_{a\in\Omega}p(a)=1，那么称 XX 是 Ω\Omega 上的一个服从概率分布（distribution） pp 的离散随机变量（random variable）。

对概率分布 pp，可以定义其熵（entropy）：H(p)=∑a∈Ωp(a)log⁡1p(a)H(p)=\sum_{a\in\Omega}p(a)\log \frac{1}{p(a)}，这也被称为随机变量 XX 的熵 H(X)H(X)。

根据函数 f(x)=xlog⁡1xf(x)=x\log \frac{1}{x} 的凸性，可知当概率分布中各项的概率相等时，即 p(a)=1∣Ω∣p(a)=\frac{1}{|\Omega|}，熵达到最大值 H(p)=log⁡∣Ω∣H(p)=\log |\Omega|。这样的分布称为均匀分布（uniform distribution）。

对于多个离散随机变量，可以定义联合分布（joint distribution）。如果 p(x,y):Ω1×Ω2→[0,1]p(x,y): \Omega_1\times\Omega_2\to[0,1] 满足 ∀a∈Ω1,b∈Ω2,Pr[X=a,Y=b]=p(a,b)\forall a\in\Omega_1,b\in\Omega_2, \mathrm{Pr}[X=a,Y=b]=p(a,b)，那么称 X,YX, Y 服从联合分布 pp，记作 (X,Y)∼p(X,Y)\sim p。

同样地，可以定义多个随机变量的联合熵（joint entropy）：若(X,Y)∼p(X,Y)\sim p，定义 H(X,Y)=∑a∈Ω1b∈Ω2p(a,b)log⁡1p(a,b)H(X,Y)=\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}p(a,b)\log \frac{1}{p(a,b)}。

给定联合分布后，可以重新计算每个变量单独的分布，称为这个变量的边缘分布（marginal distribution）：p1(a)=∑b∈Ω2p(a,b)p_1(a)=\sum_{b\in\Omega_2}p(a,b)，p2(b)=∑a∈Ω1p(a,b)p_2(b)=\sum_{a\in\Omega_1}p(a,b)。

如果联合分布可以表示为边缘分布的乘积，称这两个随机变量独立（independent）。

当两个变量 X,YX,Y 独立时，计算得

H(X,Y)=∑a∈Ω1b∈Ω2p(a,b)log⁡1p(a,b)=∑a∈Ω1b∈Ω2p(a)p(b)(log⁡1p(a)+log⁡1p(b))=∑b∈Ω2p(b)∑a∈Ω1p(a)log⁡1p(a)+∑a∈Ω1p(a)∑b∈Ω2p(b)log⁡1p(b)=H(X)+H(Y)\begin{align} H(X,Y)&=\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}p(a,b)\log \frac{1}{p(a,b)}\\ &=\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}p(a)p(b)\left(\log \frac{1}{p(a)}+\log \frac{1}{p(b)}\right)\\ &=\sum_{b\in\Omega_2}p(b)\sum_{a\in\Omega_1}p(a)\log\frac{1}{p(a)}+\sum_{a\in\Omega_1}p(a)\sum_{b\in\Omega_2}p(b)\log\frac{1}{p(b)}\\ &=H(X)+H(Y) \end{align}\\

条件熵​

通过条件概率，可以定义一个随机变量 XX 关于随机事件 ee 的条件熵（conditional entropy）：H(X∣e)=∑a∈ΩPr[X=a∣e]log⁡1Pr[X=a∣e]H(X|e)=\sum_{a\in\Omega}\mathrm{Pr}[X=a|e]\log\frac{1}{\mathrm{Pr}[X=a|e]}。

随机变量 XX 相对于随机变量 YY 的条件熵等于 XX 关于 YY 的某一取值的条件熵在 YY 的边缘分布下的期望：H(X∣Y)=∑b∈Ω2Pr[Y=b]H(X∣Y=b)H(X|Y)=\sum_{b\in\Omega_2}\mathrm{Pr}[Y=b]H(X|Y=b)。

对上式变形，可以得出条件熵另外的两种表示：

H(X∣Y)=∑b∈Ω2Pr[Y=b]H(X∣Y=b)=∑b∈Ω2Pr[Y=b]∑a∈Ω1Pr[X=a∣Y=b]log⁡1Pr[X=a∣Y=b]=∑a∈Ω1b∈Ω2Pr[X=a,Y=b]log⁡Pr[Y=b]Pr[X=a,Y=b]\begin{align} H(X|Y)&=\sum_{b\in\Omega_2}\mathrm{Pr}[Y=b]H(X|Y=b)\\ &=\sum_{b\in\Omega_2}\mathrm{Pr}[Y=b]\sum_{a\in\Omega_1}\mathrm{Pr}[X=a|Y=b]\log\frac{1}{\mathrm{Pr}[X=a|Y=b]}\\ &=\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}\mathrm{Pr}[X=a,Y=b]\log\frac{\mathrm{Pr}[Y=b]}{\mathrm{Pr}[X=a,Y=b]}\\ \end{align}\\
H(X∣Y)=∑a∈Ω1b∈Ω2Pr[X=a,Y=b]log⁡Pr[Y=b]Pr[X=a,Y=b]=∑a∈Ω1b∈Ω2Pr[X=a,Y=b]log⁡1Pr[X=a,Y=b]−∑b∈Ω2(∑a∈Ω1Pr[X=a,Y=b])log⁡1Pr[Y=b]=H(X,Y)−∑b∈Ω2Pr[Y=b]log⁡1Pr[Y=b]=H(X,Y)−H(Y)\begin{align} H(X|Y)&=\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}\mathrm{Pr}[X=a,Y=b]\log\frac{\mathrm{Pr}[Y=b]}{\mathrm{Pr}[X=a,Y=b]}\\ &=\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}\mathrm{Pr}[X=a,Y=b]\log\frac{1}{\mathrm{Pr}[X=a,Y=b]}-\sum_{b\in\Omega_2}\left(\sum_{a\in\Omega_1}\mathrm{Pr}[X=a,Y=b]\right)\log\frac{1}{\mathrm{Pr}[Y=b]}\\ &=H(X,Y)-\sum_{b\in\Omega_2}\mathrm{Pr}[Y=b]\log\frac{1}{\mathrm{Pr}[Y=b]}\\ &=H(X,Y)-H(Y)\\ \end{align}\\

互信息​

互信息（mutual information）用于衡量两个随机变量的相关性。其定义为以一个随机变量为条件后，熵的减少值。

I(X;Y)=H(X)−H(X∣Y)I(X;Y)=H(X)-H(X|Y)\\

代入 H(X∣Y)=H(X,Y)−H(X)H(X|Y)=H(X,Y)-H(X) ，得到

I(X;Y)=H(X)+H(Y)−H(X,Y)I(X;Y)=H(X)+H(Y)-H(X,Y)\\

从这里可以看出互信息是对称的。因此有

I(X;Y)=H(X)−H(X∣Y)=H(Y)−H(Y∣X)=H(X)+H(Y)−H(X,Y)\begin{align} I(X;Y)&=H(X)-H(X|Y)=H(Y)-H(Y|X)\\ &=H(X)+H(Y)-H(X,Y)\\ \end{align}\\

进一步变形，可以得到

I(X;Y)=∑a∈Ω1p1(a)log⁡1p1(a)+∑b∈Ω2p2(b)log⁡1p2(b)−∑a∈Ω1b∈Ω2p(a,b)log⁡1p(a,b)=∑a∈Ω1(∑b∈Ω2p(a,b))log⁡1p1(a)+∑b∈Ω2(∑a∈Ω1p(a,b))log⁡1p2(b)−∑a∈Ω1b∈Ω2p(a,b)log⁡1p(a,b)=∑a∈Ω1b∈Ω2p(a,b)log⁡p(a,b)p(a)p(b)\begin{align} I(X;Y)&=\sum_{a\in\Omega_1}p_1(a)\log\frac{1}{p_1(a)}+\sum_{b\in\Omega_2}p_2(b)\log\frac{1}{p_2(b)}-\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}p(a,b)\log\frac{1}{p(a,b)}\\ &=\sum_{a\in\Omega_1}\left(\sum_{b\in\Omega_2}p(a,b)\right)\log\frac{1}{p_1(a)}+\sum_{b\in\Omega_2}\left(\sum_{a\in\Omega_1}p(a,b)\right)\log\frac{1}{p_2(b)}-\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}p(a,b)\log\frac{1}{p(a,b)}\\ &=\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}p(a,b)\log\frac{p(a,b)}{p(a)p(b)}\\ \end{align}\\

于是可以证明互信息的非负性：

I(X;Y)=∑a∈Ω1b∈Ω2p(a,b)log⁡p(a,b)p(a)p(b)=−∑a∈Ω1b∈Ω2p(a,b)log⁡p(a)p(b)p(a,b)≥−log⁡∑a∈Ω1b∈Ω2p(a,b)p(a)p(b)p(a,b)=0\begin{align} I(X;Y)&=\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}p(a,b)\log\frac{p(a,b)}{p(a)p(b)}\\ &=-\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}p(a,b)\log\frac{p(a)p(b)}{p(a,b)}\\ &\ge-\log\sum_{\substack{a\in\Omega_1\\b\in\Omega_2}}p(a,b)\frac{p(a)p(b)}{p(a,b)}\\ &=0 \end{align}\\

由此可知 H(X∣Y)≤H(X)H(X|Y)\le H(X)。

当随机变量 XX 与 YY 独立时，有 H(X,Y)=H(X)+H(Y)H(X,Y)=H(X)+H(Y)，可知 H(X∣Y)=H(X),H(Y∣X)=H(Y),I(X;Y)=0H(X|Y)=H(X), H(Y|X)=H(Y), I(X;Y)=0。

反过来，当互信息 I(X;Y)=0I(X;Y)=0 时，从上面不等式的取等条件可以看出，p(a)p(b)p(a,b)\frac{p(a)p(b)}{p(a,b)} 不依赖于 a,ba,b 的选取，进而可知 XX 与 YY 独立。

当随机变量 YY 完全依赖于 XX 时，也即 Pr[X=a,Y=b]={1,b=f(a)0,otherwise\mathrm{Pr}[X=a,Y=b]=\begin{cases}1, &b=f(a)\\0, &\text{otherwise}\end{cases} ，有

H(X,Y)=∑a∈Ωb∈f(Ω)p(a,b)log⁡1p(a,b)=∑a∈Ωp(a,f(a))log⁡1p(a,f(a))=∑a∈Ωp(a)log⁡1p(a)=H(X)\begin{align} H(X,Y)&=\sum_{\substack{a\in\Omega\\b\in f(\Omega)}}p(a,b)\log\frac{1}{p(a,b)}\\ &=\sum_{a\in\Omega}p(a,f(a))\log\frac{1}{p(a,f(a))}\\ &=\sum_{a\in\Omega}p(a)\log\frac{1}{p(a)}\\ &=H(X)\\ \end{align}\\

因此，I(X;Y)=H(Y)I(X;Y)=H(Y)。

多元互信息​

对于多于两个的随机变量 X1,X2,⋯ ,XnX_1,X_2,\cdots,X_n，记其概率分布为 p:Ω1×Ω2×⋯×Ωn→[0,1]p:\Omega_1\times\Omega_2\times\cdots\times\Omega_n\to[0,1]，以及每个变量的边缘分布 Xi∼piX_i\sim p_i，于是可以定义多元联合熵

H(X1,X2,⋯ ,Xn)=∑x1∈Ω1∑x2∈Ω2⋯∑xn∈Ωnp(x1,x2⋯ ,xn)log⁡1p(x1,x2⋯ ,xn)H(X_1,X_2,\cdots,X_n)=\sum_{x_1\in\Omega_1}\sum_{x_2\in\Omega_2}\cdots\sum_{x_n\in\Omega_n} p(x_1,x_2\cdots,x_n)\log\frac{1}{p(x_1,x_2\cdots,x_n)}\\

以及关于随机事件 ee 的多元条件熵

H(X1,X2,⋯ ,Xn∣e)=∑x1∈Ω1∑x2∈Ω2⋯∑xn∈Ωnp(x1,x2⋯ ,xn∣e)log⁡1p(x1,x2⋯ ,xn∣e)H(X_1,X_2,\cdots,X_n|e)=\sum_{x_1\in\Omega_1}\sum_{x_2\in\Omega_2}\cdots\sum_{x_n\in\Omega_n} p(x_1,x_2\cdots,x_n|e)\log\frac{1}{p(x_1,x_2\cdots,x_n|e)}\\

考虑三个随机变量 X,Y,ZX,Y,Z 的条件熵，定义

H(X,Y∣Z)=∑zPr[Z=z]⋅H(X,Y∣Z=z)=∑x∑y∑zPr[Z=z]⋅Pr[X=x,Y=y∣Z=z]log⁡1Pr[X=x,Y=y∣Z=z]=∑x∑y∑zPr[X=x,Y=y,Z=z](log⁡1Pr[X=x,Y=y,Z=z]−log⁡1Pr[Z=z])=H(X,Y,Z)−∑z(∑x∑yPr[X=x,Y=y,Z=z])log⁡1Pr[Z=z]=H(X,Y,Z)−∑zPr[Z=z]log⁡1Pr[Z=z]=H(X,Y,Z)−H(Z)\begin{align} H(X,Y|Z)&=\sum_z\mathrm{Pr}[Z=z]\cdot H(X,Y|Z=z)\\ &=\sum_x\sum_y\sum_z\mathrm{Pr}[Z=z]\cdot\mathrm{Pr}[X=x,Y=y|Z=z]\log\frac{1}{\mathrm{Pr}[X=x,Y=y|Z=z]}\\ &=\sum_x\sum_y\sum_z\mathrm{Pr}[X=x,Y=y,Z=z]\left(\log\frac{1}{\mathrm{Pr}[X=x,Y=y,Z=z]}-\log\frac{1}{\mathrm{Pr}[Z=z]}\right)\\ &=H(X,Y,Z)-\sum_z\left(\sum_x\sum_y\mathrm{Pr}[X=x,Y=y,Z=z]\right)\log\frac{1}{\mathrm{Pr}[Z=z]}\\ &=H(X,Y,Z)-\sum_z \mathrm{Pr}[Z=z]\log\frac{1}{\mathrm{Pr}[Z=z]}\\ &=H(X,Y,Z)-H(Z)\\ \end{align}\\

接下来定义关于随机事件 ee 的条件互信息

I(X;Y∣e)=H(X∣e)+H(Y∣e)−H(X,Y∣e)I(X;Y|e)=H(X|e)+H(Y|e)-H(X,Y|e)\\

以及关于随机变量的条件互信息

I(X;Y∣Z)=∑zPr[Z=z]⋅I(X;Y∣Z=z)=∑zPr[Z=z]⋅(H(X∣Z=z)+H(Y∣Z=z)−H(X,Y∣Z=z))=H(X∣Z)+H(Y∣Z)−H(X,Y∣Z)\begin{align} I(X;Y|Z)&=\sum_{z}\mathrm{Pr}[Z=z]\cdot I(X;Y|Z=z) \\ &=\sum_z \mathrm{Pr}[Z=z]\cdot \left(H(X|Z=z)+H(Y|Z=z)-H(X,Y|Z=z)\right)\\ &=H(X|Z)+H(Y|Z)-H(X,Y|Z) \end{align}

继续定义多元互信息

I(X1;X2;⋯ ;Xn)=∑i=1nH(Xi)−∑1≤i<j≤nH(Xi,Hj)+⋯+(−1)n−1H(X1,X2,⋯ ,Xn)I(X_1;X_2;\cdots;X_n)=\sum_{i=1}^n H(X_i)-\sum_{1\le i<j\le n}H(X_i,H_j)+\cdots+(-1)^{n-1}H(X_1,X_2,\cdots,X_n)\\

特别地，有三元互信息

I(X;Y;Z)=H(X)+H(Y)+H(Z)−H(X,Y)−H(X,Z)−H(Y,Z)+H(X,Y,Z)=H(X)+H(Y)−H(X,Y)+2H(Z)−H(X,Z)−H(Y,Z)+H(X,Y∣Z)=I(X;Y)−H(X∣Z)−H(Y∣Z)+H(X,Y∣Z)=I(X;Y)−I(X;Y∣Z)\begin{align} I(X;Y;Z)&=H(X) + H(Y) + H(Z) −H(X, Y) −H(X, Z) −H(Y, Z) + H(X, Y, Z)\\ &=H(X) + H(Y) −H(X, Y) + 2H(Z) −H(X, Z) −H(Y, Z) + H(X, Y|Z)\\ &=I(X;Y) - H(X|Z)-H(Y|Z)+H(X,Y|Z)\\ &=I(X;Y) - I(X;Y|Z)\\ \end{align}\\

仿照二元互信息，可知

I(X;Y∣e)=∑x∑yPr[X=x,Y=y∣e]log⁡Pr[X=x,Y=y∣e]Pr[X=x∣e]⋅Pr[Y=y∣e]I(X;Y|e)=\sum_x\sum_y\mathrm{Pr}[X=x,Y=y|e]\log\frac{\mathrm{Pr}[X=x,Y=y|e]}{\mathrm{Pr}[X=x|e]\cdot\mathrm{Pr}[Y=y|e]}\\

于是

I(X;Y∣Z)=∑x∑y∑zPr[Z=z]⋅Pr[X=x,Y=y∣Z=z]⋅log⁡Pr[X=x,Y=y∣Z=z]Pr[X=x∣Z=z]⋅Pr[Y=y∣Z=z]=∑x∑y∑zPr[X=x,Y=y,Z=z]⋅(log⁡Pr[X=x,Y=y,Z=z]Pr[X=x,Z=z]⋅Pr[Y=y,Z=z]−log⁡1Pr[Z=z])=−H(Z)−∑x∑yPr[X=x,Y=y]∑zPr[X=x,Y=y,Z=z]Pr[X=x,Y=y]⋅log⁡Pr[X=x,Z=z]⋅Pr[Y=y,Z=z]Pr[X=x,Y=y,Z=z]≤−H(Z)−∑x∑yPr[X=x,Y=y]⋅log⁡∑zPr[X=x,Y=y,Z=z]Pr[X=x,Y=y]⋅Pr[X=x,Z=z]⋅Pr[Y=y,Z=z]Pr[X=x,Y=y,Z=z]=−H(Z)−∑x∑yPr[X=x,Y=y]⋅(log⁡1Pr[X=x,Y=y]+log⁡∑zPr[X=x,Z=z]⋅Pr[Y=y,Z=z])\begin{align} I(X;Y|Z)&=\sum_x\sum_y\sum_z\mathrm{Pr}[Z=z]\cdot\mathrm{Pr}[X=x,Y=y|Z=z]\cdot\log\frac{\mathrm{Pr}[X=x,Y=y|Z=z]}{\mathrm{Pr}[X=x|Z=z]\cdot\mathrm{Pr}[Y=y|Z=z]}\\ &=\sum_x\sum_y\sum_z\mathrm{Pr}[X=x,Y=y,Z=z]\cdot\left(\log\frac{\mathrm{Pr}[X=x,Y=y,Z=z]}{\mathrm{Pr}[X=x,Z=z]\cdot\mathrm{Pr}[Y=y,Z=z]}-\log\frac{1}{\mathrm{Pr}[Z=z]}\right)\\ &=-H(Z)-\sum_x\sum_y\mathrm{Pr}[X=x,Y=y]\sum_z\frac{\mathrm{Pr}[X=x,Y=y,Z=z]}{\mathrm{Pr}[X=x,Y=y]}\cdot\log\frac{\mathrm{Pr}[X=x,Z=z]\cdot\mathrm{Pr}[Y=y,Z=z]}{\mathrm{Pr}[X=x,Y=y,Z=z]}\\ &\le-H(Z)-\sum_x\sum_y\mathrm{Pr}[X=x,Y=y]\cdot\log\sum_z\frac{\mathrm{Pr}[X=x,Y=y,Z=z]}{\mathrm{Pr}[X=x,Y=y]}\cdot\frac{\mathrm{Pr}[X=x,Z=z]\cdot\mathrm{Pr}[Y=y,Z=z]}{\mathrm{Pr}[X=x,Y=y,Z=z]}\\ &=-H(Z)-\sum_x\sum_y\mathrm{Pr}[X=x,Y=y]\cdot\left(\log\frac{1}{\mathrm{Pr}[X=x,Y=y]}+\log\sum_z\mathrm{Pr}[X=x,Z=z]\cdot\mathrm{Pr}[Y=y,Z=z]\right)\\ \end{align}\\

马尔可夫不等式​

对实数域上的离散随机变量 XX，记期望 E(X)=∑a∈Ωap(a)E(X)=\sum_{a\in\Omega}ap(a)，当 XX 恒非负时，有马尔可夫不等式（Markov inequality）：

Pr[X≥a]=∑b∈Ωb≥aap(b)a≤∑b∈Ωb≥abp(b)a≤∑b∈Ωbp(b)a=E(X)a\mathrm{Pr}[X\ge a]=\frac{\sum_{\substack{b\in\Omega\\b\ge a}}ap(b)}{a}\le\frac{\sum_{\substack{b\in\Omega\\b\ge a}}bp(b)}{a}\le \frac{\sum_{b\in\Omega}bp(b)}{a}=\frac{\mathbb{E}(X)}{a}\\

如果 XX 是另一个随机变量 YY 到其均值的距离的平方，则有切比雪夫不等式（Chebyshev inequality）：

Pr[∣Y−EY∣≥c]=Pr[(Y−EY)2≥c2]≤E((Y−EY)2)c2=D(Y)c2\mathrm{Pr}[|Y-\mathbb{E}Y|\ge c]=\mathrm{Pr}[(Y-\mathbb{E}Y)^2\ge c^2]\le\frac{\mathbb{E}((Y-\mathbb{E}Y)^2)}{c^2}=\frac{\mathbb{D}(Y)}{c^2}\\

切比雪夫不等式描述了方差与随机变量偏离均值的程度之间的关系。

对于一般的多个随机变量 X1,X2,⋯ ,XnX_1, X_2,\cdots, X_n，记 X=∑i=1nXiX=\sum_{i=1}^n X_i，代入切比雪夫不等式有

Pr[∣1n∑i=1nXi−1n∑i=1nEXi∣≥c]=Pr[∣∑i=1nXi−∑i=1nEXi∣≥nc]≤D(X)n2c2=1n2c2∑i=1nDXi\mathrm{Pr}\left[\left|\frac{1}{n}\sum_{i=1}^nX_i-\frac{1}{n}\sum_{i=1}^n\mathbb{E}X_i\right|\ge c\right]=\mathrm{Pr}\left[\left|\sum_{i=1}^nX_i-\sum_{i=1}^n\mathbb{E}X_i\right|\ge nc\right]\le\frac{\mathbb{D}(X)}{n^2c^2}=\frac{1}{n^2c^2}\sum_{i=1}^n\mathbb{D}X_i\\

若 X1,X2,⋯ ,XnX_1, X_2,\cdots, X_n 是同分布的，记均值 μ=E(Xi)\mu=\mathbb{E}(X_i)，方差 σ2=D(Xi)\sigma^2=\mathbb{D}(X_i)，则

Pr[∣1n∑i=1nXi−μ∣≥c]≤σ2nc2\mathrm{Pr}\left[\left|\frac{1}{n}\sum_{i=1}^nX_i-\mu\right|\ge c\right]\le\frac{\sigma^2}{nc^2}\\

令 n→∞n\to\infty，则

lim⁡n→∞Pr[∣1n∑i=1nXi−μ∣≥c]=0\lim_{n\to\infty}\mathrm{Pr}\left[\left|\frac{1}{n}\sum_{i=1}^nX_i-\mu\right|\ge c\right]=0\\

这就是弱大数定律（weak law of large numbers）。

切诺夫界​

如果对 X1,X2,⋯ ,XnX_1, X_2,\cdots, X_n 有更多假设，可以给出比弱大数定律更强的估计。

若 X1,X2,⋯ ,XnX_1, X_2,\cdots, X_n 为独立泊松实验，即 Xi∈{0,1}X_i\in\{0,1\}，Pr[Xi=1]=pi\mathrm{Pr}[X_i=1]=p_i，记 X=∑i=1nXiX=\sum_{i=1}^n X_i ，μ=EX=∑i=1npi\mu=\mathbb{E}X=\sum_{i=1}^n p_i，那么

Pr[∑i=1nXi≥(1+δ)μ]=Pr[etX≥e(1+δ)tμ]≤E(etX)e(1+δ)tμ=1e(1+δ)tμ∏i=1nE(etXi)=1e(1+δ)tμ∏i=1n(piet+1−pi)≤1e(1+δ)tμ∏i=1nexp⁡(pi(et−1))=1e(1+δ)tμexp⁡(∑i=1npi(et−1))=exp⁡(μ(et−1))exp⁡((1+δ)tμ)=exp⁡(μ(1+δ)(et−ln⁡(1+δ)−11+δ−t))\begin{align} \mathrm{Pr}\left[\sum_{i=1}^nX_i\ge(1+\delta)\mu\right]&=\mathrm{Pr}\left[e^{tX}\ge e^{(1+\delta)t\mu}\right]\\ &\le\frac{\mathbb{E}(e^{tX})}{e^{(1+\delta)t\mu}}\\ &=\frac{1}{e^{(1+\delta)t\mu}}\prod_{i=1}^n \mathbb{E}(e^{tX_i})\\ &=\frac{1}{e^{(1+\delta)t\mu}}\prod_{i=1}^n (p_ie^t+1-p_i)\\ &\le\frac{1}{e^{(1+\delta)t\mu}}\prod_{i=1}^n \exp(p_i(e^t-1))\\ &=\frac{1}{e^{(1+\delta)t\mu}}\exp\left(\sum_{i=1}^np_i(e^t-1)\right)\\ &=\frac{\exp(\mu(e^t-1))}{\exp((1+\delta)t\mu)}\\ &=\exp\left(\mu(1+\delta)\left(e^{t-\ln(1+\delta)}-\frac{1}{1+\delta}-t\right)\right) \end{align}\\

令 t=ln⁡(1+δ)t=\ln(1+\delta)，则

Pr[∑i=1nXi≥(1+δ)μ]≤(eδ(1+δ)1+δ)μ\mathrm{Pr}\left[\sum_{i=1}^nX_i\ge(1+\delta)\mu\right]\le \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu\\

同理，有

Pr[∑i=1nXi≤(1−δ)μ]≤(e−δ(1−δ)1−δ)μ\mathrm{Pr}\left[\sum_{i=1}^nX_i\le(1-\delta)\mu\right]\le \left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu\\

此二式称为切诺夫界（Chernoff bound）。

Loading...