[Algo] 5.4 Probabilistic analysis and further uses of indicator random variables (4)

5.4.4 The on-line hiring problem
不同於先前的 HIRE-ASSISTANT()，這次的方法如下：在 interview 過每個 candidate i後，我們給予他們每人一個分數 score(i) ，在我們 interview k 個 candidates 之後，我們會知道在這 k 個人裡面最高分是多少(假設每個人的分數都不一樣)，但是我們不知道剩下來的 $n - k$ 個人裡面會不會有更高分的人出現。接下來我們決定 reject 前面這 k 個人，然後 hire 接下來這 $n - k$ 個人裡面第一個出現分數比前面所有人都高的那一個人。如果分數最高的那個人出現在前面 k 位裡面，那我們就 hire 第 n 位候選人。這個方法由以下的 pseudocode 來描述：

@{
\proc{On-Line-Maximum}(k, n)
\li bestscore = -\infty
\li \For i = 1 \;\textbf{to}\;k
\li \;\;\;\;\If score(i) > bestscore
\li \;\;\;\;\;\;\;\;bestscore = score(i)
\li \For i = k + 1\;\textbf{to}\;n
\li \;\;\;\;\If score(i) > bestscore
\li \;\;\;\;\;\;\;\;\Return i
\li \Return n
}@

我們要決定的就是如何找出一個最好的 k 才能讓我們最有機會挑出最好的 candidate。


令 $M(j) = \max_{1 \leq i \leq j}\{score(i)\}$ 為 1 到 j 裡面的最高分數，$S$ 為我們成功挑出最好的候選人的 event，$S_i$ 為最好的 candidate 出現在第 i 個的 event。因為每一個 $S_i$ 都是彼此獨立的，所以我們可以得到：
$\mbox{Pr}\{S\} = \sum_{i = k + 1}^n \mbox{Pr}\{S_i\}$
接下來我們來分析怎麼算$\mbox{Pr}\{S_i\}$：
首先最好的 candidate 一定要出現第 i 位，接下來前 i-1 位中最好的 candidate 一定要出現在前 k 名裡面，當然這兩件事情是獨立的，所以我們可以知道：
$\mbox{Pr}\{S_i\} = \frac{1}{n} \cdot \frac{k}{i-1} = \frac{k}{n(i-1)}$

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

因為$\frac{1}{i}$是個 monotonically decreasing function，所以我們可以得到它的 bound：
$\int_{m}^{n + 1}f(x)dx \leq \sum_{k = m}^{n} f(k) \leq \int_{m-1}^n f(x)dx$
$\Rightarrow \int_k^n \frac{1}{x}dx \leq \sum_{i=k}^{n-1}\frac{1}{i} \leq \int_{k-1}^{n-1}\frac{1}{x}dx$
$\Rightarrow \frac{k}{n}(\ln n - \ln k) \leq \mbox{Pr}\{S\} \leq \frac{k}{n}(\ln(n-1) - \ln(k-1))$

因為我們要最大化$\mbox{Pr}\{S\}$，所以要找到一個 k 使得它的 lower bound 越大越好，所以我們可以對 $k/n(\ln n - \ln k)$ 微分，可以得到$1/n (\ln n - \ln k - 1)$，解這個方程式我們可以算出最好的 $\ln k$ 等於 $\ln n - 1 = \ln (n/e)$，也就是說 $k = n/e$，這時我們成功僱用到最好的 candidate 的機率至少大於 $1/e$