密码学 | 5.3.4 随机变量

密码学 1年前 (2022) admin
390 0 0

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)(Nmni)(Nn)

5.31 几何分布 (Geometric Distribution)

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

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

(# 表示的数量)

随机变量  定义为

因此

于是我们得到公

(5.25)fX(n)=Pr(X=n)=(1p)n1p,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, 和  是相互独立的。显然我们也能够得出 和  也是独立的。因此,在三个随机变量 和 中,任意一对都是独立的。然而,我们并不想把他们三个称为独立族,因为  的值由  和  的值决定。于是我们有定义

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

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

但是

       

原文始发于微信公众号(山石网科安全技术研究院):密码学 | 5.3.4 随机变量

版权声明:admin 发表于 2022年12月27日 上午10:32。
转载请注明:密码学 | 5.3.4 随机变量 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...