二选一的成功概率可以高于一半

在最佳约会策略里，我们提到，如果有 100 个女孩可以顺序挑选，那么最好的方法是先看前 37 个，然后在剩下的女孩里选择当时最好的那个女孩，这样有接近 40%的概率挑选到最好的那个女孩。同时，不可能有更好的策略。

American Scientist 于 2009 年出版的一篇文章How to gamble if you must—the mathematics of optimal stopping，里面讨论了一个简单的情景，而且有一个非常违反直觉的答案。在这个简单场景里，你只有两个女孩可以挑选。当你见了第一个女孩后，你只有两种选择，选第一个女孩，或者放弃第一个女孩，这时候你只能选第二个女孩。你能有多大概率选中两个女孩中较好的那一个呢？

直觉上好像没有比总是挑第一个，总是挑第二个，或者随机挑更好的方法，这几个方法成功的概率都是二分之一。但如果好坏的标准可用用分数来体现（即使评分方法和评分范围等一切东西都未知），同时这两个女孩的排序是随机的，那么有一种方法，无论这两个女孩的分值是何种分布，你都有超过一半的概率选中较好的女孩。

方法很简单：生成一个随机数$x$ ，符合标准正态分布。将$x$ 与第一个女孩的分值$p$ 比较。如果$p$ 大于$x$ ，则选择第一个女孩，否则放弃第一个女孩，选择第二个女孩。

这时候，如果两个女孩之间的排序是随机的，那么无论女孩的分值是何种分布，都有超过一半的概率选中较好的那位女孩。

证明：

假设两个女孩的分值分别为$p$ 和$q$ ，满足$p<q$ ，$\text{N}$ 为正态分布的累计分布函数。那么第一个女孩较好时，成功选中第一位女孩的概率为$\text{P}(x<q) = \text{N}(q)$ ；如果第二位女孩较好时，成功选中第二位女孩的概率为$\text{P}(x>p)=1-\text{N}(p)$ 。所以你选中较好的女孩的平均概率为 $(\text{N}(q)+1-\text{N}(p))/2$ ，由于$p<q$ ，所以$\text{N}(p)<\text{N}(q)$ ，所以平均概率大于$\frac12$ 。

有趣的是，这种方法可以保证成功的概率高于 1/2 ，但无法保证高于任何一个大于 1/2 的数。

Q. E. D.