Optimal Stopping - The Secretary Problem

柏拉圖有一個很有名的故事：他要弟子去麥田裡，不准回頭地摘下一株最大的麥穗。

結果弟子為了等後面「可能」更大的，最後什麼都沒摘到。

這個故事大家可能都聽過，但如果我們把它變成一個嚴格的數學問題呢？

1. 問題設定

假設你現在是老闆，要面試 \(N\) 個秘書，面試完必須立刻決定要不要錄取，不能吃回頭草。

• 你遇到第一個人，他是目前最好的機率是百分之百，也就是 1。
• 遇到第二個人，他比第一個好的機率是 \(1/2\)。
• 第三個人，剛好是目前這三人裡最優秀的機率，是 \(1/3\)。
• 以此類推，第 \(k\) 個人成為「目前為止最好」的機率，剛好就是 \(1/k\)。這每一個都是獨立事件。

問題來了：你要怎麼選，才能讓自己選到那個「絕對第一名」的機率最大？

2. 逆向歸納法 (Backward Induction)

遇到這種不知從何下手的問題，最暴力的解法，就是從結果往回推。

秘書問題的本質，其實是最簡單的一種動態規劃。 如果你有學過任何 Dynamic Programming 的話，現實中的 DP 絕對比這個還要複雜非常多。 這裡 optimal stopping 是一個特別簡單的情形，數學上叫做 Backward Induction，逆向歸納法。

如果你沒學過也完全沒關係，因為我們現在馬上來看一下，它到底在幹嘛。

想像一下，你站在面試的最後一關。如果前面都沒選，最後一個就算再爛，你也只能硬著頭皮選下去。因為你已經知道最後一步的下場，所以我們可以開始「往回倒推」。

3. 確立解的形狀：黃金交叉

在往回推的過程中，我們每一步其實都只在做一件事：拿「天平」秤兩邊的重量。 左邊是「我現在就停下來」的期望值；右邊是「我繼續面試下去」的期望值。哪邊重，我們就選哪邊。 - 如果你太早停下來，樣本數根本不夠，所以「停下來」的期望值一開始是很差的。 - 但反過來說，如果你一直撐著不選，隨著剩下的人越來越少，「繼續找」的期望值也會無情地往下跌。

既然一邊在漲、一邊在跌，這兩條線，注定會產生一個「黃金交叉」。

這個交叉點非常重要，它幫我們確立了「解的形狀」： - 在交叉點之前，繼續找的期望值比較高，所以不管遇到誰，我們一律放棄； - 但是，一旦越過了這個門檻，只要遇到「目前為止最好的人」，我們就毫不猶豫地錄取他！

4. Bruss Algorithm 與 Odds 的推導

既然知道了策略是切出一個門檻，那這個門檻具體到底在幾趴？這時候，我們就要請出 Optimal Stopping 領域最漂亮的公式：Bruss Algorithm。

我們畫一個狀態圖來推導。

假設每一個面試者是最好人選的機率是 \(P\)，不是最好的機率是 \(Q\)。如果選到了不是最好的人，比賽就要繼續，這就是走 \(Q\) 的路線；如果抽中最好的人，就是走 \(P\) 的路線。 假設我們在第 \(S\) 個人的時候決定停下來，我們把天平的兩端拿出來比：

• 天平的一邊，是你選擇「現在就停」。那你後面必須全部槓龜，才會證明你現在選的是對的。 所以機率是從第 \(S+1\) 個 \(Q\)，一路連乘到第 \(N\) 個 \(Q\)。(語音讀法：從 Q s 加 1，一路連乘到 Q n)

• 天平的另一邊，是你選擇「繼續找」。要贏的話，代表後面「至少要發生一次」選到最好的人。也就是把剛才那一長串的 \(Q\) 連乘裡面，把其中一個 \(Q\) 換成 \(P\) 的所有組合，全部加總起來。

當我們把天平兩端相等，也就是找出那個黃金交叉點的時候，神奇的事情發生了。 只要把右邊的一大串加總，除以左邊的 \(Q\) 連乘。每一個組合裡的 \(Q\) 都會被消掉，只剩下 \(P\) 除以 \(Q\)。

\(P\) 除以 \(Q\) 是什麼？在機率論裡，這就叫做 Odds，賠率！ Bruss 演算法證明了，只要你從最後面開始，把每一個人的 Odds 加起來。當這個總和「剛好超過 1」的那一瞬間，就是你該設立門檻的完美停損點！

5. 結論

這個數學公式非常漂亮，算出秘書問題的答案大約是 37%。很多人看完這種影片，就會傻傻地把 37% 當作人生真理去套用。 但說實話，這在現實生活中是不完全合用的。

為什麼？因為數學公式把「選到絕對的第一名」當作 100 分，選到第二名、第三名，甚至是倒數第一名，全部當作 0 分。

但在現實面試、甚至找伴侶的時候，如果你已經看過了 80% 的人，此時遇到一個綜合評估是「目前第二好」的人選，你真的要為了那虛無縹緲的「絕對第一」，而把眼前的第二名放棄掉嗎？當然不該！

現實世界不是非黑即白的 0 與 1。當我們把第二名、第三名的價值也考慮進去時，這個遊戲的規則就會改變。解的形狀不再是單一一個門檻，而是會出現多重門檻（Multiple Thresholds）—— 隨著時間流逝，你會願意妥協的標準會像階梯一樣慢慢放寬。

至於這個「多重門檻」在數學上又該怎麼計算？這其實是 Optimal Stopping 裡更進階的變體。如果大家對這種「更貼近真實人性」的數學推導有興趣，我們下一支影片再來好好聊聊。