算法导论学习笔记第五章概率分析和随机算法

小灰灰 2022-11-14 10:10 248阅读 0赞

雇佣问题：假如你要雇佣一名新的办公助理，你决定找一个雇用代理，雇用代理每天推荐一名应聘者，而你要付钱给雇用代理以便面试应聘者，如果面试通过，你要付一大笔中介费给雇用代理，并且要辞掉目前的办公助理，估算该策略的费用。

以上雇佣过程的伪代码，假设应聘办公助理的候选人编号为1到n：

HIRE-ASSISTANT(n)
    	best = 0    // candidate 0 is a least-qualified dummy candidate
    	for i = 1 to n
    		interview candidate i
    		if candidate i is better than candidate best
    			best = i
    			hire candidate i

此问题关注的不是以上代码的执行时间，而是面试和雇佣所产生的费用，两者采用的分析技术是相同的，都是计算特定基本操作的执行次数。

面试的费用较低，设为ci，而雇佣的费用较高，设为ch，假设m是雇佣的人数，则该算法总费用为O（ci\*n+ck\*m）。

在最坏情况下，我们会雇佣每个面试的应聘者，即应聘者质量按出现次序严格递增。

平均情况是应聘者以随机顺序出现，假设所有应聘者存在一个全序关系，因此可以使用从1到n的唯一号码对应聘者排列名次，用rank（i）表示应聘者i的名次，应聘者随机出现等价于排名列表是rank（i）的n！种排列中的任一个，每种排列以等概率排列。

雇佣问题中，应聘者好像以随即顺序出现，但我们不知道是否的确如此，因此我们必须对应聘者的次序有更大控制，我们稍稍改变这个模型，假设雇佣代理有n个应聘者，而且他们事先给我们一份应聘者名单，每天随机选择一个应聘者来面试，这样不像以前依赖于猜测应聘者以随机次序出现，而是获得了对流程的控制并加强了随机次序。

更一般地，如果一个算法的行为不仅由输入决定（上例中的n个应聘者名单），而且也由随机数生成器产生的数值决定（每天随机选一个应聘者来面试），则称这个算法是随机的。

我们将一个随机算法的运行时间称为期望运行时间，以此区分随机算法和那些输入是随机的算法，一般而言，当概率分布是在算法的输入上时，我们讨论的是平均情况运行时间，当算法本身做出随机选择时，我们讨论其期望运行时间。

为分析雇佣算法这类随机算法，我们采用指示器随机变量，给定一个样本空间S和一个事件A，那么事件A对应的指示器随机变量I\{A\}定义为：  
![在这里插入图片描述][20210328201236306.png]  
如确定抛掷一枚硬币时正面朝上的期望次数时，样本空间S=\{H，T\}，其中Pr\{H\}=Pr\{T\}=1/2，之后定义一个指示器随机变量XH，对应于硬币正面朝上的事件H，这个变量计数抛硬币时正面朝上的次数，如果正面朝上则值为1，否则为0：  
![在这里插入图片描述][20210411131046117.png]  
在一次抛掷硬币时，正面朝上的期望次数就是指示器变量XH的期望值：  
![在这里插入图片描述][20210411131140832.png]  
![在这里插入图片描述][20210411131709335.png]  
设Xi=I\{第i次抛掷硬币时出现事件H\}，随机变量X表示n次抛硬币中出现正面的总次数，于是：  
![在这里插入图片描述][20210411170652413.png]  
我们希望计算正面朝上次数的期望，对上面等式两边取期望，得到：  
![在这里插入图片描述][20210411170728780.png]  
以上等式给出了n个指示器随机变量总和的期望值，它等于n个随机变量期望值的总和：  
![在这里插入图片描述][20210411170849483.png]  
回到雇佣问题上，我们希望计算雇佣一个新的办公助理的期望次数，假设应聘者以随机顺序出现，假设Xi对应于第i个应聘者被雇佣事件的指示器随机变量：  
![在这里插入图片描述][20210411174737879.png]  
因此：  
![在这里插入图片描述][20210411174845460.png]  
应聘者i被雇佣，意味着应聘者i比从1到i-1的每个应聘者优秀，我们已经假设应聘者以随机顺序出现，所以前i个应聘者也以随即次序出现，前i个应聘者都是等可能地是目前最有资格的，应聘者i比应聘者1到i-1更有资格的概率是1/i，因此：  
![在这里插入图片描述][20210411175314706.png]  
现在就可以计算E（X）了：  
![在这里插入图片描述][20210411175340613.png]  
![在这里插入图片描述][20210411175533542.png]  
雇佣的人数的期望值大约是lgn，比最坏情况下的雇佣费用O（ckn）有了很大改进。

n位顾客，每个人给餐厅核对帽子的服务生一顶帽子，服务生以随机顺序将帽子归还给顾客，拿到自己帽子的顾客的期望数为多少？

![设Xi为第i个顾客拿到自己帽子的随机变量指示器，由于是随机发的帽子，因此E（Xi）=1/n。][Xi_i_E_Xi_1_n]  
用指示器随机变量计算由n个不同数随机排列构成的数列中逆序对的数目。任意一对数是逆序对的概率是1/2，而数列中有n（n+1）/2对数，因此逆序对的数目期望为n（n+1）/4。

进一步探索概率分析和随机算法之间的区别：雇佣问题中，聘用一个新办公助理的期望次数大约是lnn，但这个算法是确定性的，对于任何特定输入，雇佣一个新办公助理的次数始终相同，而算法的费用依赖于各个应聘者的排名的顺序，因此每个输入的花费可能是昂贵的（雇佣n次），也可能是便宜的（雇佣1次）。可以考虑先对应聘者随机排列，此时，我们让随机发生在算法上，而不是输入分布上，此时对于同一个输入，每次运行算法时的花费依赖于随机选择，而且很可能和前一次算法的执行不同，这样没有特别的输入会引出它的最坏情况行为，只有在随机数生成器产生一个不走运的排列时，随机算法才会运行得很差。

对于雇佣问题，代码只需要作出一行改动，以随机排列应聘者序列：

RANDOMIZED-HIRE-ASSISTANT(n)
    randomly permute the list of candidate
    best = 0
    for i = 1 to n
    	interview candidate i
    	if candidate i is better than candidate best
    		best = i
    		hire candidate i

通过以上简单改变，就建立了一个随机算法。

![在这里插入图片描述][20210411205836916.png]  
引理5.2中，我们在输入上作了一个假设，在引理5.3中，我们没有作这种假设，尽管随机化输入会花费一些额外时间。为保持术语的一致性，我们用平均情形下的雇佣费用来表达引理5.2，用期望雇佣费用来表达引理5.3。

构造一个数组的随机排列的一个通常方法是为数组的每个元素赋一个随机的优先级，然后根据优先级对数组A中的元素进行排序：

PERMUTE-BY-SORTING(A)
    n = A.length
    let P[1 ... n] be a new array
    for i = 1 to n
    	P[i] = RANDOM(1, n³)    // 选取在1~n³之间的数，让所有优先级尽可能唯一，此处假设所有优先级都唯一
    sort A, using P as sort keys

以上过程产生均匀随机的排列，每种排列出现的概率为1/n!。证明一个排列是均匀随机排列，只证明对于每个元素A\[i\]排在位置j的概率是1/n这个弱条件是不充分的。

产生随机排列的另一个更好方法是原址排列给定数组：

RANDOMIZE-IN-PLACE
    n = A.length
    for i = 1 to n
    	swap A[i] with A[RANDOM(i, n)]

以上过程产生一个均匀随机排列。一个具有n个元素的k排列是包含这n个元素中的k个元素的序列，并且不重复，一共有n!/(n-k)!种可能的k排列。

如果以上过程不是将元素A\[i\]与子数组A\[i … n\]中的一个随机元素交换，而是将它与数组任何位置上的随机元素交换，则不会产生一个均匀随机排列。

一个屋子里人数要达到多少人，才能使其中两个人生日相同的机会达到50%，可以使用指示器随机变量分析：  
![在这里插入图片描述][2021041217224119.png]  
设一年有n天，两人生日相同的概率为1/n。设X表示计数生日相同两人对数目的随机变量，有：  
![在这里插入图片描述][20210412172404270.png]  
两边取期望，并应用期望的线性性质：  
![在这里插入图片描述][20210412172428514.png]  
因此，对于n为365，人数k为28时E\[X\]大于1。仅用概率分析时，计算出的结果是23人，虽然两种结果不同，但它们在渐进阶数上是相等的，都是θ（根号n）。

把球随机投到b个箱子里，球落在任一个箱子中的概率为1/b。在平均意义下，要投b个球才能在给定箱子里投中一个球。我们需要投几次球，才能保证每个箱子中至少有一个球，这个问题可将n次投球分为几个阶段，第i阶段表示从第i-1次命中到第i次命中，第1阶段包含第1次投球，可以保证一次命中；对第i阶段的每一次投球，有i-1个箱子有球，b-i+1个箱子为空，因此命中的概率为(b-i+1)/b。用ni表示第i阶段的投球次数，此次投中的期望为命中概率的倒数：  
![在这里插入图片描述][20210412173547429.png]  
根据期望的线性性质：  
![在这里插入图片描述][20210412173616299.png]  
期望每个箱子中都有一个球需要大约投blnb次。这个问题也称为礼券收集者问题，一个人如果想要收集齐b钟不同礼券的每一种（每种礼券收到的概率相同），大约需要blnb张随机得到的礼券。

假设抛投一枚标准的硬币n次，最长连续正面的序列的期望长度是θ（lgn）。

雇佣问题中，如果我们不希望面试所有应聘者，也不愿意不停地雇佣新人解雇旧人，我们愿意雇用接近最好的应聘者，只雇佣一次。每次面试后，立即提供职位给应聘者，或马上拒绝应聘者，可通过如下方式对该问题建模以在最小化面试次数和最大化雇佣应聘者的质量两方面取得平衡：在面试一个应聘者后，给每人一个分数，假设每个人的分数都不同，在面试完j个人后，我们知道这j个人中哪一个分数最高，但不知道在剩余n-j个应聘者中会不会有更高分数的应聘者，我们采用这样的策略，即选择一个正整数k<n，面试然后拒绝前k个应聘者，再雇佣其后比前面的应聘者有更高分数的第一个应聘者，如果最好的应聘者在前k个面试之中，那么将雇佣第n个应聘者：

ON-LINE-MAXIMUM(k, n)
    bestscore = -∞
    for i = 1 to k
    	if score(i) > bestscore
    		beststore = score(i)
    for i = k + 1 to n
    	if score(i) > bestscore
    		return i
    return n

当k选择n/e时，选到最好应聘者的概率最大，将以至少1/e的概率成功雇佣到最好的应聘者。

[20210328201236306.png]: /images/20221022/2a1007f67368497191f46c0cefd0544c.png
[20210411131046117.png]: /images/20221022/64939dbfbcd9435c9e446af952b58b1a.png
[20210411131140832.png]: /images/20221022/0a18eb80b7a5497aa4bdbfe508e5f319.png
[20210411131709335.png]: /images/20221022/0faab72e0bfa440f83a4000d68c2eb7e.png
[20210411170652413.png]: /images/20221022/0e4a176904ed4ec4b726a9ad39f22611.png
[20210411170728780.png]: /images/20221022/976dcd7de9fb44f5a74b295f039684df.png
[20210411170849483.png]: /images/20221022/fd53504651b54488884594933010a7b4.png
[20210411174737879.png]: /images/20221022/8c86d540d11845258001b57603ee9ad0.png
[20210411174845460.png]: /images/20221022/f046be4389a5418fa72d388c8dc378cf.png
[20210411175314706.png]: /images/20221022/05d19458dff648ecbc5a7176fe0f7458.png
[20210411175340613.png]: /images/20221022/db71e5f515e04b9a8dfffce18c6c5c28.png
[20210411175533542.png]: /images/20221022/9827b2d95d7f4181bf804b4df11bf3d5.png
[Xi_i_E_Xi_1_n]: /images/20221022/d0ced9928f8a492cb233db678bd5a08e.png
[20210411205836916.png]: /images/20221022/0fa66cebe0c4456abfbbdd4bc3537f3b.png
[2021041217224119.png]: https://img-blog.csdnimg.cn/2021041217224119.png
[20210412172404270.png]: https://img-blog.csdnimg.cn/20210412172404270.png
[20210412172428514.png]: https://img-blog.csdnimg.cn/20210412172428514.png
[20210412173547429.png]: https://img-blog.csdnimg.cn/20210412173547429.png
[20210412173616299.png]: https://img-blog.csdnimg.cn/20210412173616299.png