|||
假如有n个美女逐个介绍与你约会,每个见面时,如果你选了她就没机会见到后面可能更好的;如果让她走了,也许后面都不如她,追悔莫及也无法挽回。问怎么选结果最好?
在生活中也有类似的情况。比如说相亲谈朋友,选项目,货比三家购物,或者有几个工作的机会。现实的情况都不容你脚踩几条船来比较,只能是一个个的来,错过就不好回头了。这都和上面的例子面临着相同的问题。这问题看起来漫无头绪,对于任何一种策略,都可以举出一个具体的出场顺序,使得你得到最差的后果。
实践中人们多是这样做的:直接选第一个那叫盲目没有比较,除了一见钟情的外,总得看过k个才甘心,待到后面候选人不多时就急了,只要比前面都见过的好,就是她了,要是全不满意到了最后一个,好坏都是她了。机会和美女都是随机出现的,那就问你到底要Pass几个炮灰才开始认真比较?这是n个随机序列中求k值,使得选到美女数学期望最高的问题。这个期望是按照这方法选到美女满意程度的数学期望值。
这个问题我考虑过,虽然思路不难,但随着n的数目增加,计算的复杂性增加的很快。前几天在科学网上看到“谈恋爱的技巧也能用数学模型表达?兼谈管理科学研究”博文里面转载了一个数学计算,其思路让我赞叹,虽然他把问题简化成选中最好那一个的概率问题,而不是得到最高的期望值问题。但他的结果是十分简洁的通解,计算的结果和我计算的几个情况也吻合。这是个很漂亮的结果也很有应用价值,可惜博文没有给出原文的出处。珠玉在前,我本不想再现丑了,就在那博文后跟了几句赞词并替他解答。后来有网友来追问,又见许多跟帖对那研究的意义颇有微词,我想还是写个帖子解释一下。
那博文中转载那篇文章的思路和表达都十分简洁,后面的两个结论都显示出作者灵活应用数学的功力。我对此十分赞赏。跟贴中对那文章的批评多集中在复杂现实中的适用性问题。那是另一方面的诉求。
读论文和好文章,我更倾向于理解和欣赏作者的巧思而不是挑剔戏剧性说法的疵瑕。其实借用一些理想情况夸张性的应用在阐述理论的论文并不少见。2012年诺贝尔经济奖的核心Gale-Shapley算法,就是以稳定婚姻设计的求偶规则为题的【1】。现实中的婚姻要比算法的假设条件复杂得多,所以难以应用。科技工作者对抽象数学模型的局限和应用都有常识,所以用不着将注意力集中在这方面而忽略了对核心思想的欣赏。
在这里我先替那作者解答一下跟帖对式子中的k/(i-1)/n项的疑问。作者假定在这n个人中有一个最佳的人选A,随机时A在任何一个位置的概率都是1/n,自然A出现在第i个位置的概率也是这个数。为了保证A有机会被选上,前面i-1个人中最好的那个B必须在前k个人中,不然B入选了就轮不到A了,这个情况的概率是k/(i-1)。把这两者概率综合起来,就是从第k+1个开始比较,刚好在第i个时选中A的概率k/(i-1)/n。P(k)是把所有可能i的概率都加起来。得出n充分大时的P(k)逼近公式,再求导得到k的通解。整个思路和推导十分漂亮。
那个数学模型是针对选中这n个人中A的最大概率问题。更靠近现实的提法是看过前面k个以后,被选中的人不一定是A但是美女的期望值E(k)最高。这个问题复杂点,我想用比较简单的4个美女的例子来直观地说明思路。
将这4个美女从1到4打分,四位1,2,3,4分的美女按随机顺序出场,闭着眼睛选一个,平均是2.5分。你的期望是在2,3分美女之间。E(0)=2.5.
如果Pass第一个,后面出场的再和她比较,更好的就是她,否则等下一个,第一个出来的有四种情况:
她是1分美女,后面哪个出来都比她强,自然第二位出来就迷倒了,这第二位2,3,4都有可能,平均是3分;
她是2分美女,后面3,4分的出来比她强,谁先到就是谁,3,4平均是3.5分;
她是3分美女,后面还有个4分美女,跑不了4分;
她是4分美女,这再往后看的都失望,只能是最后一个了。1,2,3都有可能,平均2分。
这四种情况机会都是一样的,所以把这四种平均得分再平均,总的期望是(3+3.5+4+2)/4=3.1。这美女指数比盲选高了一点,可以期望3分美女强一点。E(1)=3.1.
再看Pass两个又如何,Pass的是1分和2分,记为(1,2),后面剩下3分和4分,记为【3,4】,这一共有6种情况:
(1,2)【3,4】,同上面的道理分析,平均等分3.5;
(1,3)【2,4】,会等到4;
(2,3)【1,4】,会等到4;
(1,4)【2,3】,捡了最后一个,平均为2.5;
(2,4)【1,3】,捡了最后一个,平均为2;
(3,4)【1,2】,捡了最后一个,平均为1.5;
这六种情况机会均等,总的期望是(3.5+4+4+2.5+2+1.5)/6=2.9,比盲选的强,比Pass第一个的差。E(2)=2.9.
Pass 3个剩下只有一个,这和盲选一个样,2.5。E(3)=2.5.
综合这几种情况E(1)=3.1最大。所以在只有四位美女情况,拿第一个当炮灰只欣赏不点头,从第二个开始认真比较最明智,可以期望3.1分的美人,比平均分2.5高。可以看出总数多时,先Pass的人数也可以多一点,这期望美女指数E(k)随着炮灰人数k先增加,然后再减少。
n位美女可以用相同的思路,用排列组合计算数学期望值可以得出一般的式子E(k)。这个一般公式约减的工作量会大一点。因为珠玉在前,我没有动力去完成最优k值的计算公式。但是应该不难用计算机逐个k计算E(k)后比较来取得。
我在纸上算出n为2、3、4时,最优的k分别是0、1、1。这个结果和求最大概率问题的通解[n/e]计算的数值是一样的。。虽然求最大概率和求最大数学期望不是同一个问题,而且后者还和赋值有关。但是前者是一个很好的简化模型有着很漂亮的结果。
结论:对于n个依次来临的机会,首先了解一下[n/e]个,然后将后面遇到的与前面所有见到的相比,如果更好就接受,否则等下一个,这是对待这类问题的最佳策略。这里e=2.71828…,[n/e]是n/e的整数部分。
对于现实中经常遇到的相亲、求职、选项目和逛商店买东西,这类选项不多于28个的序列选择,我们有了比凭经验更为理性的指导:对前面的1/3只作了解不做选择,在这之后每一次机会都和前面的相比较,如果更好就选择了她,否则等下一个。
对于细心读过上面选择四个美女思路掌握其道理的人,不难根据自己问题的特殊性对这计算出来的k值略加增减。
【参考文献】
【1】 D. Gale and L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962 http://www.econ.ucsb.edu/~tedb/Courses/Ec100C/galeshapley.pdf
【2】 谈恋爱的技巧也能用数学模型表达?兼谈管理科学研究
http://blog.sciencenet.cn/home.php?mod=space&uid=200071&do=blog&id=643493#quickcommentform_643493
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 07:31
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社