【數學理論】 02. 如何利用數學策略找到真愛 (下) — 最佳停止點理論 (Optimal Stopping Theory)

--- title: 【數學理論】 02. 如何利用數學策略找到真愛 (下) — 最佳停止點理論 (Optimal Stopping Theory) tags: - 【數學理論】 url: https://hackmd.io/e1f_0iYZQauCW0_3aHA_3A lastSync: 2025-05-25T08:45:19.364Z hackmd: url: https://hackmd.io/e1f_0iYZQauCW0_3aHA_3A title: 【數學理論】 02. 如何利用數學策略找到真愛 (下) — 最佳停止點理論 (Optimal Stopping Theory) lastSync: 2025-05-25T08:51:47.292Z --- 如何利用數學策略找到真愛 (下) === 最佳停止點理論 (Optimal Stopping Theory) ---  上一篇我已經詳細介紹了最佳停止點問題以及自然常數 $e$ ，本篇就來詳細講解**最佳停止點理論 (Optimal stopping theory)** 我相信有些人可能等得不耐煩了，所以我先說這個策略，以撿石頭為例。 >[!Tip] **策略** >假設總共有 $n$ 顆石頭，先看前面 $k$ 顆石頭，並且將這 $k$ 顆石頭中最大顆的大小記住，接著從第 $k+1$ 顆開始，只要找到比 $k$ 顆石頭中最大顆的還大，那就就撿起來，這樣你撿到最大顆的機率就會是 $37\%$。 下面讓我來分析一下。 ## 策略分析按照上面這個策略，我們設定 $n=10, \ k=5$ 也就是總共有 $10$ 顆石頭，**先看前面五顆石頭**來跟**後面五顆石頭**比較大小。 接下來會有幾種情況。 **情況一、第六顆就是最大顆的石頭。** 這樣撿到最大顆的機率就會是 $\dfrac{1}{10}$ <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/02/01.png" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> **情況二、第七顆才是最大顆的石頭。** 那就代表，在前面六顆當中最大顆的(藍色石頭)只能在**前五顆**，不能在**第六顆**，否則你看完前面五顆，看到第六顆都比前面五顆大，你就會撿走前六顆中最大的**第六顆**，而不是這十顆裡面最大顆的**第七顆**。 <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/02/02.png" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 這樣撿到最大顆的機率就會是 $\dfrac{1}{10}\times \dfrac{5}{6}$ **情況三、第八顆才是最大顆的石頭。** 那就代表，在前面七顆當中最大顆的只能在**前五顆**，不能在**第六顆**或是**第七顆**，否則你看完前面五顆，看到**第六顆**或**第七顆**都比前面五顆大，你就會撿走前面七顆當中最大的，而不是這十顆裡面最大顆的**第八顆**。 <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/02/03.png" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 這樣撿到最大顆的機率就會是 $\dfrac{1}{10}\times \dfrac{5}{7}$ **情況四、第九顆才是最大顆的石頭。** 那就代表，在前面八顆當中最大顆的只能在**前五顆**，不能在**第六顆**、**第七顆**或是**第八顆**，否則你看完前面五顆，看到**第六顆**、**第七顆**或是**第八顆**都比前面五顆大，你就會撿走前面八顆當中最大的，而不是這十顆裡面最大顆的**第九顆**。 <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/02/04.png" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 這樣撿到最大顆的機率就會是 $\dfrac{1}{10}\times \dfrac{5}{8}$ **情況五、**第十顆**才是最大顆的石頭。** 那就代表，在前面九顆當中最大顆的只能在**前五顆**，不能在**第六顆**、**第七顆**、**第八顆**或是**第九顆**，否則你看完前面五顆，看到**第六顆**、**第七顆**、**第八顆**或是**第九顆**都比前面五顆大，你就會撿走前面九顆當中最大的，而不是這十顆裡面最大顆的**第十顆**。 <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/02/05.png" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 這樣撿到最大顆的機率就會是 $\dfrac{1}{10}\times \dfrac{5}{9}$ 把這五種情況的機率都加起來就會得到 \begin{aligned} P&=\dfrac{1}{10}+\dfrac{1}{10}\times \dfrac{5}{6}+\dfrac{1}{10}\times \dfrac{5}{7}+\dfrac{1}{10}\times \dfrac{5}{8}+\dfrac{1}{10}\times \dfrac{5}{9}\\ &= \dfrac{1}{10}\times (1+\dfrac{5}{6}+\dfrac{5}{7}+\dfrac{5}{8}+\dfrac{5}{9})\\ &\approx 0.37281746031 \end{aligned} 假如你從這 $10$ 顆石頭裡面選一顆，選到最大顆的機率只有 $\dfrac{1}{10}$ ，利用這種策略你可以將機率提高到 $37 \%$ 你可能會問：**「一條路上可能不只有 $10$ 顆石頭，只要路夠長，可能有趨近於無限多顆嗎？」** 沒錯，所以我們現在將情況拓展到無限多種，來進行**最佳停止點理論的數學證明**。 ## 數學證明先來回顧一下最佳停止點理論在無限多種選項時的策略： >[!Tip] **策略** >令撿到最大顆的機率為 $P(k)$ ，總共有 $n \to \infty$ 顆石頭，先看前面 $k$ 顆石頭。 這樣 $P(k)$ 就會是 \begin{aligned} P(k) &=(\dfrac{k}{n}\times (\dfrac{1}{k}+\dfrac{1}{k+1}+\dfrac{1}{k+2}+...+\dfrac{1}{n-1}))\\ &= (\dfrac{k}{n}\times \displaystyle\sum_{m=k}^{n-1}\dfrac{1}{m}) \end{aligned} 接下來我們就針對上面的 $P(k)$ 來進行證明。 --- ### 1. 級數近似 首先，我們把 $\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k}^{n-1}\dfrac{1}{m}$ 稍微改寫如下： \begin{aligned} \displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k}^{n-1}\dfrac{1}{m}&=\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{1}{m-1} \end{aligned} 此時由於 $n \rightarrow \infty$ ，因此以下兩個極限相等。 \begin{aligned} \displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{1}{m-1}&=\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{1}{m} \end{aligned} 所以我們可以得出以下這個結果： \begin{aligned} \displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{1}{m-1}&=\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{1}{m} \end{aligned} > 只有在 $n \rightarrow \infty$ 時，上面這個等式才會成立，否則令 $k=1$、$n=5$ 試試看，會發現兩個極限結果不相等。 接著再稍微改寫一下 \begin{aligned} \displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{1}{m}&=\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{n}{m}\cdot\dfrac{1-0}{n} \end{aligned} 眼尖的人大概發現了，上面這個形式跟黎曼和的極限，也就是 **黎曼積分（Riemann integral）** 。 > [!Note] **黎曼積分（Riemann integral）** > > $$ > \displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=1}^{n}f(x^*_m) \cdot \dfrac{b-a}{n}=\int_{a}^{b}f(x)dx > $$ > 上面符號的涵義後面會說明 但其實比較一下，會發現我們推導出來的結果 $\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{n}{m}\cdot\dfrac{1-0}{n}$ 當中是 $m=k+1$ 而非黎曼積分當中的 $m=1$ 。 **接下來就是我覺得最絕妙的地方了。** --- ### 2. 黎曼積分小區間的縮減與上下限的變化 $\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{n}{m}\cdot\dfrac{1-0}{n}$ 就不是黎曼積分了嗎？其實還是，只是上下限改變了，讓我用數學的方式來證明： 我們考慮一個函數 $f(x)$ 在區間 $[a,b]$ 的黎曼積分，並將區間 $[a,b]$ 劃分成 $n$ 等份，這樣就有 $n$ 個小區間，而每個小區間的長度為 $\Delta x=\dfrac{b-a}{n}$ 接下來我們定義 $x_m=a+m\Delta x$ 是小區間的「端點」，而 $x^*_m$ 就是小區間內的一個點，這樣我們就有以下這個黎曼和。 \begin{aligned} \Phi_n&=\displaystyle\sum_{m=1}^{n}f(x^*_m) \Delta x \end{aligned} 此時當我們將 $n$ 個小區間中前 $k$ 個拿走，這樣這個黎曼和 $\Phi_n$ 就會發生變化。 首先這樣黎曼和 $\Phi_n$ 的區間 $[a,b]$ 就會變成 $[a+k\Delta x,b]$，因為原本有 $n$ 個小區間，現在只剩下 $n-k$ 個小區間，區間的起點發生平移了，所以原始的黎曼和 $\Phi_n$ 就會發生以下變化： :::info - 區間起點：$a\longrightarrow a'=a+k\Delta x$ - 小區間的數量：$n\longrightarrow n-k$ - 小區間的長度：和原本一樣是$\Delta x$ ::: 因此新的黎曼和就會變成 \begin{aligned} \Phi_{n-k}&=\displaystyle\sum_{m=k+1}^{n}f(x^*_m) \Delta x \end{aligned} 然而只要進行轉換，令 $j=m-k$ ，新的黎曼和就能寫成 \begin{aligned} \Phi_{n-k}&=\displaystyle\sum_{j=1}^{n-k}f(x^*_{j+k}) \Delta x \end{aligned} 其實跟我們熟悉的黎曼和是一樣的。 所以將黎曼和推向極限時，原本的黎曼和 $\Phi_n$ 就能寫成： \begin{aligned} \displaystyle\lim_{n\to\infty}\Phi_n&=\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=1}^{n}f(x^*_m) \cdot \dfrac{b-a}{n}\\&=\int_{a}^{b}f(x)dx \end{aligned} 前 $k$ 個小區間移走的黎曼和 $\Phi_{n-k}$ 由於起點 $a$ 平移成 $a+k\Delta x$ ，所以就會變成 \begin{aligned} \displaystyle\lim_{n\to\infty}\Phi_{n-k}&=\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}f(x^*_{j+k}) \cdot \dfrac{b-a}{n}\\&=\int_{a+k\Delta x}^{b}f(x)dx \end{aligned} 因此回過頭來看到最一開始的黎曼積分$\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}\dfrac{n}{m}\cdot\dfrac{1-0}{n}$，再跟上面的式子比較一下，我們可以發現： - $a=0$ - $b=1$ - $\Delta x=\dfrac{1}{n}$ - $f(y)=\dfrac{1}{y}$ 最後再加上我們最一開始定義的 $\dfrac{k}{n}=t$ ，黎曼積分 $\displaystyle\lim_{n\to\infty}\Phi_{n-k}$ 就可以寫成： \begin{aligned} \displaystyle\lim_{n\to\infty}\Phi_{n-k}&=\displaystyle\lim_{n\to\infty}\displaystyle\sum_{m=k+1}^{n}f(x^*_{j+k}) \cdot \dfrac{b-a}{n}\\&=\int_{a+k\Delta x}^{b}f(x)dx\\&=\int_{t}^{1}\dfrac{1}{y}dy \end{aligned} >[!NOTE] 註 > 上面提到的 $y$ 只是啞變數 (dummy variable) --- ### 3. 積分計算將級數近似成積分的工作完成了，接下來計算積分 \begin{aligned} \int_{t}^{1}\dfrac{1}{y}dy&=\ln(1)-\ln(t)\\ &=\ln(\dfrac{1}{t}) \end{aligned} 因為 $t=\dfrac{k}{n}$ ， $P(k)$ 就會等於 \begin{aligned} P(k)&=\dfrac{k}{n}\cdot \ln(\dfrac{1}{t})\\ &=t\cdot \ln(\dfrac{1}{t})\\ &=-t\cdot \ln(t) \end{aligned} 最後我要求出 $P(k)$ 的極值，只要令 $\dfrac{dP(k)}{dt}=0$ 進行計算即可。 因為 $P(k)=-t\cdot \ln(t)$ 且 $\dfrac{dP(k)}{dt}=0$，所以我們可以得到以下等式： $$ \dfrac{d(-t\cdot \ln(t))}{dt}=0 $$ $-t\cdot \ln(t)$ 的微分我們利用微分的乘積法則可得： $$ -1- \ln(t)=0 $$ 此時因為 $-1- \ln(t)=0$，因此 $\ln(t)=-1$，所以我們可以得到： $$ t=1/e \approx0.368=36.8\% $$ --- ### 4. 證明結果我們復盤一下。 >[!Tip] **策略** >**撿到最大顆的機率為 $P(k)$ ，總共有 $n$ 顆石頭，先看前面 $k$ 顆石頭。** 所以 $t=\dfrac{k}{n}$ 代表著： $\dfrac{k}{n}=\dfrac{先看的石頭數量}{總共的石頭數量}=$ 前 $t\times 100\%$ 的石頭 而 $t$ 被我們計算出來的結果是 $t=1/e\approx36.8\%$ ，所以當 $t=\dfrac{k}{n}=1/e\approx36.8\%$ 代表我先看前 $36.8\%$ 的石頭，記住這些石頭裡面最大顆的。 而當 $t=\dfrac{k}{n}=1/e\approx36.8\%$ 時 \begin{aligned} P(k)&=-t\cdot ln(t)\\&=-1/e\cdot ln(1/e)\\ &=-1/e\cdot (-1)\\ &=1/e\approx36.8\% \end{aligned} 剛好也是 $36.8\%$ 所以後面遇到比前 $36.8\%$ 的石頭還大顆的就撿起來，這樣你撿到最大顆的機率就會是 $P(k)=1/e\approx36.8\%$ --- ## 結論所以，講了這麼多數學的東西，**最佳停止點理論 (Optimal Stopping Theory)** 就是： >[!Important] **最佳停止點理論 (Optimal Stopping Theory)** >假設總共有 $n$ 個選擇，先看前 $k$ 個，只看不選，並且將這 $k$ 個選擇當中最好的選擇記住，接著從第 $k+1$ 個選擇開始，只要找到比前 $k$ 個還要好的，那就選擇它，這樣你選到最好的機率就會是 $37\%$。 我們可以利用`python`寫一個程式，來呈現可視化的結果： :::spoiler 點擊以查看程式碼 ```python= import numpy as np import matplotlib.pyplot as plt from matplotlib.animation import FuncAnimation def calculate_optimal_probability(n): """計算在n個候選人中使用最優策略的成功概率""" if n <= 1: return 1 optimal_k = int(n/np.e) # 最優停止點 prob = 0 for i in range(optimal_k + 1, n + 1): prob += (optimal_k / (i - 1)) # 在位置i選中最佳候選人的概率 prob /= n return prob def get_strategy_success_rate(n, k): """計算使用k作為停止點的策略成功率 n: 總候選人數 k: 觀察k個候選人後開始考慮聘用 """ if k >= n: return 0 prob = 0 for i in range(k + 1, n + 1): prob += (k / (i - 1)) prob /= n return prob # 創建圖表 plt.style.use('seaborn-v0_8') fig, (ax1, ax2) = plt.subplots(2, 1, figsize=(12, 10)) fig.suptitle('The Secretary Problem: Analysis of Optimal Stopping Strategy', fontsize=14, pad=20) # 第一個子圖：不同n值的最優概率 n_values = range(1, 101) optimal_probs = [calculate_optimal_probability(n) * 100 for n in n_values] ax1.plot(n_values, optimal_probs, 'b-', linewidth=2) ax1.set_xlabel('Total Number of Candidates') ax1.set_ylabel('Success Rate (%)') ax1.set_title('Optimal Strategy Success Rate vs. Number of Candidates') ax1.grid(True, linestyle='--', alpha=0.7) # 標記一些特殊點 special_ns = [10, 20, 50, 100] for n in special_ns: prob = calculate_optimal_probability(n) * 100 ax1.plot(n, prob, 'ro') ax1.annotate(f'n={n}\n{prob:.1f}%', xy=(n, prob), xytext=(10, 10), textcoords='offset points', bbox=dict(boxstyle='round,pad=0.5', fc='white', ec='gray', alpha=0.7)) # 第二個子圖：固定n值下，不同k值的成功率 n_fixed = 100 # 固定候選人數為100 k_values = range(1, n_fixed) success_rates = [get_strategy_success_rate(n_fixed, k) * 100 for k in k_values] ax2.plot(k_values, success_rates, 'g-', linewidth=2) ax2.set_xlabel('Observation Window (k)') ax2.set_ylabel('Success Rate (%)') ax2.set_title(f'Success Rate vs. Observation Window (n={n_fixed})') ax2.grid(True, linestyle='--', alpha=0.7) # 標記最優k值 optimal_k = int(n_fixed/np.e) optimal_rate = get_strategy_success_rate(n_fixed, optimal_k) * 100 ax2.plot(optimal_k, optimal_rate, 'ro') ax2.annotate(f'Optimal k={optimal_k}\n{optimal_rate:.1f}%', xy=(optimal_k, optimal_rate), xytext=(10, 10), textcoords='offset points', bbox=dict(boxstyle='round,pad=0.5', fc='white', ec='gray', alpha=0.7)) plt.tight_layout() # 保存圖表 plt.savefig('secretary_problem.png', dpi=300, bbox_inches='tight') # 顯示圖表 plt.show() ``` ::: 由上面的程式可以輸出以下結果： <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/02/06.gif" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 由上面這張圖分成上下兩個部分，可以看到： **上半圖**：展示了隨著候選人總數 $n$ 的增加，使用最佳停止策略的成功率變化。 - 橫軸：候選人總數 - 縱軸：成功選中最佳候選人的概率 - **紅點**標記了最後圖形收斂的 $n$ 值和對應的成功率 **下半圖**：展示了在固定候選人數 $n=100$ 的情況下，不同 $k$ 的成功率 - 橫軸：不同 $k$ 值 - 縱軸：成功率 - **紅點**標記了最優的 $k=n/e$ 值和對應的成功率。 --- 最後我們拿生活當中的例子來比喻一下： 如果說你今天要找**租屋**，預計要找100間，先看前37間，只看不選，將這37間當中最好的記住，接著從第38間開始，只要找到比前37間還好的那就選，這樣選到最好的那間機率就會是 $37\%$。 又或者是：如果說你今天要找**男女朋友**，預計要找100位，先看前37位，只看不選，將這37位當中最好的記住，接著從第38位開始，只要找到比前37位還好的那就選，這樣選到最好的那位機率就會是 $37\%$。 又或者：如果說你在夜深人靜的時候點開某種網站想看**學術影片**，預計要找100頁，先看前37頁，只看不選，將這37頁當中最好的記住，接著從第38頁開始，只要找到比前37頁還好的那就選，這樣選到最好的那頁機率就會是 $37\%$。 再不然就是：如果說你今天要**跟朋友幹架**，預計要被打100拳，那你就先被揍37拳，只被揍不躲，將這37拳當中最痛的那拳記住，接著從第38拳開始，你醒來就會在醫院了。(本專欄不支持與提倡暴力) 你可能會覺得說：**欸不是，無論是找房子、交男女朋友，都不適用於這個方法，不要說100個，可能連10個都懶了，而且好壞跟美醜都無法量化。** 確實，這篇專欄所提到的都只是 **「策略」** 而非 **「方法」**，如果是抱持著必能選到最好的選擇而來，那肯定會失望，畢竟這個策略並非那麼的 **「實際」**。 你可能聽過一句話：**「小孩子才做選擇，大人全都要！」**，但**大人才更應該做選擇，學會選擇就是在學會放棄，選擇比努力重要，但是放棄比選擇更重要**。 ***「選擇，就是承擔。」*** 如果你在人生的交叉路口當中選擇，或是已經選了卻反悔了，那有一句話是這麼說的： **擇你所愛，愛你所選。** 放下執念，生活會更美好。 我是Lewis，我們[**下一篇**](https://hackmd.io/@lewisjjj800/r1yyOQgfxx)專欄見！