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\) ,令

$$F_k(\alpha)=\beta\in \Pi_k\ \ \ \ \ \ \text{s. t.} \ \ \ \ \ \beta \leq \alpha$$

下面开始证明。

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

而首先,我们需要对一个约会策略建模。任何一个策略面对一个约会对象的序列,这个序列可视作一个排列组合。策略一项一项检验这个排列组合,并且决定在什么时候停止。假设这个策略在检查 \( \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\) 项停止并成功的概率为:

$$P=\frac{1}{n!}\sum_k\frac{(n-1)!}{(k-1)!}\cdot s_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!}\) 个这样的排列,并且所有这些这样扩充后的排列都互不相同。因此:

$$\sum_{j=1}^{j-1}s_j\frac{(i-1)!}{j!} + s_i\leq (i-1)!$$

\( t_i=s_i/i!\) ,上式转化为对任意 \( i\)

$$\sum_{j=1}^{i-1}t_j+it_i\leq 1$$

\( u\) 为满足 \( \sum_{i=u}^{n-1}\frac1i\geq 1\) 的最大值,以下有:

$$\begin{array}{rcl}P&=&\frac1n\sum\limits_{k=1}^n kt_k\\&=&\frac1n\sum\limits_{i=1}^n(\sum\limits_{j=1}^{i-1}t_j+it_i)(1-\sum\limits_{j=i}^{n-1}\frac1j)\\&\leq&\frac1n\sum\limits_{i=u+1}^n(1-\sum\limits_{j=i}^{n-1}\frac1j)\\&=&\frac{u}{n}\sum\limits_{i=u}^{n-1}\frac1i\end{array}$$

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

Q. E. D.

系列: 数学之美 »
数学 » 搞笑, 数学之美
来自 University of WarwickMike Paterson 星期二在 Yao 的理论计算机课堂上给了一个非常有趣的小讲座。
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」(也就是 pass ,不作猜测的意思)。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
数学 » 数据分析, 统计
假设 某一天,某媒体发布一条消息,说清华大学研究生新生录取的面试过程中,每个系的女性报考者的通过率都要比男性报考者的通过率要低,然后攻击清华大学的新生录取歧视女性。你对这件事情有何看法?
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」(也就是 pass ,不作猜测的意思)。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。