你好,密码学(2):离散概率(速成课)

导览

课程地址请见Coursera

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

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

基本定义

$U$:一个总是有限集的全集。通常是n位二进制字符串的集合,记为${0,1}^n$。

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

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

我们要求:将$U$中所有元素的概率加起来,我们能得到1。即:
$$
\sum_{x\in U} P(x)=1
$$

即对于全集$U$中的每一个元素,$P$返回该元素的概率组成的集合。


常用概率分布

均匀分布

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

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

在点$x_0$的点分布

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

$$
P(x_0)=1,\quad \forall x \neq x_0: \;P(x)=0
$$

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

本节最后

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

事件

基本定义

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

$$
\mathbf {For\;\:a\;\:set\;}A\subseteq U:\quad Pr[A]=\sum x \in [0,1]
$$

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

联合界(union bound)

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

$$
Pr[A_1 \cup A_2] \; \le\; Pr[A_1]+Pr[A_2]
$$

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

$$
\mathbf {if} A_1 \cap A_2= \varnothing, \quad \mathbf{than} \;\;\; Pr[A_1 \cap A_2]=Pr[A_1]+Pr[A_2]
$$

随机变量

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

$$
\mathbf { rand \;\; var.} \;\: x \;\; \mathbf { includes\;\;a\;\;distribution\;\;on} \;\;V \mathbf:\quad Pr[X=v]:=Pr[x^{-1}(v)]
$$

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

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

均匀随机变量

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

$$
r \overset{R} \longleftarrow \mathbf{\;\;means\;\;devote\;\;uniform\;random\;variable\;\;on}\;\;U\
\forall\;a\in U:\quad Pr[i=a]\;=\;\;\frac{1}{|U|}
$$

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

##随机化算法

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

$$
y \longleftarrow A(m)
$$

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

$$
y \longleftarrow A(m\;;\;r)\quad \mathbf{where}\quad r \overset{R} \longleftarrow {0,1}^R\\
\mathbf{output\;\;is\;\;a\;\;random\;\;variable}\\
y \overset{R} \longleftarrow A(m)
$$

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

本节完

=。=
0%