秘書問題

在機率及賽局理論上，秘書問題（Secretary problem），類似的名稱有37%法則、麥穗理論、相親問題、止步問題、見好就收問題、蘇丹的嫁妝問題、挑剔的求婚者問題等，屬於最佳停止問題。內容是這樣的：要聘請一名秘書，有 n 個應聘者。每次面試一人，面試後就要即時決定是否聘他，如果當下決定不聘他，他便不會回來。面試後總能清楚了解應聘者的合適程度，並能和之前的每個人做比較。問什麼樣的策略，才使最佳人選被選中的概率最大。

求解最優策略

這個問題的最優解是一個停止規則。在這個規則里，面試官會拒絕頭 r - 1 個應聘者（令他們中的最佳人選為 應聘者 M），然後選出第一個比 M 好的應聘者。可見最優策略包含於這個系列的策略中。（如果M在所有n個應聘者中也是最好的一個，那麼這個策略將選不出任何人選）對於任意的截斷值 r，最佳人選被選中的概率是：

${\begin{aligned}P(r)&=\sum _{i=1}^{n}P\left({\text{applicant }}i{\text{ is selected}}|{\text{applicant }}i{\text{ is the best}}\right)\times P\left({\text{applicant }}i{\text{ is the best}}\right)\\&=\left(\sum _{i=1}^{r-1}0\times {\frac {1}{n}}\right)+\left(\sum _{i=r}^{n}P\left(\left.{\begin{array}{l}{\text{the best of the first }}i-1{\text{ applicants}}\\{\text{is in the first }}r-1{\text{ applicants}}\end{array}}\right|{\text{applicant }}i{\text{ is the best}}\right)\times {\frac {1}{n}}\right)\\&=\sum _{i=r}^{n}{\frac {r-1}{i-1}}\times {\frac {1}{n}}\quad =\quad {\frac {r-1}{n}}\sum _{i=r}^{n}{\frac {1}{i-1}}.\end{aligned}}$

求和符號內概率的計算是基於：如果應聘者 i 是（所有應聘者中的）最佳人選，他被選中若且唯若頭 i - 1 個應聘者中的最佳人選處在頭 r - 1 個被拒絕的應聘者中。令 n 趨近無窮大，把 x 表示為 r/n 的極限，令 t 為 i/n，dt 為 1/n，總和可以近似為如下積分：

$P(x)=x\int _{x}^{1}{\frac {1}{t}}\,dt=-x\ln(x).$

令 P(x) 對 x 的導數為 0，解出 x，我們得到最優的 x 等於 1/e。從而，當 n 增大時，最優截斷值趨近於 n/e 最佳人選被選中的概率為 1/e。

對於較小的 n 值， 最優的 r 也可以通過動態規劃方法得到。下表給出了一些最優的 r 值：

n	1	2	3	4	5	6	7	8	9
r	1	1	2	2	3	3	3	4	4
P	1.000	0.500	0.500	0.458	0.433	0.428	0.414	0.410	0.406

此問題的變種

• 選擇者可選多於一人
• 求職者的數目未知
• 求職者之間的關係可影響選擇
• 被拒絕的求職者有一定機率能被叫回來
• 選擇者滿足於次好的人

參考

譯自本頁英文版

• T. S. Ferguson. "Who solved the secretary problem?" Statistical science, volume 4, pp.282-296. 1988.
• 數學傳播第二卷第三期 : 海外學人相親記 [1] （頁面存檔備份，存於網際網路檔案館）

本版未標示充足內容請見英文版