二选一的成功概率可以高于一半

作者: , 共 1000 字
系列:生活中的数学

查看该系列所有文章

最佳约会策略里,我们提到,如果有 100 个女孩可以顺序挑选,那么最好的方法是先看前 37 个,然后在剩下的女孩里选择当时最好的那个女孩,这样有接近 40%的概率挑选到最好的那个女孩。同时,不可能有更好的策略

American Scientist 于 2009 年出版的一篇文章How to gamble if you must—the mathematics of optimal stopping,里面讨论了一个简单的情景,而且有一个非常违反直觉的答案。在这个简单场景里,你只有两个女孩可以挑选。当你见了第一个女孩后,你只有两种选择,选第一个女孩,或者放弃第一个女孩,这时候你只能选第二个女孩。你能有多大概率选中两个女孩中较好的那一个呢?

直觉上好像没有比总是挑第一个,总是挑第二个,或者随机挑更好的方法,这几个方法成功的概率都是二分之一。但如果好坏的标准可用用分数来体现(即使评分方法和评分范围等一切东西都未知),同时这两个女孩的排序是随机的,那么有一种方法,无论这两个女孩的分值是何种分布,你都有超过一半的概率选中较好的女孩。

方法很简单:生成一个随机数\( x\) ,符合标准正态分布。将\( x\) 与第一个女孩的分值\( p\) 比较。如果\( p\) 大于\( x\) ,则选择第一个女孩,否则放弃第一个女孩,选择第二个女孩。

这时候,如果两个女孩之间的排序是随机的,那么无论女孩的分值是何种分布,都有超过一半的概率选中较好的那位女孩。

证明:

假设两个女孩的分值分别为\( p\)\( q\) ,满足\( p<q\)\( \text{N}\) 为正态分布的累计分布函数。那么第一个女孩较好时,成功选中第一位女孩的概率为\( \text{P}(x<q) = \text{N}(q)\) ;如果第二位女孩较好时,成功选中第二位女孩的概率为\( \text{P}(x>p)=1-\text{N}(p)\) 。所以你选中较好的女孩的平均概率为 \( (\text{N}(q)+1-\text{N}(p))/2\) ,由于\( p<q\) ,所以\( \text{N}(p)<\text{N}(q)\) ,所以平均概率大于\( \frac12\)

有趣的是,这种方法可以保证成功的概率高于 1/2 ,但无法保证高于任何一个大于 1/2 的数。

Q. E. D.

系列: 生活中的数学 »
网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问题太快放到网上。
类似文章:
相似度: 0.142
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。
相似度: 0.096
写篇三门问题的终结版。欢迎补充材料。
相似度: 0.092
最近看到一个有趣的问题:
数学 » 数学游戏, 概率
蚁迹寻踪及其他数学探索》提到一个游戏:
本文将证明:最佳约会策略里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过\( \frac{u}{n}\sum_{i=u}^{n-1}\frac1i\) ,其中\( u\) 为满足\( \sum_{i=u}^{n-1}\frac1i\geq 1\) 的最大值。这个\( u\) 大约为 37%,最后成功的概率大约为 40%。
相似度: 0.080
首先申明一下,赌博是不对的,下面的讨论也更多是理论性的。
在 slashdot 上看到一篇科技新闻,两个数学家(其中一个来自于 MIT )和一个计算机学家,在 arXiv 上发表了一篇论文《HOW TO GAMBLE IF YOU』RE IN A HURRY》(PDF 版链接),是最近几天很热门的一条新闻。
以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的overhang 堆积木 - 能伸出桌面多远?。今天这次课,来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
数学 » 赌博
何时适合而止中,我们提到一个有趣的硬币问题,抛一个硬币,选择合适的时点,使得正面数与总次数的比值最大。这个问题目前还没有被完全解决,之前我们也只是用模拟法逼近了一下结果
风险管理 » VaR Primer
一个场景是所有风险因子的表现序列。历史场景是指风险因子在历史上某天的实际表现,随机场景则是计算机随机模拟生成的。通常蒙特卡洛模拟法需生成至少 1000 个随机场景,然后计算组合在每个场景下的损益,最后取 5%分位点得到组合的 VaR 值。
编程 » Excel
此篇为学习笔记。
数学 » 赌博
何时适合而止中,我们提到一个有趣的硬币问题,抛一个硬币,选择合适的时点,使得正面数与总次数的比值最大。这个问题目前还没有被完全解决,之前我们也只是用模拟法逼近了一下结果