本文需要高数知识。


众所周知,许多算法将随机性加入其中,以此作为在递归时开销与执行其它操作开销的折中方案。(如快排中随机选择基准元素)直觉上来说,我们可以感觉到随机化快排的平均时间复杂度几乎总是最优的——O(nlogn)。为了从数学上证明这一点,也为了分析其它具有随机性的算法,我们需要离散概率的数学知识。

取样空间(样本空间)

所谓取样空间,就是可能发生的所有不同事情(基本事件)的集合。例如,对于投骰子这个随机过程,取样空间就是\Omega=\{1,2,3,4,5,6\}

取样空间中的每个元素i都有一个非负的概率p(i),可以认为是随机过程的结果为i的频率。对于投骰子这个过程,p(i)对于每个i=1,2,3,4,5,6都是\frac{1}{6}。显然,取样空间中所有事件的概率和应该为1。

\sum\limits_{i\in\Omega} p(i)=1

\Omega中的每一个元素都具有相同的概率,这称为均匀分布。此时对于每个i\in\Omegap(i)=\frac{1}{|\Omega|}1。在快排的例子中,数组中的每个元素都可能被选为基准元素,因此每个元素被选为基准元素的概率都为\frac{1}{n}n为数组的长度。

事件

事件S是取样空间的一个子集,即S\sube\Omega。==注意与基本事件区分,事件是集合,基本事件是元素。==事件S的概率Pr[S]定义为S中基本事件的概率之和:

Pr[S]=\sum\limits_{i\in S} p(i)

举个例子

虽然很好理解,但还是举个例子。如果S表示同时投出两个标准骰子,点数之和为7这个事件,则S中共有6个基本事件:

S=\{(6,1),(5,2),(4,3),(3,4),(2,5),(1,6)\}

由于\Omega中的每个基本事件具有相同的概率,对于每个i\in\Omegap(i)=\frac{1}{36}。因此:

Pr[S]=|S|\cdot\frac{1}{36}=\frac{6}{36}=\frac{1}{6}

事件S的概率为\frac{1}{6}

快排运用

定义近似中位元素:选择一个基准元素后,若至少有25%的元素小于这个基准,且至少有25%的元素大于这个基准,则称这个元素为近似中位元素。那么S表示随机选择的基准元素为近似中位元素,则事件S的概率是什么?

同上一个例子:

Pr[S]=|S|\cdot\frac{1}{n}=\frac{n}{2}\cdot\frac{1}{n}=\frac{1}{2}

不解释了。

随机变量

因为我搞了很久才弄明白,所以开头先强调一下。

随机变量是函数!!!

(离散)随机变量X是从一个有限或可数无限样本空间S到实数的函数。它将每个试验可能的结果与一个实数关联起来,这使得我们可以分析结果数集上的概率分布。随机变量也可以定义在不可数无限样本空间上,但是这么做会引起一些技术问题,这对我们的目标是不必要的。因此,我们将假定随机变量是离散的。

对于随机变量X和实数x,定义事件X=x为\{s\in S:X(s)=x\};因此

Pr\{X=x\}=\sum\limits_{s\in S,X(s)=x} Pr\{s\}

函数

f(x)=Pr\{X=x\}

是随机变量X的概率密度函数。由概率公理可知,Pr\{X=x\}\ge0\sum\limits_x Pr\{X=x\}=1

——摘自《算法导论(第三版)》

个人认为算法导论的描述是比较晦涩的。通俗描述一下,随机变量是一个在取样空间\Omega上定义的一个实数值函数X:\Omega\rightarrow R。(根据映射的定义,\Omega中的每个元素在R上都有唯一确定的元素与之对应)即它的输入是事件的结果,输出是结果的量化数值。进一步简化,随机变量是个把事件的结果转化为数值的函数。比如定义一个随机变量X为投骰子的点数,投骰子的结果为“投出3点”,将这个结果作为X的输入,它的输出是“3”。

期望值

随机变量X的期望值E[x]是它所有可能发生情况的加权平均值,它是根据不同结果的概率进行加权的。随机变量X的期望值是

E[X]=\sum\limits_{i\in\Omega} p(i)\cdot X(i)

p(i)即为结果的概率,权重,X(i)为事件结果的量化数值。

个人认为上面公式比算法导论中的

E[X]=\sum\limits_x x\cdot Pr\{X=x\}

Pr\{X=x\}指事件发生的结果输入X后输出为x的概率,即某一事件结果经过加权后的值。

来的更为直观,这里同时列出两个式子以强调它们意义的相同。(算法导论中对事件X=x进行了定义)

在这里不想举例了,直接进入下一节重点——线性期望值。

线性期望值(期望的线性性质)

期望的线性性质指的是两个随机变量的和的期望与它们的期望之和相等,即

E[X+Y]=E[X]+E[Y]

其中,E[X]E[Y]需有定义。即使XY不独立,这一性质依然成立。由期望的线性性质我们可以得到如下定理:

假设X_1,...,X_n是在同一个取样空间中定义的随机变量,并且a_1,...a_n是实数,则

E[\sum\limits^n_{j=1}a_j\cdot X_j]=\sum\limits^n_{j=1}a_j\cdot E[X_j]

这个定理表明随机变量的求和以及期望值的计算可以按任何顺序进行。

线性期望值的证明是双求和的反转,这里不赘述了。

对于实际问题,独自定义随机变量与期望值来解决问题是个困难的任务,至少我尚且无法掌握。如有需要,下次会放上运用期望的线性性质来解决问题的例子。

Q.e.d.


  1. 对于有限集S|S|表示S中元素的数量。 ↩︎

夢に僕らで帆を張って 来るべき日のために夜を越え。