[关闭]
@lizhaohan001 2017-03-14T04:52:23.000000Z 字数 2306 阅读 87

密码学I:离散概率(速成课)

密码学 信息安全与密码学 信息安全


Header-img

目录

导览

课程地址请见Coursera

对于分布概率的更详细解释,请见:WikiBooks (English)

注意:文章中对专业名词进行解释的链接均来自维基百科,中国大陆读者若想访问请自备... ...

欢迎访问作者博客

基本定义

:一个总是有限集的全集。通常是n位二进制字符串的集合,记为

:全集上的概率分布,为一个函数,即。该函数为上的元素分配一个值。

例如:对于,即U表示所有两位的二进制串集合。此时。而因为是二进制字符串,因此中的每一个元素分配一个0到1之间的数,称作该元素在全集概率(或权重)。

我们要求:将中所有元素的概率加起来,我们能得到1。即:

个人理解 - 概率分布:对于全集中的每一个元素,返回该元素的概率组成的集合。


常用概率分布

均匀分布

先导定义:
:全集的大小,即全集中元素的个数。

均匀分布:即为全集中的每一个元素分配相同的权重。
因为我们要求权重之和为1并且所有这些权重都相等,因此对全集中的每一个元素,它的概率为1/|U|
这意味着若从这个分布中随机抽样,将得到所有n位字符串上的均匀样本。即根据这个分布 所有字符串被抽中的可能性是相同的。

在点的点分布

点分布:将所有权重放在单一的点上,并对其他中的元素的可能性赋0值。即:

因此,此时若从这个分布中多次抽样,将总是能够确保抽到代表的数值而绝不会抽到任何其他的数值。

本节最后

由于全集总是有限集,事实上我们可以把分布于中每一个元素的权重写出来 从而将整个分布表示为一个向量。该向量的每个实数都在0到1之间。

事件

基本定义

事件:考虑全集的一个子集 ,因为全集的所有元素概率之和为1,因此它的子集的概率之和必然介于0和1之间。即:

此时,称全集的子集为一个事件,集合的概率称为事件的概率

联合界(union bound)

联合界:假定有2个事件 ,它们都是全集的子集。因为代表两个集合的并 ,所以 发生的概率小于这两个概率之和。即:

原因在于,当我们计算这两个概率之和时, 交集交集中元素的概率被计算了2次,所以这两个概率之和将大于或等于 并集的实际概率。
特别地,若 ,那么 将等于 ,即:

随机变量

随机变量:一个从全集映射到某个集合的函数,记为。此时我们说集合V是随机变量的值域。
更一般地,如果有一个从某个集合中取值的随机变量,那么它实际上生成了集合上的一个概率分布,即:

意思是说:随机变量输出的概率等于我们从全集中随机抽取一个元素,对其施加函数 ,然后输出的可能性是多少。
正式地,我们说输出的概率就等于我们从全集中随机抽取一个元素,正好落在 在函数之下的原像中的概率。

关键:随机变量在特定集合中取值,就生成了上的一个概率分布。

均匀随机变量

均匀随机变量:假定是某个有限集合,对于全集中的所有元素,随机抽取一个元素等于的概率是 ,即:

正式来讲,均匀随机变量是一个恒等函数,也就是说对全集中的所有等于

随机化算法

确定性算法:给定输入数据,总是产生相同输出的算法。即一个输入数据 ,总产生相同输出的函数:

随机化算法:取输入数据作为输入,但它每次执行算法时都重新取一个隐性参数,因为我们每次执行算法所取的都不同,因此即使输入的数据一致,输出也不会相同:

关键:即使随机化算法每次执行时的输入都一样,你还是会得到不同的输出。

本节完

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注