魔方吧·中文魔方俱乐部

标题: 100囚徒放风问题 [打印本页]

作者: lulijie 时间: 2009-10-30 19:54:48 标题: 100囚徒放风问题

有100个被判无期的囚徒，每天会有一个囚徒被随机地抽出来放风。
有一天国王实行大赦，决定：当100个囚徒都放过风后就全部释放。（从明天开始计算）
那么，平均多少天（期望值）后100个囚徒将重获自由？
要求期望值的精确值。
--------------------------------------------------------------
答案在8楼。
推导过程见10楼。

[ 本帖最后由 lulijie 于 2009-10-31 22:39 编辑 ]

作者: ursace 时间: 2009-10-30 20:01:53 标题: 这是概率

100/100*99/100*98/100*...*1/100

期望也许是这个数的分母？

作者: lulijie 时间: 2009-10-30 20:06:34

可以先利用电脑编个程模拟一下放风过程，知道一下所求值的近似值。

作者: 骰迷 时间: 2009-10-30 21:37:49

我弱弱的問個：兩個囚犯的情況呢。。。那該怎麼計算。。最終會收斂嗎

作者: lulijie 时间: 2009-10-30 21:53:41

4楼的问题很好，可以先考虑2、3、4个囚徒等少数囚徒的情况，以期找到有什么规律。

作者: superacid 时间: 2009-10-30 22:37:31

两个人是3天

作者: tm__xk 时间: 2009-10-30 22:39:00

经计算,a_n=(n+1)/2..

作者: schuma 时间: 2009-10-30 22:47:01

这是coupon collector's problem. 期望的精确值是 n*(1+1/2+1/3+...+1/n)。渐进的表达式是 n*ln(n)

作者: tm__xk 时间: 2009-10-30 22:57:21

我晕....8L正解....

我一个没留神把n/k算成k/n了....

作者: lulijie 时间: 2009-10-31 21:55:56

8楼正确，精确值就是 n*(1+1/2+1/3+...+1/n)
如果某事件在某天发生的概率为p，那么该事件平均1/p天发生一次。
n个囚徒：
●第一天，一个人放过风。
●从第二天开始，出现第二个人放风的概率为(n-1)/n，所以平均过 n/(n-1)天，第二个人会放风。
●第二个人放风后，出现第三个人放风的概率为(n-2)/n，所以平均过 n/(n-2)天，第三个人会放风。
●......
●第n-1个人放风后，出现第n个人放风的概率为1/n，所以平均过 n/1天，最后一个人会放风。
所以所有人都放过风的期望天数=1+n/(n-1)+n/(n-2)+......+n/1
=n*(1+1/2+1/3+......+1/n)

作者: lulijie 时间: 2009-10-31 22:06:06

当n比较大时，近似等于n*(ln(n)+c)    c为欧拉常数，等于0.57721566490......
n=100时，精确计算  100*(1+1/2+1/3+......+1/100)= 518.737751763962
                     近似计算  100*(ln100+0.57721566490)=518.238585......
非常吻合。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)