在機率及賽局理論上，秘书问题（Secretary problem），类似的名称有37%法則、麥穗理論、相亲问题、止步问题、见好就收问题、苏丹的嫁妆问题、挑剔的求婚者问题等，屬於。内容是这样的：要聘请一名秘书，有 n 个应聘者。每次面试一人，面试后就要立即决定是否聘他，如果当下决定不聘他，他便不会回来。面试后总能清楚了解应聘者的合适程度，并能和之前的每个人做比较。问什么样的策略，才使最佳人选被选中的概率最大。
求解最优策略
这个问题的最优解是一个停止规则。在这个规则里，面试官会拒绝前 r - 1 个应聘者（令他们中的最佳人选为 应聘者 M），然后选出第一个比 M 好的应聘者。可见最优策略包含于这个系列的策略中。（如果M在所有n个应聘者中也是最好的一个，那么这个策略将选不出任何人选）对于任意的截断值 r，最佳人选被选中的概率是：
:
\begin{align}
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{align}
求和符号内概率的计算是基于：如果应聘者 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 值：
此問題的变种
- 選擇者可選多於一人
- 求職者的數目未知
- 求職者之間的關係可影響選擇
- 被拒絕的求職者有一定機率能被叫回來
- 選擇者滿足於次好的人
參考
譯自本頁英文版
- T. S. Ferguson. "Who solved the secretary problem?" Statistical science, volume 4, pp.282-296. 1988.
*數學傳播第二卷第三期 : 海外學人相親記 [http://episte.math.ntu.edu.tw/articles/mm/mm_02_3_12/index.html]
本版未標示充足內容請見英文版
评论 (0)