概率分析和随机算法

问题描述

1. 在线雇用问题
2. 生日悖论

在线雇用问题

描述

现在公司需一名办公助理，雇用代理每天都会推荐一名应聘者，假设一共会有n个应聘者；应聘的规则是一旦面试完后需要立刻做出决断是否录取该应聘者；而且只能在这n个应聘者中选取一个，也就是说一旦应聘了该应聘者，如果接下来的应聘者比之优秀，不能解雇先前的而录取该优秀的；请给出合理的策略

解决

下面的这种方法是一个方案，至于为什么要采取这个方案书中并没提到(或许我暂时没能理解)
对于n个应聘者，设定一个k (1<=k<=n-1)，每个应聘者在应聘后会有一个分数记为score(i),选取1~k个应聘者中最优秀的一个，分数为score(m),从k+1开始，如果有score(i)>score(m)，则录取第i名应聘者，否则录取最后一名应聘者。
下面通过分析得出k的值
k值的选取决定了该方法是否能够选取到n个应聘者中最优的概率，因此从最优的角度出发来计算最优的应聘者被应聘的概率；
如果应聘的是最优的应聘者，记为S，则最优的应聘者一定在第k+1~n中，否则不可能被应聘；记Si表示第i个应聘者为n个中最优秀的应聘者且被成功应聘。应聘成功的概率等于对p(Si)求和
Si成功需要满足两点：

1. 第i个应聘者为n个中最优秀的应聘者
2. 第k+1~i-1个应聘者均小于score(m)

两个事件是相互独立的，因此p(Si)=p(Si1)*p(Si2)
p(Si1)即1/n，p(Si2)表示的是只要1~i-1个元素中最大的在1~k中，即k/(i-1)
即

$$p(Si)=k/(n*(i-1))$$ $$\sum_{i=k+1}^n p(Si)=p(S)$$ $$k/n*\sum_{i=k}^{n-1} 1/i=p(S)$$

参见调和基数可以得到如下公式：

$$\int_k^\int_n