最优终止策略 —— 为什么是 37%？

见好就收。

描述

考虑一个问题：假设现在有若干件同类型商品，每件商品的质量都不一样且商品质量等可能分布，我们在看到商品前不知道商品的质量，且在看商品时无法回退到上一个商品，接下来要从这些商品中挑选一件商品。现在考虑如下策略：

如果有 \(n\) 件商品，我们先依次看前 \(k\ (k \leq n)\) 件商品，不论商品质量如何，都将其舍弃，在随后的 \(n - k\) 件商品中如果出现了质量比前 \(k\) 件商品质量更好的商品，那就选择该商品，请问选择 \(k\) 为多少，可以最大化我们选择到质量最好的商品的概率呢？

假设第 \(i\) 件商品的质量最高，则要选择该商品，则需要保证前 \(i - 1\) 个商品的质量最大值在前 \(k\) 件商品，所以若该商品被选中的概率为 \(\frac{k}{i - 1}\)，因此，第 \(i\) 件商品被选择的概率为 \(\frac{k}{i - 1}\) ，又由于商品质量分布是均匀的，所有质量最高的商品等可能出现在每一个 \(i\ (1 \leq i \leq n)\)。综上所述，选择到最高质量 \(P_k\) 的商品的概率为： \[ P_k = \sum_{i = k + 1} ^ n \frac{k}{i - 1} \frac{1}{n} \] 当 \(n\) 足够大时，\(\sum_{i = k + 1} ^ n \frac{1}{i - 1}\) 可以近似看作 \(ln(n) - ln(k)\) ，所以有： \[ P_k \approx \frac{k}{n} (ln(n) - ln(k)) \] 对 \(k\) 求导，可得： \[ \frac{\partial P_k}{\partial k} = \frac{ln(\frac{n}{e}) - ln(k)}{n} \] 可知，当 \(k \approx [\frac{n}{e}]\) 时，\(P_k\) 取得最大值。

换言之，当 \(\frac{k}{n}\) 近似等于自然常数 \(\frac{1}{e}\) 的时候 \(P_k\) 取得最大值。事实上，\(\frac{1}{e}\) 在数值上约等于 0.36787944117144233，近似等于 0.37，这也是我们经常说的 37% 法则。

历史

这个问题可以追溯到到上世纪 60 年代，当时美国杂志《科学美国人》提出了几个趣味数学问题，其中之一是秘书问题。假如你需要聘请一个秘书，你依次面试多个候选人，每面试一个人后，你要立刻决定是否聘用她，如果放弃她，她就会去其他公司工作，可能她是最优人选，但是你错过了她，如果录用她，你就不会再面试后面的人选，可能会错过后面更好的人选。那么什么时候停止，才能选到最佳人选呢？
目前已知的第一个提出 37% 法则的是数学家弗拉德。他发现 37% 是最佳选择的一个分割点，当有 N 个候选人时，前 37% 的人面试时，不做决策，找出最优的一位，后面每面试一位，就和前面最优的这位比较，如果劣于她，就面试下一位，如果优于，就选择当前人选，停止面试。

37% 法则在生活中十分常见，它经常出现在各式各样的统计学问题和决策问题上，其描述了一种选择策略上的最优化理论，可以帮我们解决一些日常的决策纠结，37% 法则让我们在面对不确定时，尽可能获取到一个较好的结果。