37% 原则约会策略的最优性证明

本文将证明：最佳约会策略里提到策略，忽略前 37%的对象，然后在剩下的对象里挑第一个比前 37%都好的对象，这个策略是最优的。更准确地，我们将证明：任何约会策略的成功概率都不可能超过un∑n−1i=u1i ，其中u 为满足∑n−1i=u1i≥1 的最大值。这个u 大约为 37%，最后成功的概率大约为 40%。

首先定义一些符号，Πn 表示{1,2,⋯,n} 的排列的集合。

我们可以定义排列之间的半有序关系。对于任何两个排列α∈Πa 和β∈Πb ，如果a≤b 并且α 的大小顺序和β 的 前a 项一样(即对任意1≤i,j≤a 都有αi<αj⇔βi<βj )，我们则认为α≤β ，我们也可以用另外一种说法，满足这样的条件的α 被认为是β 的子排列。

对任意α∈Πn ，令

下面开始证明。

随机策略是确定性策略的随机组合，所以任何一个随机策略的胜率都不会超过其中最好的确定性策略的胜率。所以我们只需要对确定性策略证明上述胜率上界。

而首先，我们需要对一个约会策略建模。任何一个策略面对一个约会对象的序列，这个序列可视作一个排列组合。策略一项一项检验这个排列组合，并且决定在什么时候停止。假设这个策略在检查α 时停止在第k 项，那么该策略只知道α 的前k 项的相对顺序，也就是Fk(α) ，便决定停止。令Sk∈Πk 为所有这样的Fk(α) ，并令sk=|Sk| 。我们也称S=S1∪S2∪⋯∪Sn 为策略的停止集。

显然，对于任意α∈Sk , 都有n!k! 个排列比它大。这其中，有(n−1)!(k−1)! 个排列被策略成功找出最大值(即第k 项为n )。所以策略在第k 项停止并成功的概率为：

从上面概率等式看，一个策略的停止集越大越好。现在我们需要指明一个事实，这是证明我们结论的关键。一个策略的停止集S 并不能无限制的大，它必须满足其中的任意一个排列都不能是另外一个排列的字串，即对任意i<j ,α∈Si 且β∈Sj , α 不能是β 的子排列。

如果同为停止集元素的排列α 是另一个停止集元素β 的子排列，那么当策略在遇到β 时，策略将直接停止在第i 个元素，不会等到第j 个元素才停止，从而β 不可能也是停止集合的成员。

从上面的事实，我们计算{1,2,⋯,i} 的最后一位为i 的排列个数。任何一个属于Sj 的排列都可以扩充为(i−1)!j! 个这样的排列，并且所有这些这样扩充后的排列都互不相同。因此：

令ti=si/i! ，上式转化为对任意i

令u 为满足∑n−1i=u1i≥1 的最大值，以下有：

等号成立时必须有∀i≤u 都有ti=0 ，亦即策略需忽略前u 项，并且∀i>u 有∑i−1j=1tj+iti=1 ，递推可知最佳约会策略是唯一的最优的策略。

Q. E. D.