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

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

首先定义一些符号，$\Pi_n$ 表示$\{1,2,\cdots, n\}$ 的排列的集合。

我们可以定义排列之间的半有序关系。对于任何两个排列$\alpha\in \Pi_a$ 和$\beta\in \Pi_b$ ，如果$a\leq b$ 并且$\alpha$ 的大小顺序和$\beta$ 的 前$a$ 项一样(即对任意$1\leq i,j\leq a$ 都有$\alpha_i < \alpha_j \Leftrightarrow \beta_i < \beta_j$ )，我们则认为$\alpha \leq \beta$ ，我们也可以用另外一种说法，满足这样的条件的$\alpha$ 被认为是$\beta$ 的子排列。

对任意$\alpha\in\Pi_n$ ，令

下面开始证明。

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

而首先，我们需要对一个约会策略建模。任何一个策略面对一个约会对象的序列，这个序列可视作一个排列组合。策略一项一项检验这个排列组合，并且决定在什么时候停止。假设这个策略在检查$\alpha$ 时停止在第$k$ 项，那么该策略只知道$\alpha$ 的前$k$ 项的相对顺序，也就是$F_k(\alpha)$ ，便决定停止。令$S_k\in\Pi_k$ 为所有这样的$F_k(\alpha)$ ，并令$s_k=|S_k|$ 。我们也称$S=S_1\cup S_2 \cup \cdots \cup S_n$ 为策略的停止集。

显然，对于任意$\alpha\in S_k$ , 都有$\frac{n!}{k!}$ 个排列比它大。这其中，有$\frac{(n-1)!}{(k-1)!}$ 个排列被策略成功找出最大值(即第$k$ 项为$n$ )。所以策略在第$k$ 项停止并成功的概率为：

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

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

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

令$t_i=s_i/i!$ ，上式转化为对任意$i$

令$u$ 为满足$\sum_{i=u}^{n-1}\frac1i\geq 1$ 的最大值，以下有：

等号成立时必须有$\forall i\leq u$ 都有$t_i=0$ ，亦即策略需忽略前$u$ 项，并且$\forall i>u$ 有$\sum_{j=1}^{i-1}t_j+it_i=1$ ，递推可知最佳约会策略是唯一的最优的策略。

Q. E. D.