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

--- title: 【數學理論】 01. 如何利用數學策略找到真愛 (上) — 最佳停止點理論 (Optimal Stopping Theory) tags: - 【數學理論】 url: https://hackmd.io/QUCJDlnATgeQiyMCRRxHaQ lastSync: 2025-05-25T05:19:38.113Z hackmd: url: https://hackmd.io/QUCJDlnATgeQiyMCRRxHaQ title: 【數學理論】 01. 如何利用數學策略找到真愛 (上) — 最佳停止點理論 (Optimal Stopping Theory) lastSync: 2025-05-25T08:51:40.369Z --- 如何利用數學策略找到真愛 (上) === 最佳停止點理論 (Optimal Stopping Theory) ---  開頭先來說一個故事。 很多人說**牡羊座**衝動，但我認為我是一個異類的牡羊座，每每在進行決策時，我往往都是躊躇不前、沒有反覆思考很難做出決定。不知道有沒有人跟我一樣？ 打個比方，還記得在剛找到現在這份工作時，就開始在挑未來租屋的地方，我跟著我當時的女友兩個人看了很久，東挑西選，總覺得每間都很好，但也總覺得每間都還有可以更好的地方，很難下定決心要挑哪一間。畢竟選了可就很難後悔了。 我意識到，不只是找租屋，挑工作、選伴侶、想三餐要吃什麼這種需要進行無法回頭的決策充斥著我們的日常生活。 那**有沒有一種策略，能夠讓我在進行無法回頭的選擇時，能夠以最大的概率選到最佳的選項？** 答案是有的，就是本篇的重點：「**最佳停止點理論 (Optimal Stopping Theory)**」 剛剛說的最佳停止點「理論」，代表它已經有了結果，結果我放最後，首先先來談談什麼是「**最佳停止點問題 (Optimal stopping problem)**」。 ## 最佳停止點問題 (Optimal stopping problem) 「最佳停止點問題」又被稱為「撿石頭問題」、「秘書問題」、「麥穗問題」、「相親問題」、「止步問題」、「見好就收問題」...，你可以在維基百科上面查到很多不同的名稱，但它的核心問題就在於： >[!Note] **最佳停止點問題 (Optimal stopping problem)** >**「有沒有一種策略，能夠讓我在進行無法回頭的選擇時，能夠以最大的概率選到最佳的選項？」** 舉個例子，以祕書問題為例。 >[!Note] **秘書問題** >有一個老闆想要招聘一位**祕書**，**有 100位想應徵秘書的人。但每次只能面試一人**，而且**面試後就要馬上決定是否聘用他**，如果當時否決了這位應徵者，面試結束就沒有機會再請他回來。面試後老闆都會為每一位應徵者打分數，並且也能和之前應徵者做比較。**那到底要用什麼樣的策略，才能讓最佳人選被選中的概率最大？** 你可能也聽過「撿石頭」問題。 >[!Note] **撿石頭問題** >小時候父母帶你去海邊，你看到滿地的**石頭**，向父母提議想要撿一顆回家，但父母告訴你，**你只能撿一顆，不能撿了留著看到更好的丟掉再撿，也不能回頭再撿**。那麼要如何才能撿到最大的石頭呢？ 相關的問題還有很多，但核心問題就是我剛剛說的：**「有沒有一種策略，能夠讓我在進行無法回頭的選擇時，能夠以最大的概率選到最佳的選項？」** **答案是有的，而且這種策略能選中最佳的選擇的機率高達** $37\ \%$。 $37\ \%$，很高嗎？ 這麼來想好了，如果說要從 $100$ 個選項中挑到最好的那一個，且每個選項選中的機率相當且均勻分布，那選到最好選項的機率是 $1\%$ 。 但是只要用了這種策略，就能把選到最好的機率提高到 $37\%$ ，等於是從百裡挑一變成三選一的概念。 **機率很高，而且非常高。** >而且手遊抽卡機率 $0.5\%$ 你都抽了，大樂透中獎機率千萬分之一你也買了，$37\ \%$ 不高嗎？ 本篇的重點就是要來介紹這種策略，並且利用數學方式推導並驗證 $37\%$ 是怎麼來的。 > [!TIP] **提醒** > 想當然爾接下來的篇幅會充滿數學式，如果你極度討厭數學、看到數學課本只會想撕爛、恨不得數學從教育裡拔掉的人，請直接跳到[**這裡**](https://hackmd.io/@lewisjjj800/ry37qUxfex?view#%E7%B5%90%E8%AB%96)看結論吧XD。 如果你不排斥數學，甚至跟我一樣還有點喜歡的，不妨跟隨我的腳步，讓我帶你了解這個策略以及 $37\ \%$ 的由來。 在那之前，請先容許我介紹一個長得很奇怪，卻又非常能代表數學之美的常數-**「自然常數 $e$ (Eular's number)」** ## **什麼是「自然常數 $e$ (Eular's number)」？** 自然常數 (以下大部分直稱為 $e$ ) 的值大約等於 $e = 2.718281828459045...$，是一個無理數，和 $\pi$ 一樣。 我記得高中在學對數的時候，會認識各種以不同數字為底的對數，例如「**以 $2$ 為底的二進位對數**」 $$ \log_2N $$ 或是「**以 $10$ 為底的常用對數**」 $$ \log_{10}N $$ 這時還有一個「**以自然常數** $e$ **為底的自然對數**」 $$ \log_{e}N= \ln N $$ **這時我整個就不爽了**，為什麼一個看起來這麼不自然的數會被稱作自然常數，作為底數時它的對數記法還這麼特立獨行？ 二進制是電腦的記數系統，包含位元、邏輯閘等都是以二進制來計算，這對電腦來說非常**自然**。 十進制就不用說了，我們十根手指頭，以十進制計算對我們來說非常**自然**。 那自然對數 $e$ 到底**自然**在哪？ 要了解這個問題，我們得先談談**複利與增長極限**。 ## **複利增長極限** 我們都知道把錢存在銀行裡是有利息的，如果把利息連著本金繼續存著，本金會連帶利息在下一次結算利息時連本帶利一起算，就是所謂的**利滾利，把本金越滾越大**。 <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/01/01.jpg" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 假如你現在走在路上，然後**潮爽der撿到100塊咧~** <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/01/02.png" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 你把它存到一間年利率是 $1$ 的銀行，也就是說你一年後可以拿到 $$ 100\times(1+1)^1=200 $$ 這間銀行很佛心，不但利率超高，你發現還可以讓你自由選擇期數的長短，所以你告訴銀行，你想要讓期數變成 $2$，也就是一年結算 $2$ 次利息，所以一年後你可以拿到 $$ 100\times(1+\dfrac{1}{2})^2=225 $$ 你發現期數變多，最後拿到的錢好像也變多了，所以你向銀行要求每個月都幫我結算一次利息，所以一年後你可以拿到 $$ 100\times(1+\dfrac{1}{12})^{12}=261 $$ 又變更多了，這實在是太爽了，按照這個規律來看，**如果我期數變得無限大，每分每秒都要求銀行幫我結算利息，時間一久不就成了億萬富翁了？** 很可惜並不會，如果本金是100，那一年後結算了一萬次利息大概可以拿回272塊，一年後結算了一百萬次利息還是只有272塊，一千萬次、一億次，你都只能拿回272塊，這就是**增長的極限**，最後你的錢會收斂到一個定值。 我們來把剛剛的範例寫成數學式，定值如下。 $$ \displaystyle\lim_{n\to\infty}(1+\dfrac{1}{n})^n=2.718281828459045... $$ 聰明的你大概已經發現或是早就知道了，這就是 $e$ 的定義 $$ \displaystyle\lim_{n\to\infty}(1+\dfrac{1}{n})^n=e $$ 你現在已經知道 $e$ 的定義是什麼了，接下來我再跟你說個故事。 ## 國王的棋盤 >[!Note] **國王的棋盤** > **相傳古印度的一位國王因為象棋的發明而賞賜象棋的發明者，再那個糧食缺乏的年代，這個發明者在棋盤的第一格放下一粒米，要求國王從明天開始在下一格放下前一天雙倍的米，第二天兩粒，第三天四粒，第四天八粒...** <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/01/03.jpg" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 我想你大概已經猜到這個故事的結局了，但結局並不是重點，讓我們觀察一下棋盤上米粒數量的變化。 第一天有 **1** 粒米，第二天會比第一天多 **1** 粒米，第二天有 2 粒米。第二天有 **2** 粒米，第三天會比第二天多 **2** 粒米，第三天有 4 粒米。第三天有 **4** 粒米，第四天會比第三天多 **4** 粒米，第四天有 8 粒米。 按照這個規律我們可以發現，明天會多幾粒米，會跟我今天有幾粒米有關，也就是說**今天有 $n$ 粒米，明天就會多 $n$ 粒米**。 所以我們可以很輕易的推斷：**「我現在米粒的數量等於米粒的變化數量。」** 可以寫成以時間 $t$ 表示的數學式 $$ \dfrac{2^{t+dt}-2^t}{dt} $$ 我想你大概已經發現，當 $dt$ 無限小，上面這個式子其實就是 $2^t$ 的微分。所以我們可以寫成以下這個式子： $$ \lim\limits_{dt\to 0}\dfrac{2^{t+dt}-2^t}{dt} $$ 而因為 $2^{t}$ 跟 $dt$ 沒有關係，所以我們可以把 $2^{t}$ 提出來： $$ 2^t\times\lim\limits_{dt\to 0}\dfrac{2^{dt}-1}{dt} $$ >因為 $2^t$ 當中的 $t$ 是變數，而 $dt$ 只是一個很小的值。 現在我們重點關注 $\lim\limits_{dt\to 0}\dfrac{2^{dt}-1}{dt}$ ，並且令 $\dfrac{2^{dt}-1}{dt}$ 為 $k$，可得： $$ \dfrac{2^{dt}-1}{dt}=k $$ 接下來我們進行一些移項的步驟： $$ 2^{dt}=1+k\cdot dt $$ $$ dt=\log_{2}(1+k\cdot dt) $$ 將上式同除以 $k$，可得： $$ \dfrac{dt}{k}=\dfrac{1}{k}\times \log_{2}(1+k\cdot dt) $$ 再把 $dt$ 移到等號右側，可得： $$ \dfrac{1}{k}=\dfrac{1}{k\cdot dt}\times \log_{2}(1+k\cdot dt) $$ 接下來我們令 $k\cdot dt=\dfrac{1}{n}$，上式就會變成： $$ \dfrac{1}{k}=n \times \log_{2}(1+\dfrac{1}{n}) $$ 因為對數的性質，可得以下式子： $$ \dfrac{1}{k}=\log_{2}(1+\dfrac{1}{n})^{n} $$ 接下來我們把極限給取回來。 $$ \lim\limits_{n\to \infty}\dfrac{1}{k}=\lim\limits_{n\to \infty}[\log_{2}(1+\dfrac{1}{n})^{n}] $$ >因為 $k\cdot dt=\dfrac{1}{n}$ ，也就是 $n=\dfrac{1}{k\cdot dt}$ ，所以當 $dt\to 0$ 也就等於 $n\to \infty$ 而因為 $\lim\limits_{n\to \infty}\dfrac{1}{k}=\dfrac{1}{k}$，因此： $$ \dfrac{1}{k}=\lim\limits_{n\to \infty}[\log_{2}(1+\dfrac{1}{n})^{n}] $$ 我們都知道，**連續函數的極限交換性**，也就是： >[!Note] **連續函數的極限交換性** >若一個函數 $f(x)$ 是**連續函數**，當 $\lim\limits_{x\to a}f(x)=L$ 且 $L$ 存在時，該函數的極限具有以下性質： >$$ \lim\limits_{x\to a}f(g(x))=f(\lim\limits_{x\to a}g(x)) $$ 而 $log(x)$ 就是一個定義域在 $(0,\infty)$ 的**連續函數**，因此以下兩式相等： $$ \lim\limits_{n\to \infty}[\log_{2}(1+\dfrac{1}{n})^{n}]=\log_{2} \ [\lim\limits_{n\to \infty}(1+\dfrac{1}{n})^{n}] $$ 所以 $\dfrac{1}{k}$ 就等於： $$ \dfrac{1}{k}=\log_{2} \ [\lim\limits_{n\to \infty}(1+\dfrac{1}{n})^{n}] $$ 這時，我們會發現，$\lim\limits_{n\to \infty}(1+\dfrac{1}{n})^{n}$ 就是 $e$，因此可得： $$ \dfrac{1}{k}=\log_{2}(e)=\dfrac{\log(e)}{\log(2)} $$ 接下來我們取倒數。 $$ k=\dfrac{\log(2)}{\log(e)}=\log_{e}(2)=\ln(2) $$ 而最一開始的式子是 $$ \lim\limits_{dt\to 0}\dfrac{2^{dt}-1}{dt}=k $$ 再把 $k=\ln(2)$ 代回上式可得： $$ \lim\limits_{dt\to 0}\dfrac{2^{dt}-1}{dt}=\ln(2) $$ 我們最一開始要算的是 $2^t$ 的微分：$\lim\limits_{dt\to 0}\dfrac{2^{t+dt}-2^t}{dt}$，所以最後我們可以得到： $$ \lim\limits_{dt\to 0}\dfrac{2^{t+dt}-2^t}{dt}=2^{t}\cdot \ln(2) $$ 所以 $2^t$ 的微分就等於 $2^{t}\cdot \ln(2)$。 事實上，我們把上面所有推導過程的底數 $2$ 換成一個常數 $a$ 進行推導，就可以獲得指數函數微分的公式： >[!Tip] **指數函數的微分** >當 $y(x)=a^x$ 則 $\dot{y}(x)=a^x\cdot \ln(a)$ 由上式可知： $$ 當\space a=e \space \space 則 \space \space \dot{y}(x)=e^x\cdot \ln(e)=e^x $$ $e^x$ 微分就是它自己本身，因為 $\ln(e)=1$。 怎麼去直觀理解「$e^x$ 微分就是它自己本身」這件事呢？我們都知道，**微分**就是取連續函數曲線的**切線斜率**，因此我們可以利用以下程式來描繪 $e^x$ 以及其切線斜率變化的圖形： :::spoiler 點擊以查看程式碼 ```python= import numpy as np import matplotlib.pyplot as plt from matplotlib.animation import FuncAnimation import matplotlib.animation as animation # Set up the figure and axis fig, ax = plt.subplots(figsize=(12, 8)) x_vals = np.linspace(0, 5, 400) y_vals = np.exp(x_vals) line_func, = ax.plot(x_vals, y_vals, label=r"$e^x$", color="blue", linewidth=2) line_tangent, = ax.plot([], [], "--", label="Tangent line", color="orange", linewidth=2) point, = ax.plot([], [], 'ro', markersize=8) # 創建文字顯示區域 point_text = ax.text(0, 0, "", ha='center', va='bottom', color="red", fontsize=10, bbox=dict(boxstyle="round,pad=0.3", facecolor="yellow", alpha=0.7)) info_text = ax.text(0.5, np.exp(5) * 0.9, "", ha='left', va='top', color="black", fontsize=12, bbox=dict(boxstyle="round,pad=0.5", facecolor="lightblue", alpha=0.8)) ax.set_xlim(0, 5) ax.set_ylim(0, np.exp(5)) ax.set_title("Function $e^x$ and Its Tangent Line", fontsize=14) ax.set_xlabel("x", fontsize=12) ax.set_ylabel("y", fontsize=12) ax.axhline(0, color='gray', linewidth=0.5) ax.axvline(0, color='gray', linewidth=0.5) ax.legend(fontsize=11) ax.grid(True, alpha=0.3) def init(): line_tangent.set_data([], []) point.set_data([], []) point_text.set_text("") info_text.set_text("") return line_tangent, point, point_text, info_text def update(frame): x0 = frame y0 = np.exp(x0) # e^x 的值 slope = y0 # e^x 的導數也是 e^x，所以斜率等於函數值 # 計算切線 tangent_x = np.array([x0 - 0.8, x0 + 0.8]) tangent_y = slope * (tangent_x - x0) + y0 # 更新圖形元素 line_tangent.set_data(tangent_x, tangent_y) point.set_data([x0], [y0]) # 更新點位置標籤 point_text.set_position((x0, y0 + 5)) point_text.set_text(f"({x0:.2f}, {y0:.2f})") # 更新資訊顯示 info_text.set_text(f"x = {x0:.2f}\n$e^x$ = {y0:.3f}\nSlope = {slope:.3f}") return line_tangent, point, point_text, info_text # Create animation for x0 from 1 to 5 (100 frames) frames = np.linspace(1, 5, 100) ani = FuncAnimation(fig, update, frames=frames, init_func=init, blit=True, interval=100) # 顯示動畫 plt.tight_layout() plt.show() # 存成動畫 gif_path = "exp_function_tangent_improved.gif" ani.save(gif_path, writer='pillow', fps=10) ``` ::: 根據上面的程式，我們可以輸出以下動圖。 <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/01/04.gif" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 動圖左上角可以看到，有三個參數： - $x$ 代表函數的變數 - $e^x$ 代表藍色曲線在 $x$ 增加時，$e^x$ 的值。 - Slope 代表橘色切線在 $x$ 增加時，橘色切線的斜率。 我們會發現，$e^x$ 跟 Slope 在 $x$ 增加時，兩者的值一直都是相同的。 $e^x$ 跟 $e^x$ 的切線斜率相同，代表 $e^x$ 跟 $e^x$ 的微分相同。 ## 怪美的數學常數現在你已經知道 $e^x$ 微分就是它自己本身，也就是 $\dfrac{de^x}{dx}=e^x$，這時就體現 $e^x$ 的重要性。 如果要描述一個物理現象的狀態 (無論是運動狀態、電流電壓...)，通常會是以微分方程 (Differential equation)，因為我要了解它的狀態，以及狀態的變化，所以建立一個數學模型以進行**預估**甚至**控制**，以一個簡單的RLC電路為例： <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/01/05.png" alt="圖片描述" style="display: block; margin: 0 auto;" width="600"> 上圖這個RLC電路能夠以常微分方程(Odinary Differential Equation ODE) 來表示如下。 $$ L\dfrac{d^2i(t)}{dt^2}+R\dfrac{di(t)}{dt}+\dfrac{i(t)}{C}=0 $$ 將 $L=1\ H, \ R=3\ \Omega, \ C=0.5\ F$ 代入上式，則 $$ \dfrac{d^2i(t)}{dt^2}+3\dfrac{di(t)}{dt}+2{i(t)}=0 $$ 這時如果想解這個常微分方程，通常會假設 $i(t)=e^{mt}$ 再求出 $m$，這是因為如果假設成以其他數為底的指數函數，例如 $i(t)=a^t$，每進行一次微分就會多出一個 $ln(a)$ ，上面這個二階的ODE就會微了兩次，這還只是二階而已，如果出現更高階的ODE，就會多出很多不必要的常數 $ln(a)$。 但是假設 $i(t)=e^{mt}$ 就會免除掉很多麻煩，解會變得很乾淨漂亮。 讓我們快速解上面這個微分方程。 由於現在 $i(t)=e^{mt}$ 所以同理可證 $\dfrac{di(t)}{dt}=me^{mt},\\\ \dfrac{d^2i(t)}{dt^2}=m^{2}e^{mt}$，把 $\dfrac{di(t)}{dt}$ 以及 $\dfrac{d^2i(t)}{dt^2}$ 代入原ODE可得： $$ m^{2}e^{mt}+3me^{mt}+2e^{mt}=(m^{2}+3m+2)e^{mt}=0 $$ 此時我們求出 $m^{2}+3m+2=0$ 的特徵值 (eigen value) 可得 $m=-1\ or\ -2$ 此時ODE的通解應為 $$ i(t)=C_1e^{-t}+C_2e^{-2t} \ \ \ \ \ where \ \ C_1 \ \ and \ \ \ C_2 \ \ are \ \ constants. $$ >請容許我不給初始值，因為我懶得再解特解。 唯有長得如此奇怪的 $e$ 才能得出這麼漂亮且簡單的解，這就是為什麼我說 $e$ 長得很奇怪，卻又是個非常能代表數學之美的常數。 相信看到這邊的你已經對 $e$ 有了充分的了解，但 $e$ 並不是本篇的重點，**關於找到真愛的數學策略，我放在[下篇](https://hackmd.io/@lewisjjj800/ry37qUxfex)詳談**。 我是Lewis，我們[**下一篇**](https://hackmd.io/@lewisjjj800/ry37qUxfex)專欄見！