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\) 的前a项的大小顺序和 \(\beta\) 一样(即对任意 \(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.


上一篇:最佳约会策略2007年3月10日
题外话:最近阅微堂发的都是网友转发的政治方面的文章,不爱看的人会比较痛苦。现在讨论一个轻松一点的话题。其问题,已经被研究了很多年,有

下一篇:帽子游戏一2007年6月19日
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。