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

作者: , 共 3334 字 , 共阅读 0
系列:数学之美

查看该系列所有文章

本文将证明:最佳约会策略里提到策略,忽略前 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 ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
类似文章:
相似度: 0.172
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。
相似度: 0.108
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
移动平均$ \text{ema}(x,n)$ 是指按照如下方法计算指标
利用线性代数可以给某些问题很精妙的证明,Matrix67 就给出了一个这样的例子,这也让我想起以前看见的另外一个例子,分享如下:
最佳约会策略里,我们提到,如果有 100 个女孩可以顺序挑选,那么最好的方法是先看前 37 个,然后在剩下的女孩里选择当时最好的那个女孩,这样有接近 40%的概率挑选到最好的那个女孩。同时,不可能有更好的策略
相似度: 0.095
CAPM 公式是指一个组合的预期收益率可以用它的不可分散风险大小所刻画,在数学上,它可以表示为一个组合$ p$ 的收益率$ r_p$ 的表达式:
相似度: 0.089
首先申明一下,赌博是不对的,下面的讨论也更多是理论性的。
最近看了几个风险管理和组合管理系统,有几个系统里附带了组合优化模块,也了解到这一方面工业界的最新成果。最新的组合优化模块被称为第二代最优化模型,主要成果就是二阶锥优化算法的应用,其中一个重要的改进为对 alpha 估计的不准确性考虑在内。
相似度: 0.085
最近看到一个有趣的问题:
相似度: 0.080
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
数学 » 数据分析, 统计
假设某一天,某媒体发布一条消息,说清华大学研究生新生录取的面试过程中,每个系的女性报考者的通过率都要比男性报考者的通过率要低,然后攻击清华大学的新生录取歧视女性。你对这件事情有何看法?
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」(也就是 pass ,不作猜测的意思)。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。