引言
當我還在上大學的時候，我從室友那裡聽說過秘書問題，不過當時我並不知道問題的名字，只在印象中留下了一個除以e的結論。
最近我在無意中發現了Secretary Problem，並引起了我的興趣。我意識到若將問題作適當修改，是可以擴展到一系列日常決策當中去，並且發現了可以在生活中使用的例子，特別與Algorithm結合加以考慮。
模型
首先介紹一下秘書問題，指的是在n個候選中拒絕前r-1個，然後從第r開始，如果比前r-1個好，就選中它。所以它也像是挑剔的求婚者問題。
離散
考慮最優選解在選項中是均勻分佈的，將按此策略選出最優解的概率記作$P_r$
$$
P_r = \sum_{i = 1}^{r - 1} \frac{1}{n}\times0 + \sum_{i = r}^n \frac{1}{n}\times\frac{r - 1}{i - 1} = \frac{r - 1}{n} \sum_{i = r}^n \frac{1}{i - 1}
$$
這裡做一些解釋。
1/n指的是最優解在任意候選位置出現的概率，顯然如果落在前r-1個當中（已經被預先捨棄），那麼按此策略選出來的概率就是零。而另一種情況是，假設是在第i個位置選出這個最優解，為了確保這一點，則需要：前i-1個選項當中的最優解（局部而非全局的最優解），必須出現在這i-1個選項的前r-1個當中（i大於r）。
現在考慮極值在什麼地方，顯然要有
$$
P_r \geq P_{r - 1}
$$
以及
$$
P_r \geq P_{r + 1}
$$
第一個條件給出
$$
\sum_{i = r}^n \frac{1}{i - 1} \geq 1
$$
以及第二個條件
$$
\sum_{i = r + 1}^n\frac{1}{i - 1} \leq 1
$$
通俗一點，那就是要求臨界點r滿足
$$
\frac{1}{n - 1} + \frac{1}{n - 2} + … + \frac{1}{r} \leq 1
$$
的同時，且滿足
$$
\frac{1}{n - 1} + \frac{1}{n - 2} + … + \frac{1}{r} + \frac{1}{r - 1} \geq 1
$$
這樣就可以找出r，在程式語言上實現是非常簡單的。
連續
當n很大時，離散就可以視為近似連續了。考慮$n \to \infty$時，考慮$x = r/n$以及$t = i/n$，需要解釋的是我們實質上希望
$$
x = \frac{r - 1}{n}
$$
以及
$$
t = \frac{i - 1}{n}
$$
當分母趨近無窮大時，分子中的常數也就忽略不計了。因此$dt = 1/n$，這樣
$$
P_r \approx x\sum_{i = r}^n\frac{1}{t}dt = x\int_1^x\frac{1}{t}dt = -x\ln x
$$
取微分並令其為零
$$
\frac{dP_r}{dx} = -\ln x - 1 = 0
$$
也就是極值點在
$$
x = \frac{r}{n} = \frac{1}{e}
$$
這個位置。
離散先驗修正
如果實現知道一些關於最優解的分佈信息（這一點可以來自歷史數據的統計），那麼最優解在候選項中就不再是均勻分佈。引入一個概率密度$p_i$，滿足
$$
\sum_{i = 1}^np_i = 1
$$
現在重寫$P_r$
$$
P_r = \sum_{i = 1}^{r - 1} p_i\times0 + \sum_{i = r}^n p_i\times\frac{\sum_{i’ = 1}^{r - 1}p_{i’}}{\sum_{i’ = 1}^{i - 1}p_{i’}} = \sum_{i = r}^n p_i\times\frac{\sum_{i’ = 1}^{r - 1}p_{i’}}{\sum_{i’ = 1}^{i - 1}p_{i’}}
$$
考慮其極值條件
$$
P_r \geq P_{r - 1}
$$
這將給出
$$
\sum_{i = r}^n \frac{p_i}{\sum_{i’ = 1}^{i - 1}p_{i’}} \geq 1
$$
以及另一個條件
$$
P_r \geq P_{r + 1}
$$
同理給出
$$
\sum_{i = r + 1}^n \frac{p_i}{\sum_{i’ = 1}^{i - 1}p_{i’}} \leq 1
$$
以上兩個條件就是離散情況所要求的最後結果。
連續先驗修正
接著考慮連續的情況。同樣$x = r/n$，$t = i/n$以及$t’ = i’/n$，因此
$$
dx = dt = dt’ = \frac{1}{n}
$$
並定義
$$
p(t)dt = p_i
$$
將結果改寫一下
$$
P_r = \sum_{i = r}^n p_i\times\frac{\sum_{i’ = 1}^{r - 1}p_{i’}}{\sum_{i’ = 1}^{i - 1}p_{i’}} = \sum_{i = r}^n p(t)dt\times\frac{\sum_{i’ = 1}^{r - 1}p(t’)dt’}{\sum_{i’ = 1}^{i - 1}p(t’)dt’}
$$
寫成積分的形式
$$
P_r \approx \int_{x}^{1} dtp(t)\times\frac{\int_0^x dt’p(t’)}{\int_0^t dt’p(t’)}
$$
根據Leibniz integral rule取微分
$$
\frac{dP_r}{dx} = -p(x) + \int_x^1 dtp(t)\times\frac{p(x)}{\int_0^t dt’p(t’)}
$$
令其為零，極值應滿足
$$
\int_x^1 dt \frac{p(t)}{\int_0^t dt’p(t’)} = 1
$$
這個條件對應近似連續情況的結果。若令
$$
F(t) = \int_0^t dt’p(t’)
$$
則$P_r$可以寫成如下
$$
P_r = -F(x)\ln[F(x)]
$$
緊湊的結果。
後記
以上源於我對生活的思考。我對原始的Secretary Problem並不滿意，在於候選數目通常是未知的，然而我又不清楚應該如何去處理它。直到我突然想到，似乎可以引入一個先驗的分佈，只要這個分佈足夠複雜，就足以覆蓋所有可能會出現的情況。顯然，無窮大是沒有意義的，也不會有人擁有無限的時間和無窮的機會，通常只需要讓概率密度的末端收斂到零即可。
當然，毫無疑問，你需要事先引入一些信息。我能想到的一個絕好的例子是定時掃描廉價機票，類似Skyscanner，在算法上實現頗為容易，如果可以根據歷史數據給出一個粗略分佈，便可以得到更為理想的結果。原始的Secretary Problem曲線在極值附近十分平坦，而先驗信息可以使之陡峭。
補充實例
指數
考慮指數模型$p(t) \propto a^t$，帶入連續先驗修正
$$
\int_x^1 dt \ln(a)\frac{a^t}{a^t - 1} = \ln\left[\frac{1 - a}{1 - a^x}\right] = 1
$$
解得
$$
\frac{r}{n} = x = \frac{\ln(1-1/e+a/e)}{\ln(a)}
$$
針對極限情況，考慮羅必達法則
$$
\lim_{a \to 1} x = \lim_{a \to 1} \frac{(1-1/e+a/e)/e}{1/a}= 1/e
$$
與秘書問題結果一致。具體計算概率的大小，令$x_c = \frac{\ln(1-1/e+a/e)}{\ln(a)}$，計算概率
$$
P_r = \frac{a^x - 1}{a - 1}\ln\left[\frac{a - 1}{a^x - 1}\right]
$$
代入後不難發現結合了先驗信息的策略最優。
Delta函數
考慮最優解的位置由先驗信息直接給出$p(t) = \delta(t-t_0)$，由於分母不能為零，則要求$x \geq t_0$，代入得到
$$
\int_x^1 dt p(t) = 1
$$
若$x > t_0$，上面等式不能成立，則必有$x \leq t_0$，因此
$$
x = t_0
$$
與日常經驗一致。