概率分析和随机算法

概率论基础知识

基础知识

伯努利试验：在相同条件下，重复地进行n次相互独立的实验 。
有两种可能的结果，成功概率：p、失败概率：q=1-p。
例如：进行n次抛硬币的实验。
几何分布：在n次伯努利试验中，试验k次才得到第一次成功的机率。（是离散型概率分布）
例如：进行n次抛硬币,试验k次才得到第一次正面的概率。
几何分布的概率与期望分别是：

二项分布：重复n次独立的伯努利试验。在每次试验中只有两种可能的结果，而且两种结果发生与否互相对立，并且相互独立，与其它各次试验结果无关，事件发生与否的概率在每一次独立试验中都保持不变，则这一系列试验总称为n重伯努利实验。
例如：进行完n次抛硬币之后,正面出现的次数
二项分布的概率与期望：

0-1分布：就是试验次数为1的二项分布
0-1分布的期望：

当然还有一个很重要的调和级数：

雇佣问题

假设你要雇佣一个新的办公室助理，雇佣代理每天想你推荐一个应聘者（连续推荐n个），你面试这个人，如果这个应聘者比目前的办公室助理更优秀，你就会辞掉当前的办公室助理，然后聘用这个新的。面试一个人需付给雇佣代理一笔费用，聘用办公助理也需要费用。

假设面试费用为Ci，雇佣的费用为Ch，假设整个过程中雇佣了m次，于是总的费用是 nCi+mCh。由于n是固定值，总费用的变化取决于m值。因此，求解雇佣 问题就是对算法中best的更新频率m（次数）建立模型。

情形分析

最坏情形分析

当应聘者质量按出现的次序严格递增时，就会出现最坏情 况： 最坏情形下实际雇用了所有参加面试的应聘者。  此时面试了n次，雇用了n次，所以雇用总费用是O(chn)。

一般情况分析

事实上，我们既不能得知应聘者出现的顺序，也不能控制这个顺序，因此我们使用概率分析。概率分析就是在问题的分析中使用概率技术。为了使用概率分析，必须使用关于输入分布的知识或者对其做假设，然后分析算法，计算出一个期望的运行时间。这个期望值通过对所有可能的输入分布算出。

在雇佣问题中，可以假设应聘者是以随机顺序出现的。假设可以对任何两个应聘者进行比较并确定哪个更优；换言之，在所有的应聘者之间存在这一个全序关系。因此可以使用从1到n的唯一号码来标志应聘者的优秀程度。用rank(i)来表示应聘者i的名次。这个有序序列<rank(1),rank(2)，…, rank(n)>是序列<1,2,…,n>的一个排列。说应聘者以随机的顺序出现，就等于说这个排名列表是1到n的n！中排列中的任何一个，每种都以相等的概率出现。

随机算法

在许多情况下，我们对输入分布知识知之甚少；即使知道关于输入分布的某些信息，也无法对这种分布建立模型。然而通过使一个算法中的某些部分的行为随机化，就常常可以利用概率和随机性作为算法设计和分析的工具。

比如在雇佣问题中，如果雇佣代理给我们一份应聘者的名单，每天我们随机地挑选一个应聘者进行面试，从而确保了应聘序列的随机性。

更一般地，如果一个算法的行为不只有输入决定，同时也由随机数生成器所产生的数值决定，则称这个算法是随机的。

示例：

描述Random(a,b)过程的一种实现，它只调用现有实现Random（0，1）。作为a和b的函数，你的程序的期望运行时间是多少？假设Ramdom（0，1）的运行时间是常数。

将一个随机算法的评平均运行时间称为期望运行时间

指示器随机变量

事件A的期望值就是事件A在样本空间中发生的概率。

练习5.2.2：
在雇佣问题中，假设应聘者以随机的顺序出现，正好雇佣两次的概率是多少？

分析：第一个应聘者肯定被雇佣，最优秀的应聘者也肯定被雇佣。如果第一个就是最优秀的那么指挥雇佣一次，这种情况就可以排除。那么恰好雇佣两次就意味这在第一个应聘者和最优秀的应聘者之间的应聘者都不如第一个优秀。由于应聘者是随机出现的，那么任何一种序列都是等可能的，只要能求出满足前一要求的排列数目就能求出概率。

假设应聘者对应于集合S={1，2，3，…,n}。应聘者的优秀程度就有数值来标记。假设我们将最大的数n暂时抽出。将剩下的1~n-1个分成两组，在由这两组形成两个序列S1、S2，要求S1的第一个数是S1中最大的数，S2完全随机排列， 那么 序列 S1nS2 就是满足需求的一种n排列。反过来，每种满足需求的排列都可以表示成这种形式。

这种排列的数目有m = ∑k=1~~~~n-1C(n-1,k）(k-1)!*(n-1-k)! –k=1n-1
概率为： m/n! = 1/n∑k=1n-1^1/k^

期望运行时间和平均情况运行时间

期望运行时间：

我们将一个随机算法的平均运行时间称为期望运行时间。
此时，算法的最终输入由随机数发生器产生

一般而言，当概率分布是发生在算法的原始输入上时，我们讨论算法的“平均情况运行时间”，而当算法本身做出随机选择时，我们讨论算法的“期望运行时间”。