密码学 ｜ 5.3.4 随机变量

5.3.4 随机变量

通常情况下与实验本身相比，我们更注重实验结果，例如，我们赢得或输掉一个比赛的概率。从数学上讲，这意味着我们对定义在事件上并在某个集合中取值的函数感兴趣。

定义 随机变量是一个函数，满足

其中，定义域是样本空间 ，值域是实数域。更一般地说，随机变量是一个值域为任意集合的的映射 ，例如，  可以是一个密钥的集合，或者是一个明文的集合。需要注意到的是，由于我们的样本空间是有限的，所以随机变量只有有限多个值。随机变量一般用于定义事件，比如，如果  是一个随机变量，那么任何一个实数  都可以定义三个事件，分别是

定义 设随机变量 ， 的概率分布函数定义为 

换句话说， 是  取值为  的概率。有时为了方便，在不会混淆的情况下也会记为 

注 5.27 在概率论中，人们经常使用  的分布函数来代替密度函数，即 。事实上，在研究无限样本空间上的概率时，使用  至关重要。然而，由于我们的样本空间是有限的，因此我们的随机变量是有限的和离散的，这两个概念基本上是可互换的。为了简单起见，我们将坚持使用密度函数。

在离散概率计算中经常出现许多标准密度函数。我们这里简要介绍一些比较常见的

例 5.28 均匀分布(Uniform Distribution)

设集合  包含  个元素，如 .设  为随机变量满足

这个随机变量  被称为均匀分布或具有均匀密度，因为  中的每个结果都有相同的可能性

例5.29 二项分布（Binomial Distribution）

假设一个实验有两个结果，成功或失败。设  表示成功的概率。实验进行了  次，随机变量  记录了成功的次数。样本空间  由长度为  的所有二进制字符串 组成，其中，如果第  次实验失败，则 ，如果第  次实验成功，则  为 。那么，随机变量  在  处的值简单地为 ，这是成功的次数。使用随机变量 ，我们可以将单个事件  的概率表示为  。于是我们可以表示成功  次为

后一行来表示有  种方法可以从  次实验中选择  次来成功。于是我们得到二项式密度函数

例5.30 超几何分布（Hypergeometric Distribution）

设一个盒子里有  个球，其中  个是红色  个是蓝色的。从盒子中不放回的随机选择  个球。设 表示选择的红色球的数量，那么  是整数随机变量 。当 ，那么这就和我们在 例 5.20 讨论的i情况一致。超几何分布函数为‍

(5.24)fX(i)=Pr(X=i)=(mi)(N−mn−i)(Nn)

例5.31 几何分布 (Geometric Distribution）

这里我们给出一个无限概率空间的例子。假设我们重复投掷一枚不公平的硬币，其中获得头像的概率是某个数字。设  为随机变量，表示第一次出现头像前所需的总投掷次数。请注意， 有可能取任何正整数值，因为我们有可能（虽然不太可能）一直投不出头像。

样本空间  由所有二进制字符串 组成，其中如果第  次不是头像，则 ，如果第  次投掷是头像，则 。注意，  是一个无限集合。我们通过指定一些初始掷骰的值，将概率分配给某些事件，即  的某些子集。因此，对于任何给定的有限二进制字符串 ，我们指定一个概率

（# 表示的数量）

随机变量  定义为

因此

于是我们得到公式

(5.25)fX(n)=Pr(X=n)=(1−p)n−1p,n=1,2,3,…

若一个随机变量有 5.25 的密度公式，则我们称之为其具有几何分布，因为序列  构造了一个几何级数。稍后，在 例5.37 中，我们将通过对无限几何级数求和来计算该  的期望值。

早些时候，我们研究了涉及两个或多个事件以各种方式相互作用的概率。我们现在讨论研究两个或多个随机变量间的相互作用。

定义 设两个随机变量 ， 和  的联合密度函数记为 ，意为  取 ， 取 ，因此

同样的，条件密度函数记为 ，意为当  取值为 ， 取  的概率：

如果满足下式，我们则称  是独立的

即  是独立事件。如果没有歧义的话，有时也简单地记为 。

例5.32

一个盒子内有四枚金币和三枚银币。随机抽取一枚硬币，检查并放回，然后随机抽取第二枚硬币并进行检查。设  是金币的数量，  是银币的数量。为了找到联合密度函数 ，我们需要计算事件  的概率。方便起见，这里我们定义两个额外的随机变量：

；

；

注意这里 ；另外，这里的连个随机变量是独立的，并且 ，我们可以计算 

换言之，抽到一枚金币和一枚银币的概率约为 0.4898。

上面的计算很容易，因为  和  是独立的。如果在选择第二个硬币之前没有放回第一个硬币，我们的计算将如何改变？第二次选择获得银币的概率取决于第一枚硬币是金还是银。因此  的计算变为

因此，如果不放回的选取硬币获得一枚金币和一枚银币的几率会更大。

我们注意到，最后的计算是超几何分布的一种特殊情况；因此  的计算可以使用 式 5.24 ，，得到 

通常使用贝叶斯公式方便条件概率的计算。

定理 5.33 （贝叶斯公式）设随机变量 ，假设 ，那么

如果  相互独立，那么 ，两者是充要条件。

例 5.34

在这个示例中，我们使用贝叶斯公式来探索三元组  随机变量对的独立性。设  和  为可取值 +1 和 -1 的独立随机变量，每个概率为 ，设 。然后  也取值 +1 和 −1，我们有

(5.26)fZ(1)=∑x∈{−1,+1}∑y∈{−1,+1}Pr(Z=1|X=x and Y=y)⋅fX,Y(x,y)

如果 ，那么 ，所以只可以 ，在这两个条件下， ，因此

并且有 

然后我们计算  的联合密度函数

同样的，能够计算得出 

因此，根据定理 5.33， 和  是相互独立的。显然我们也能够得出 和  也是独立的。因此，在三个随机变量 和 中，任意一对都是独立的。然而，我们并不想把他们三个称为独立族，因为  的值由  和  的值决定。于是我们有定义

定义 如果事件  与每个  的值的选取独立，则由两个或多个随机变量  组成的族是独立的。

注意到上面的例子， 就不是一个独立族，因为

但是