CWYAlpha

Just another WordPress.com site

Thought this was cool: 二选一的成功概率可以高于一半

leave a comment »


博客 » 自然科学 » »

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

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

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

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

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

证明:

假设两个女孩的分值分别为pq,满足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的数。

相关文章


© zhiqiang for 阅微堂, 2012. | 链接 | 14 条评论

from 阅微堂: http://zhiqiang.org/blog/science/how-to-choose-the-better-one-in-two-girls.html

Written by cwyalpha

八月 15, 2012 在 3:29 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: