秘书问题

这个问题的最优解是一个停止规则。在这个规则里，面试官会拒绝头 r - 1 个应聘者（令他们中的最佳人选为 应聘者 M），然后选出第一个比 M 好的应聘者。可见最优策略包含于这个系列的策略中。（如果M在所有n个应聘者中也是最好的一个，那么这个策略将选不出任何人选）对于任意的截断值 r，最佳人选被选中的概率是：

${\displaystyle {\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，总和可以近似为如下积分：

${\displaystyle 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.
• 数学传播第二卷第三期 : 海外学人相亲记 [1] （页面存档备份，存于互联网档案馆）

本版未标示充足内容请见英文版