【现代密码学理论与实践】概率论和信息论

标准符号

概率论的基本概念

令S为一个任意确定的点的集合，称之为概率空间（或样本空间）。任意元素 x∈S 成为样点（也称为结果、简单事件或不可分事件。一个事件（也成为合成事件或可分事件）是 S 的一个子集，通常用以一个大写字母表示（比如 E ）。一次实验或观察是一种从 S 中产生（取出）一个点的动作。一个事件 E 的发生就是一个实验产生某个点 x∈S ，并满足 x∈E 。

概率的经典定义

假设一个实验可以从 n=#S 个等可能的点中产生一个点，并且每次实验必须产生一个点。令 m 表示事件 E 包含的点的数目，那么称 m/n 为事件 E 发生的概率，并记为

$$Prob[E]=\frac{m}{n}$$

概率的统计定义

假设在相同条件下进行了 n 次实验，其中事件 E 发生了 μ 次。如果对所有足够大的 n ， μ/n 保持不变，那么就说事件E的概率为 μ/n ，记为

$$Prob[E]≈\frac{μ}{n}$$

基本运算

加法规则

条件概率

设 E、F 为两个事件，且 E 的概率不为 0 。在 E 发生的条件下 F 发生的概率称为已知 E 时 F 的条件概率，记为

$$Prob[E|F]=\frac{Prob[E∩F]}{Prob[E]}$$

独立事件

事件 E、F 是相互独立的，当且仅当

$$Prob[E|F]=Prob[F]$$

乘法规则

全概率定律★

随机变量及其概率分布

离散随机变量及其分布函数

1. 一个（离散）随机变量是一个实验的数字化结果。它是定义在一个（离散）样本空间上的函数。

2. 设 S 为一个（离散）概率空间，ξ 为一个随机变量。ξ 的（离散）分布函数是 S→R 的一个函数，以一个概率值

   $$Prob[ξ=x_i]=p_i（i=1,2,...,S）$$

   列表为条件，并满足下面的条件

   $$1.p_i≥0$$ $$2.\sum_{1}^{S}{p_i}=1$$

二项式分布

如果随机变量 ξn 取值为0，1，…，n，且对每一个 p ，0<p<1 ，有

$$Prob[ξ_n=k]=(_k^n)p^k(1-p)^(n-k)（k=0,1,2,...,n）$$

那么称 ξn 服从贝努利分布，用 b(k ; n , p) 表示一个贝努利项，其中 k=0,1,2,…,n 且 0<p<1 。

中心项

相邻的二项式两项的比值是

$$\frac{b(k；n，p)}{b(k-1 ；n ，p)}=\frac{(n-k+1)p}{k(1-p)}=1+\frac{(n+1)p-k}{k(1-p)}$$

当 k<(n+1)p 时，其值为正；当 k>(n+1)p 时，其值为负。因此在 k=(n+1)p 时，二项式 b(k ; n , p) 达到最大值。此二项式 b((n+1)p ; n , p) 称为中心项。