# 不會看不懂的秘書問題

總覺得「秘書問題」或「37% 法則」的數學推導太難懂，看一看就放棄。
這篇 ... 寫給自己的，應該不會看不懂了吧！

# Problem Statement
老闆要找一個秘書，決定面試 N 個人，每個秘書單獨進行面試，面試結束時，老闆當下立刻決定是否錄取對方。

若錄取，秘書一定會答應；若不錄取，那未來也沒有機會再回頭重新錄取對方。

對老闆來說，在這樣的條件下，他應該採取怎麼樣的策略，來提高自己錄取的秘書是所有面試者中最好的一位的可能性呢？

# Initial Strategy Idea
## Concerns
老闆的困擾與想法：
1. 直接錄取第一個人的話，根本沒有**標準**來評斷好壞 :thinking_face:
2. 面試太少人的話，擔心還會有更好的人選在後頭 :disappointed:
3. 面試太多人的話，會在猶豫不決的過程中錯過最好的人選，只能選剩下的 :sob:

假設老闆在面試的時候並沒有設定硬性的門檻（例如：TOEIC 500 分以上），而是單純以這次有來面試的所有人作為標準，只能用比較的方式來判斷。

## Idea
老闆決定採取的策略是：
1. 先觀察一部分的面試者 :face_with_monocle:
2. 建立標準 :dizzy:
3. 再選出比標準更好的面試者 :heart_eyes:

此時的問題就是，那要怎麼建立標準呢？

因為只能透過面試者互相比較的方式，所以老闆決定以「觀察階段」中最好的面試者作為**標準**，「觀察階段」結束後，第一個比該標準還要高的人，立刻錄取！

## Example Case

舉例來說，老闆決定一共面試 5 個人，這些人現在都坐在走廊上等待面試。

| 編號 | 1 | 2 | 3 | 4 | 5 |
| -------- | -------- | -------- |-------- | -------- |-------- |
| 面試順序 | 1 | 2 | 3 | 4 | 5 |
| 能力分數 | 3 | 1 | 2 | 5 | 4 |

面試按照 1 到 5 號的順序進行，面試者若沒有當下立刻被錄取，就直接離開、再也不回頭。

上帝視角的我們知道每個人的實際工作能力，但是老闆不知道。面試者一號能力有 3 分、面試者二號能力有 1 分 ... 以此類推，分數愈高表示愈棒，老闆愈喜歡！

假設老闆自己偷偷設定觀察階段觀察兩個人就好，也就是一號跟二號都預設不選，只作為判斷標準的依據。面試流程如下：

:face_with_monocle: **觀察階段**
- 面試 #1：預設不選，能力分數 3 分
- 面試 #2：預設不選，能力分數 1 分

:dizzy: **建立標準**
- 觀察階段中最好的面試者 #1 得到了 3 分，因此在這之後，只要面試到能力分數大於 3 分的，立刻錄取！

:heart_eyes: **選擇階段**
- 面試 #3：能力分數 2 分，沒有比**標準** 3 分還要高，因此不錄取
- 面試 #4：能力分數 5 分，比**標準** 3 分還要高，錄取！
- 不面試 #5：直接請他回家，所以老闆也不知道他能力幾分，但因為已經錄取其他人了，所以沒有再繼續面試的必要了。

# Mathematical Derivation

## Problem Reframing

從上面的案例來看，身為上帝視角，老闆的確選到了所有來面試的秘書中的最佳人選！

但這可能只是運氣好而已 ... 隨著面試順序的不同、設定不同的觀察人數，可能會造成截然不同的結果。

為了要最大化老闆成功錄取到最好的面試者的機率，接下來就要認真來討論：**「怎麼決定觀察階段要觀察幾個人才停止？」**

延續上面的案例，先來定義幾個變數：
1. $N$ = 秘書總人數，案例中為 5 人
2. $S$ = 觀察階段，前面 $S$ 人都不錄取，同時代表會被放棄選擇的人數，案例中為 2 人
3. $k$ = 最佳人選，案例中為第四個進行面試的 #4

以上這些變數以「位置」、「順序」來理解會比較容易。
此時問題可以更具體的被定義出來：

> 當已知有 $N$ 個人要來面試時，老闆在面試到第 $S$ 人之前都不錄取，之後遇到第一個比 $S$ 好的人 $k$ 就立刻錄取。若要最大化成功的機率，應該要將 $S$ 設定為多少呢？

## Core Probability Formula
要成功選到最佳人選 $k$ 的條件有：
1. $k$ 是全體最佳人選
2. $k$ 出現在觀察階段 $S$ 人之後
3. $k$ 剛好是觀察階段 $S$ 人之後第一個高過標準的人（標準為前面 $S$ 人中能力分數最高者）

\
把條件的機率與限制寫出來後：
1. 第 $k$ 人是全體最佳人選的機率 = $\frac{1}{N}$
2. 第 $k$ 人出現在觀察階段 $S$ 人之後：第 $S+1$ 到 $N$ 人
3. 第 $k$ 人剛好是觀察階段 $S$ 人之後第一個高過標準的人的機率（代表前 $k−1$ 個人裡最大值在觀察階段 $S$ 人裡的機率） = $\frac{S}{k-1}$

\
條件 1 和 3 是直接決定每個位置的機率值，條件 2 的作用是限制範圍，代表「只在某個區間裡去算每個人的機率」。

目標是找出讓成功機率最高的 $S$，因為每個位子上的人是最佳人選的機率是獨立的，所以要將「限制範圍」內符合條件的都加總起來，也就是將第 S+1 人到第 N 人是最佳人選的機率加總，即可得出設定不同的 S 時成功的總機率。

\
\begin{aligned}
P(\text{選到最佳})
&= \sum_{k=S+1}^{N} P(\text{第 k 人是最佳人選}) \cdot P(\text{觀察區最大值在 k-1 前}) \\
&= \sum_{k=S+1}^{N} \frac{1}{N} \frac{S}{k-1}
\end{aligned}

## Trial Calculation
用案例來試算一次吧！

$N=5$
$S=2$

所以在這個條件下，選到最佳人選的機率是：
\
\begin{align}
P(\text{選到最佳}) &= \sum_{k=S+1}^{N} \frac{1}{N} \frac{S}{k-1} \\
&= \sum_{k=2+1}^{5} \frac{1}{5} \frac{2}{k-1} \\
&= \frac{1}{5} (\frac{2}{2}+\frac{2}{3}+\frac{2}{4}) \\
&= \frac{1}{5} (1+0.6667+0.5) = 43.33 \%
\end{align}

\
也就是說，若一共有 5 個秘書來面試，老闆觀察前 2 人之後，下一個面試到比前兩人還要更好的就錄取，此時老闆錄取到了實際上 5 個人中最佳人選的機率是 43.33%。

$S$ 帶入 1, 2, 3, 4 即計算出不同的成功機率，就可以比較出當 $S$ 為多少時成功機率最高，並以那個數字（位置）做為最終觀察階段的人數即可。

## General Formula for S

案例的數字很小（5,2），可以一個一個慢慢算，但如果要得出一個可以通用的 $S$ 要怎麼辦？

舉例來說，若 $N$ 無限大、或是可細分時，或是當 $N$ 不是人數，而是時間區間，又要如何設定 $S$ 呢？

這時候就需要從離散機率推到連續極限，用微積分找出最大值。

## Integral Solution
重新調整問題框架後，我們希望算出一個最好的觀察階段比例，讓我們從全部人當中，找到最佳人選的機率最大。

當 $N$ 很大的時候（$N \rightarrow \infty$），成功機率的和式極限可以用積分表示：

\begin{align}
& \lim_{N\to\infty}\sum_{k=S+1}^{N} (\frac{1}{N} \frac{S}{k-1}) \approx \int_{\frac{S}{N}}^{1} \frac{S}{N} \frac{1}{t} dt
\end{align}

為了簡化積分表達，引入比例變數 $X$ 和 $t$，其中 $t$ 代表第 $k$ 個人之前（也就是 $k-1$）面試位置佔總人數的比例：

\begin{align}
& X = \frac{S}{N}, &t = \frac{k-1}{N}
\end{align}

此時成功機率可以寫成：

\begin{align}
P(\text{選到最佳})
&= \int_{X}^{1} \frac{X}{t}dt \\\\
&= X\int_{X}^{1}\frac{1}{t}dt \\\\
&= X\left[\ln t \right]_X^1 \\\\
&= X(\ln 1-\ln X) \\\\
&= -X \ln X \\\\
\end{align}

\
用微分找出 $X$ 的最佳值，對 $X$ 微分：
\begin{align}
\frac{d}{dX} P(\text{選到最佳}) &= \frac{d}{dX} (-X \ln X) \\
&= -\ln X-1
\end{align}

為了求極值（此時要找最大值）令微分結果為 $0$ 來解出 $X$：
\begin{align}
&\Rightarrow -\ln X-1 =0 \\
&\Rightarrow \ln X = -1 \\
&\Rightarrow X = e^{-1}
\end{align}

已知 $e \approx 2.71828 ...$

\begin{align}
e^{-1} \approx \frac{1}{2.71828} \approx 0.3679
\end{align}

這個結論的就是俗稱的 37% 法則。當觀察階段在 37% 的時候停止，且選擇在那之後遇到的第一個比前面都更好的，就有最高的機率可以選到最佳人選！

# Conclusion

原始的秘書問題的限制，包含：秘書一定會答應、錯過就不可再回頭、只能選一個秘書等等，因此秘書理論會基於現實世界各種使用情境與需求而調整跟變形。

當然，如果自己原本就有一套明確的標準，也不用這樣比來比去啦！知足常樂 :hearts:

# References

- [決斷的演算: 預測、分析與好決定的11堂邏輯課](https://www.eslite.com/product/1001289172616453)
- [Secretary Problem](https://hackmd.io/@jsaonlin/rJ0uXUAlgl)