概率上升

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名候选人之前,我可以按照自己的意愿采访任意数量的候选人,但他们的排名顺序是固定的.因此,我排名第n候选人之前接受采访的候选人= C(n-1,i)*(ni-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)!
• 此外,还需要在'最佳'之后为(ni-1)候选人进行置换:(ni-1)!

这给我们的是"有效"的排列的总数正好两个候选人被录用为:

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

概率很简单 P=f(n)/n!