概率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）次諧波數。