设万维读者为首页 广告服务 联系我们 关于万维
简体 繁体 手机版
分类广告
版主:红树林
万维读者网 > 五 味 斋 > 帖子
职老:囚徒问题的第三个解释--LUCKY囚徒机制
送交者: 职老 2009年12月20日12:32:06 于 [五 味 斋] 发送悄悄话

我在前两次解释中首先探讨了囚徒问题的数学模型和可行性分析,当然,我们其实是假设这是一个纯数学模型的,也就是说,不考虑囚徒的年龄和健康状况的纯数学模型,所以假设其玄正性存在。

那么,如果我们亲手解决这个问题的关键是什么内?

其实问题的关键有两个。关键A,让囚徒能够向下一位表达自己是第一次放风,还是第N次放风,这里N>=2;

关键B,任何一个囚徒每次放风能知道上面X位囚徒被放过风的次数,也就是说第M次放风的X囚徒能知道M次以内被第一次放风囚徒的数目A,当这个数目A累积到100的时候,他就可以宣布了。当然这个X囚徒本身就是随机的,可能是100个囚徒中的任何一位。

这样,我们就不难看出,这个囚徒问题其实包括了两个不同的分布概率,一个叫做:被抽概率,或者说放风概率;另外一个叫做:信号传递概率,也就是说,囚徒必须想办法知道别的囚徒放风的情况,而且不只知道上一位囚徒的,而且还要知道上S位囚徒的。

这样我们会发现一个难点,第M次放风的囚徒从条件上很难知道他被第M放风前S位囚徒的情况,虽然似乎他们可以开会约定一些所谓的组织分布,但其实很难座到有笑的信号传递,因为他们手里面的可作为信号传第的条件只有那盏灯。而这盏灯似乎首先要做到关键A的作用,然后能部分完成关键B的功能。

所以,如果按照不打破游戏规则的条件,囚徒只能遵循一种叫做:LUCKY囚徒的机制完成这项任务。

1)灯是关键A的主要功能。囚徒必须假设灯开为第一次放风,灯关为第N次放风,N>=2。

具体操作如下:囚徒只要是第一次放风,如果看到灯开着,就维持该灯开着;如果看到灯关着,就开灯。

如果囚徒是第N次放风,就保持关着或者把开着的关上。

这样灯本身就只传递唯一一个信息:前面一位是第一次或者第N次。

2)每位囚徒在牢房里面建立一个记录系统,比如用指甲在钢墙上划道道,记录每次被第N次放风后,看到灯开着--前面一位肯定是第一次被放风的。当这个记录数目n(包括该囚徒自己第一次被放风的)=100的时候,就宣布可以了。当然,任何一个囚徒都可以宣布,只要他墙上的n=100的时候,别人的墙上的可能是1-99任何一个数目。

这样我们看到,国王的游戏规则,不但提供了放风机会,而且提供了所谓的信号传递机会,也就是说第N次被抽到提供了一种传递记录前面被第一次抽风的机会,当然,N=2是最佳的结果。

这样,囚徒们就存在两个相关却独自存在的分布:

1)被抽放风分布,简称:抽风分布,这个机率是不变的,第一次和第N次都是一样,为1/100

2)传递分布,这个机率是改变的,可以是100%,也可以是零蛋。

那么,让我来首先先简单的分析一下前10轮被抽和囚徒记录的结果吧(只分析部分)

(1)10个囚徒都被第一次抽中,这个分布可以说是最佳被抽分布,但同时也是最差传递分布之一,因为囚徒只知道自己被抽和上一个被抽的情况,墙上最多记录2道(第一个囚徒一道)

(2)一个囚徒被抽10次,这个分布可以说是最差被抽和被分布情况;

(3)10个囚徒中有个最LUCKY的家伙,他被第2,4,6,8,10反复被抽放风5次,这样,他就可以记录6个道道了。这个是最佳的抽风和传递分布

(4)其他的情况介于这些分布之间

 

这样我们看来,如果囚徒按照一般的规律进行,当某个囚徒发现自己墙上的道道是100而宣布游戏结束的时候,其它的囚徒应该是1-99的正态分布,也就是大约一共记录了5500次的第一次被抽。如果按照10%幸运程度计算的话,总体被抽次数就是这个数目的10倍,大约55000天,也就是150年以上;如果按照5%可信度计算,就是110000天,也就是300年。

 

当然,如果存在一个LUCKY的囚徒,也就是这个囚徒被反复的交叉被抽中,比如刚才说的2,4,6,8,10,12,。。。。。,大约201天,他的墙上就是100个道道了,这样大家就粗去了,嘿嘿。

这个机制就叫做:LUCKY囚徒机制。

 

所以,按照抽风机率和传递机率以外的第三个总体分布而言,囚徒的被放出的机率可能是201天到大约300年,估计是T分布,嘿嘿。

其实,按照不破坏游戏规则和不让国王怀疑的前蹄下,可以内定一个LUCKY囚徒,让他画累积的道道,其它的囚徒画道道记录开始后的天数。单数1,3,5,7。。。的时候,抽到自己自己就粗去,双数天的时候,被抽到就对监狱长说:俺不想粗去,让LUCKY囚徒出去(比如说他身体不好,需要爱心什么什么的,嘿嘿),这样,虽然不能201天就粗去(因为非LUCKY囚徒有可能被N次抽到)。

当然,也可以把100个囚徒分成10组,每组构建一个LUCKY囚徒,以防止国王生气,但必须规定好每组只负责10天,轮流交替,当其中一组LUCKY囚徒墙上的道道为100的时候,宣布解放,嘿嘿。当然,冒险的话也可以是N=30左右的时候就宣布,嘿嘿。

这样的办法肯定更有笑,但如何找到最佳的分组和负责天数,下次再谈。

 

0%(0)
标 题 (必选项):
内 容 (选填项):
实用资讯
回国机票$360起 | 商务舱省$200 | 全球最佳航空公司出炉:海航获五星
海外华人福利!在线看陈建斌《三叉戟》热血归回 豪情筑梦 高清免费看 无地区限制