在HIRE-ASSISTANT中，假设应聘者以随机顺序出现，

解题思路: 首先我们可以直接观察三个结论： (1) 1号助理总是会被雇用； (2) 最佳助理（即rank为n的助理）总是会被雇用； (3) 最佳助理不可能是1号助理，因为那样将只能刚好雇用一次。 满足以上三点，就可以满足两次雇佣。所以在使HIRE-ASSISTANT刚好雇用两次的序列中，一号助理必然有rank=i 且 i<=n-1，同时，所有rank在[i+1..n-1]区间内的助理必然在rank为n的最佳助理被面试之后面试。 1.设事件Ei表示应聘者i恰好作为1号助理被雇用的情况，则对于任意给定的i，有Pr{Ei}=1/n。 因为在第一次面试中，每个应聘者都等可能被选中，所以特定的i被第一次面试的概率为1/n。 2.设j指向最佳助理在面试序列中的位置，则若要满足两次雇佣，此时必须满足2、3、...、j-1号面试的应聘者的名次都要小于i。 设事件F表示2、3、...、j-1号助理的rank比1号助理低的情况。那么发生两次雇佣只有在Ei和F都满足的情况下发生，即F∩Ei，此时rank=i的助理作为第一个面试者被雇佣，第二次雇佣发生在最佳雇佣rank=n上，且仅有两次雇佣。 而F成立，当且仅当名次为i+1、i+2、...、n-1的应聘者在最佳助理n后面进行面试，否则[i+1 .. n-1]将会出现在[1..j]次面试中，从而发生雇佣。 假设Ei成立，F成立等价于当最佳助理在rank为i+1、i+2、...、n-1的n-i-1个助理在最佳助理n之后被面试。要是rank=n的助理出现在第一位，剩下的排序任意即可，而[i+1 .. n]总共有n-i个助理，每个助理等可能的出现在最前面，所以，Pr{F|Ei}=1/(n-i)。 设事件A表示HIRE-ASSISTANT刚好雇用两次的情况。因为最佳助理n不可能被第一个面试，于是我们有： A=F∩(E1∪E2∪...∪En-1) =(F∩E1)∪(F∩E2)∪...∪(F∩En-1) Pr{A}=∑Pr{F∩Ei} (i<-1to n-1) Pr{F∩Ei}=Pr{F|Ei}Pr{Ei} =1/(n-i)*(1/n) 所以 Pr{A}=∑1/(n-i)*(1/n)(i<-1 to n-1) =1/n*∑1/(n-i) (i<-1 to n-1) =1/n*(1/(n-1)+1/(n-2)+...+1/1) 视频参考：【随机算法】雇佣问题分析-哔哩哔哩】 https://b23.tv/6c4NBaF