概率分析和随机算法

1.雇佣问题

雇佣代理向你推荐合适的候选人，每次推荐需要一笔代理费用。如果新候选人比在岗的候选人好，则决定聘用，这就需要向雇佣代理付一大笔中介费用。在这个过程中，只考虑向雇佣代理支付的费用，且每次遇到更好的候选人都辞去当前的在岗的候选人。

HIRE-ASSISTANT(n)
best = 0	//dummy候选人，默认为最差的
for i = 1 to n
	interview candidate i
	if candidate i is better than candidate best
		best = i
		hire candidate i

面试的费用设为 $c_i$ ，雇佣的费用设为 $c_h$ ，设雇佣的人数为 $m$ ，则总费用为 $O(c_in+c_hm)$ 。其中面试费用一定，而雇佣费用不一定。

最坏情形 应聘者质量按出现次序严格递增，相当于对每个面试的人都雇佣了一次(每次都把上一次的人辞退然后招新人)

概率分析 首先假设关于输入的分布，然后分析该算法，计算出一个平均情形下的运行时间。在此问题中，我们用1到n将这些应聘者标号，而令 $rank(i)$ 表示应聘者 $i$ 的名次，并约定若 $rank(i)>rank(j)$ ，则代表 $i$ 号比 $j$ 号优秀，这n个应聘者的优秀程度序列具有 $n!$ 种，且每种都是等概率的。

随机算法 一个算法的行为不仅由输入决定，也由随机数生成器的数值决定，规定 $RANDOM(a,\ b)$ 代表返回一个 $a$ 和 $b$ 之间的整数(包含边界)，且每个结果概率相等。一般而言，对于算法的输入服从某种概率分布时，我们分析平均情况运行时间；当算法本身做随机选择时，我们分析期望运行时间。

指示器随机变量 形如

I\{A\}=\begin{cases} 1\ 如果A发生\\ 0\ 如果A不发生 \end{cases}

引理给定一个样本空间S和S中的一个事件A，设 $X_A=I\{A\}$ ，那么 $E[X_A]=Pr\{A\}$ ，由期望定义很容易得出。

总和的期望等于n个随机变量期望值的总和，无论随机变量是否存在依赖关系

雇佣问题的分析

设 $X$ 是一个随机变量，其值就等于整个过程雇佣了多少次。那么，平均情况下， $E[X]=\sum_{x=1}^nxPr\{X=x\}$ ，这种计算很麻烦，因此我们采用指示器随机变量。

X_i=I\{应聘者i被雇佣\}=\begin{cases}1\ 如果应聘者i被雇佣\\ 0\ 如果应聘者i不被雇佣 \end{cases}

问题转化为分析应聘者 $i$ 被雇佣的概率，这表明应聘者 $i$ 比之前的 $i-1$ 人都优秀，由于应聘者以随机顺序出现，因此这 $i$ 个人每个人都等可能是目前最有资格的，因此我们得到 $E[X_i]=Pr\{X_i=1\}=\frac{1}{i}$ 。

因此，

\begin{align*} E[X]&=E[\sum_{i=1}^n X_i]\\ &=\sum_{i=1}^nE[X_i]\\ &=\sum_{i=1}^n1/i\\ &=\mathrm{ln}n+O(1) \end{align*}

结论是，我们尽管面试了 $n$ 个人，但平均只雇佣了 $\mathrm{ln}n$ 个人

随机算法 确定性算法对于任何不变输入，雇佣新应聘者的次数不会发生改变，我们对于某些排名序列，例如{5, 2, 1, 8, 4, 7, 10, 9, 3, 6}，依次面试，则在任何情况下我们都会雇佣3次，即在遇到排名为5，8，10的人时(数字越大代表越优秀)。但对于随机算法来说，我们让随机发生在算法上，而不是输入分布上。

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

它们区别就在于多了第一步：随机生成一个序列，或者理解为将给定名单打乱顺序。我们在分析确定性算法时，是假设输入是某种分布，但对于随机算法而言，相当于设定好了某种概率分布，因此不再需要通过假设来分析了。

在线雇佣问题

假设我们现在不追求雇佣严格意义上最好的应聘者，因为我们不希望不停雇佣新人解雇旧人，每次面试，我们要么拒绝，要么马上提供职位，无论后面是否有更好的应聘者。我们如何在最小化面试次数和最大化应聘者质量之间取得平衡？我们采取一个策略，每次面试都给应聘者一个唯一的分数，并做好记录。对于n个应聘者，选择一个正整数 $k<n$ ，面试然后直接拒绝前 $k$ 个应聘者，在雇佣后面遇到的比前 $k$ 个应聘者分数都高的第一个应聘者，如果后面没有遇到超过前 $k$ 个应聘者分数的应聘者，则雇佣最后一个应聘者。

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

那么我们如何确定下来这个 $k$ 的值使得得到的结果是最好的呢？

设 $M(j)=max_{1\le i\le j}\{score(i)\}$ 表示应聘者 $1～j$ 中最高分数。设 $S$ 表示成功选择了最好的应聘者(没有错过)， $S_i$ 表示成功选择了最好的应聘者且他是第 $i$ 个面试者。那么 $Pr\{S\}=\sum_{i=1}^nPr\{S_i\}$ ，根据规则，不选前 $k$ 个人，则对于 $i\le k,\ Pr\{S_i\}=0$ ，因此 $Pr\{S\}=\sum_{i=k+1}^nPr\{S_i\}$ ，那么如何计算 $S_i$ 发生的概率？它要发生则必须满足(1)最好的应聘者本身在位置 $i$ ，设为 $B_i$ ，(2)从 $k+1$ 到 $i-1$ 的人不能比前 $k$ 个人分数高，否则会被提前选走，设为 $O_i$ ，且二者独立，因为 $O_i$ 依赖于前 $i-1$ 个人的分数顺序， $B_i$ 依赖于 $i$ 位置相比于前后所有位置的分数值。改变前 $i-1$ 人的分数顺序并不影响第 $i$ 个位置是否比他们及其后面的分数都大，而改变第 $i$ 个人的分数使其不大于剩下任意的人，也根本不会改变前 $i-1$ 人的顺序。

Pr\{S_i\}=Pr\{B_i\cap O_i\}=Pr\{B_i\}Pr\{O_i\}\\ Pr\{B_i\}=1/n

若使得 $O_i$ 发生，则需要保证前 $i-1$ 个人的最大分数落在前 $k$ 个人里，否则会导致提前选中，因此 $Pr\{O_i\}=k/(i-1)$ 。

综上，

Pr\{S\}=\sum_{i=k+1}^nPr\{S_i\}=\sum_{i=k+1}^n\frac{k}{n(i-1)}=\frac{k}{n}\sum_{i=k}^{n-1}\frac{1}{i}

由于

\int_k^n\frac{1}{x}\mathrm{d}x\le\sum_{i=k}^{n-1}\frac{1}{i}\le\int_{k-1}^{n-1}\frac{1}{x}\mathrm{d}x

因此

\frac{k}{n}(\mathrm{ln}n-\mathrm{ln}k)\le Pr\{S\}\le\frac{k}{n}(\mathrm{ln}(n-1)-\mathrm{ln}(k-1))

我们求使下界最大的 $k$ ，对 $k$ 求导得到 $\frac{\mathrm{ln}n}{n}-\frac{\mathrm{ln}k+1}{n}$ ，因此当 $k=n/e$ 时，取最大值，此时成功雇佣到最好的应聘者的概率至少为 $\frac{1}{e}$ 。