概率HIRE- ASISTANT

Question

这是一个HIRE-ASSISTANT问题的算法。

HIRE-ASSISTANT(n) 
best <- 0 
for i <- 1 to n do 
     if candidate[i] is better than candidate[best] 
      best <- i 
      hire candidate i 

现在一些意见：

1.Candidate 1总是录用。

2.最好的候选人，即排名为n的候选人，总是被雇用。

3.如果最佳候选人是候选人1，那么这是唯一候选人。

现在问题是雇佣两次的概率是多少？

我的方法：

现在第n个排名前候选人，我可以采访任何数量的候选人，因为我想但他们的排名顺序是fixed.Therefore对我的候选人第n个排名前候选人被采访= C（ N-1，I）*（N-1）！总的情况是可能的。因此，从n-1改变i = 1并且总和除以总的可能性n！我计算答案，但它与标准答案不匹配，所以我需要帮助找到问题所在？

Answer 1

聘请的概率至少两次是(n-1)/n。
假设你有一个随机排列的候选人，你只雇用一个候选人当且仅当第一个候选人也是最好的。它发生的概率是1/n。因此，概率也不会发生（你会雇佣两次或以上）是1-1/n = (n-1)/n

要聘请正是两次：

• 选择一个位置（不是第一个）的“最佳”：n-1可能性。让这个地方成为我
• 对于每个这样的地方，选择i-1候选人放在最好的之前：Choose(n-1,i-1)
• 这些i-1候选人的第一个是他们中最好的。需要对其余部分进行排列：(i-2)!
• 另外，仍然需要在'最佳'之后对（n-i-1）个候选者进行排列：（n-i-1）！

这给了我们“有效”排列的总数正好两个候选人被录用为：

f(n) = Sum[ Choose(n-1,i-1)*(i-2)!*(n-i-1)! | for i=2,...,n] 

的概率简直是P=f(n)/n!

Answer 2

事实上，在第4子弹我们需要排列（ni）候选，所以最终答案降为P = 1/n * H_（n-1），其中H_（n-1）是第（n-1）次谐波数。