查看“︁秘書問題”︁的源代码

在[[機率]]及[[賽局理論]]上，'''秘书问题'''（Secretary problem），类似的名称有'''37%法則'''<ref>{{cite book
|title=其實攸關貧富與生死的數學並不難！選擇障礙必備的37%法則 (The Maths of Life and Death)
|author=葉茲 (Kit Yates)
|translator=林俊宏
|work=天下文化
|publisher=[[遠見·天下文化事業群]]
|url = https://bookzone.cwgv.com.tw/article/25295
|date=2022-08-15 
|archiveurl = https://web.archive.org/web/20240310145415/https://bookzone.cwgv.com.tw/article/25295
|archivedate=2024-03-10 }}
</ref>、'''麥穗理論'''<ref>{{cite book
|title=麥穗理論─如何選擇人生中最大的那支麥穗？
|author=劉潤
|work=工商時報
|url= https://www.ctee.com.tw/news/20200718700165-431001
|date= 2020-07-18
|archiveurl= https://web.archive.org/web/20240310142029/https://www.ctee.com.tw/news/20200718700165-431001
|archivedate= 2024-03-10 }}</ref>、'''相亲问题'''、'''止步问题'''、'''见好就收问题'''、'''苏丹的嫁妆问题'''、'''挑剔的求婚者问题'''等，屬於{{le|最佳停止問題|Optimal stopping}}<ref>{{cite web
|title=人生大事難以抉擇？用「最佳停止點」來幫助你下決定吧！
|author=林希陶
|work=PanSci 泛科學
|url=https://pansci.asia/archives/156137
|date=2019-03-19
|archiveurl=https://web.archive.org/web/20230327135546/https://pansci.asia/archives/156137
|archivedate=2023-03-27 }}</ref>。内容是这样的：要聘请一名秘书，有 ''n'' 个应聘者。每次面试一人，面试后就要立即决定是否聘他，如果当下决定不聘他，他便不会回来。面试后总能清楚了解应聘者的合适程度，并能和之前的每个人做比较。问什么样的策略，才使最佳人选被选中的概率最大。

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

:<math>
\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}
</math>


求和符号内概率的计算是基于：如果应聘者 ''i'' 是（所有应聘者中的）最佳人选，他被选中当且仅当头 ''i'' - 1 个应聘者中的最佳人选处在头 ''r'' - 1 个被拒绝的应聘者中。令 ''n'' 趋近无穷大，把 ''x'' 表示为 ''r''/''n'' 的极限，令 ''t'' 为 ''i''/''n''，''dt'' 为 ''1''/''n''，总和可以近似为如下积分：

:<math>
P(x)=x \int_{x}^{1}\frac{1}{t}\,dt = -x \ln(x).
</math>

令 P(''x'') 对 ''x'' 的导数为 0，解出 ''x''，我们得到最优的 ''x'' 等于 1/''e''。从而，当 ''n'' 增大时，最优截断值趋近于 ''n''/''e'' 最佳人选被选中的概率为 1/''e''。

对于较小的 ''n'' 值， 最优的 ''r'' 也可以通过[[动态规划]]方法得到。下表给出了一些最优的 ''r'' 值：

{| class="wikitable"
|-
! ''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.
*數學傳播第二卷第三期 : 海外學人相親記 [http://episte.math.ntu.edu.tw/articles/mm/mm_02_3_12/index.html] {{Wayback|url=http://episte.math.ntu.edu.tw/articles/mm/mm_02_3_12/index.html |date=20061011150214 }}
本版未標示充足內容請見英文版

[[Category:决策论]]
[[Category:最佳化決策]]
[[Category:商业数学优化]]