100囚徒放风问题

lulijie

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

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

lulijie

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

lulijie

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

lulijie

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

当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......
非常吻合。