寻找最优者：不可逆的做出选择，如何使得选到最优者的概率最大，又称为1/e法则，“秘书问题”或“相亲问题“
题目描述
- 由于无人知道缘分何时到来，假设人的一生会遇到100个异性，这100个人参差不齐，其中有个人是最好的，100人随机的排着队出现，而我们对每个人必须决定是否接受，而且一旦决定后不能修改，那么用什么策略选择更有机会选到最好的那一个呢?
解决方案
策略设想
- 拒绝前 k 个人，然后从第 k+1 个开始，只要 优于前面的所有人 ，则接受
- k 值的设定比较难，太小了容易找到不好的，太多了容易错过最好的
证明
- 假设最优者出现在第 \(i(k< i \leq n)\) 个(事件A)，那么最优者被选中(事件B)的概率为前i-1个中的最优者在前k个人中的概率
$$ P(B|A) = \frac{k}{i-1} $$- \(P(B|A) = P(最优者被选中|第 i 个为最优者)\)
- 最优者出现在第 \(i\) 个的概率为
$$P(B) = \frac{1}{n}$$ - 最优者被选中的概率为
- 接下来的证明用到了调和级数的和，详情参考调和级数的和
$$
\begin{align}
\sum_{i=1}^{n}\frac{1}{i} = ln(n) + \gamma + \epsilon_{n}
\end{align}
$$- \(\gamma\) 为欧拉-马歇罗尼常数，近似值为γ≈0.57721，下面的推导都不需要精确解的，所以可以使用该公式
- \(\epsilon_{n}\) 约等于 \(\frac{1}{2n}\)，随着n的不断增大， \(\epsilon_{n}\) 趋于0
$$
\begin{align}
P(B) &= \sum_{A}P(B,A) \\
&= \sum_{A}P(B|A)P(A) \\
&= \sum_{i=k+1}^{n}\frac{k}{i-1}\frac{1}{n} \\
&= \sum_{i=k+1}^{n}\frac{k}{n}\frac{1}{i-1} \\
&= \frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1} \\
&= \frac{k}{n}\sum_{i=k}^{n-1}\frac{1}{i} \\
&= \frac{k}{n}(\sum_{i=1}^{n-1}\frac{1}{i} - \sum_{i=1}^{k-1}\frac{1}{i}) \\
&\approx \frac{k}{n}((ln(n-1)+C)-(ln(k-1)+C)) \\
&= \frac{k}{n}ln(\frac{n-1}{k-1}) \\
\end{align}
$$
- 当n和k足够大时有
- (不能证明 k 也会足够大，但是直觉上 n 足够大 k 也会足够大，因为 n 足够大时往往需要拒绝更多的人)
$$\frac{n-1}{k-1} = \frac{n}{k}$$
- (不能证明 k 也会足够大，但是直觉上 n 足够大 k 也会足够大，因为 n 足够大时往往需要拒绝更多的人)
- 令 \(x=\frac{k}{n}\)，则有
$$
\begin{align}
f(x) &= xln\frac{1}{x} \\
{f}’(x) &= ln(\frac{1}{x})+(-\frac{1}{x^2}\cdot x \cdot x) \\
&= ln(\frac{1}{x})-1
\end{align}
$$ - 求 \(f(x)\) 的最大值，令 \({f}’(x)=0\) 有
$$ ln(\frac{1}{x})-1 = 0 $$ - 解方程得
$$ x = \frac{1}{e} $$ - 也就是说当 \(\frac{k}{n} = \frac{1}{e} \) 时，找到最优者的概率最大
策略描述
- 拒绝前 \(\frac{n}{e}\) 个人(也就是拒绝前37%的人)，然后从第 \(\frac{n}{e}+1\) 个开始，只要优于前面的所有人 ，则接受
- 这种方式可以保证我们有最大的概率找到最优者