定义2.1

一个离散的随机变量,比方说,由有限集合和定义在上的概率分布组成。我们用表示随机变量取时的概率。如果随机变量是固定的,我们有时缩写成。对任意的，有，并且

定理2.1（Bayes定理）

由

得，如果,那么

推论2.2

X和Y是统计独立的随机变量，当且仅当对所有的和,有

证明：

定义2.3

一个密码体制具有完善保密性，即，如果对于任意的 和,有。也就是说，给定密文y,明文x的后验概率等于明文x的先验概率。

定义2.4

假设随机变量X在有限集合上取值，则随机变量X的熵的定义为：

如果|X|=n并且对于所有的,Pr[x]=1/n,那么。同样，容易知道对于任意的随机变量X,。H(X)=0当且仅当对于某一个,,对于所有的,。

定理2.4

假设密码体制满足。这个密码体制是完善保密的，当且仅当每个密钥被使用的概率都是,并且对于任意的和,存在唯一的密钥使得。

定理2.5(Jensen不等式)

假设是区间上的连续的严格的凸函数,,其中 。那么

其中 。当且仅当 ,等号成立。

定理2.6

假设是一个随机变量，概率分布为,其中。那么,当且仅当时等号成立。

定义2.6

假设X和Y是两个随机变量。对于Y的任何固定值y,得到一个X上的（条件）概率分布；记相应的随机变量为X|y。显然，

定义条件熵为熵取遍所有的y的加权平均值:

定理2.7

,当且仅当X和Y统计独立时等号成立。

定理2.8

推论2.9

由定理2.7和定理2.8可得，

当且仅当X和Y统计独立时，等号成立。