算法导论中一个蒙提霍尔问题

亦称为蒙特霍问题或三门问题
服务器君一共花费了226.557 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

《算法导论》第二版的附录C.2概率有这么一道习题:

一个监狱看守从三个罪犯中随机选择一个予以释放,其他两个将被处死。警卫知道哪个人是否会被释放,但是不允许给罪犯任何关于其状态的信息。让我们分别称罪犯为X,Y,Z。罪犯X私下问警卫Y或Z哪个会被处死,因为他已经知道他们中至少一个人会死,警卫不能透露任何关于他本人状态的信息。警卫告诉X,Y将被处死。X感到很高兴,因为他认为他或者Z将被释放,这意味着他被释放的概率是1/2。他正确吗?或者他的机会仍是1/3?请解释。

由于书出这道题的一节讲到了概率、条件概率和贝叶斯定理。所以我当时是这么解题的:

记事件A为:X被释放;事件B为:Y被处死。

在假定X被释放的情况下,Y被处死的条件概率是P(B|A)=1。

那么根据贝叶斯定理,在已知Y被处死的前提下,X被释放的条件概率就是

P(A|B) = P(A) * P(B|A) / P(B) = (1/3) * 1 / (2/3) = 1/2。         (1)式

直观的想,在知道了Y会死后,X与Z各有一半被释放的机会,答案似乎也应该是1/2的。 但如果换一个角度考虑:Y或者Z一定有一个会死,不管警卫告诉X是哪一个,都不会改变X会不会被释放的结果,因而X被释放的概率都是一样的,都是1/3。

当时感觉这道题有点纠结了,觉得1/3好像是对的,但1/2又是我用公式算出来的。后来由于找不到答案,我也就不了了之(网上找到的《算法导论》答案没有附录这部分的,有知道的朋友给个链接^_^)。今天碰巧在网上看到了一个讲它的帖子,才知道这道题还挺有来头的。这个问题叫蒙提霍尔问题,又叫三门问题,据说是个"悖论",还迷惑了很多人。不过原题改头换面了一下,换成了电视节目抽汽车中奖的背景。有兴趣的朋友可以看看。

按照网上的说法,问题的答案确实是1/3。我仔细想了想,觉得应该这么分析:

样本空间本身有三个基本事件:

E1:X被释放,Y死,  Z死;

E2:X死,  Y被释放,Z死;

E3:X死,  Y死,  Z被释放。

问题出在警卫身上,X问警卫的是哪一个会死,而无论是哪种基本事件,警卫总能告诉X一个会死的人。所以用概率算应该这么去算:

记事件A'为:X被释放;事件B'为:Y和Z中某人会死。求的是,在警卫告诉给X,YZ两者中某人会死的情况下,X会被释放的条件概率

P(A'|B')=P(A') * P(B'|A') / P(B') = 1/3 * 1 / 1 = 1/3.      (2)式

很多人(包括我)之所以得出(1)式的答案,是因为没分析清问题。如果题目改成:X问警卫,Y是被释放还是被处死,而警卫回答他Y会被处死,那么答案就是(1)式的1/2 了。(注意体会与问出YZ两者中会死的一个的区别)。

网上改头换面的三门问题答案的关键也在主持人身上,如果他都知道三扇门门后是什么,总是别有用心的选择背后是羊的一扇门打开给抽奖者看,那么抽奖者就该选择换门;如果主持人只是随意的打开一扇门,而门背后正好是羊,那么抽奖者可以不换。

思考这个问题得到的体会:

  • 数学是个解决现实问题的好工具;如果用语言表达或者逻辑思考解决不好一个问题、甚至引起喋喋不休的争论,不防用数学做工具解决。
  • 用数学解决问题的关键在于建立正确的模型。比如我一开始想当然的得出(1)式的答案,是因为没分析清问题的本质,没有建立正确的模型。

本文地址:http://www.nowamagic.net/librarys/veda/detail/781,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/781

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《重来:更为简单有效的商业思维》 贾森•弗里德(Jason Fried) (作者), 大卫•汉森(David Heinemeier Hansson) (作者), Mike Rohde (插图作者), 李瑜偲 (译者)

这本书呈现的是一种更好、更简单的经商成功之道。读完这本书,你就会明白为什么计划实际上百害而无一益,为什么你不需要外界投资人,为什么将竞争视而不见反倒会发展得更好。事实是你所需要的比你想象的少得多。你不必成为工作狂,你不必大量招兵买马,你不必把时间浪费在案头工作和会议上,你甚至不必拥有一间办公室。所有这些都仅仅是借口!

更多计算机宝库...