100囚徒放风问题

lulijie

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

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

ursace

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

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

lulijie

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

骰迷

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

lulijie

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

superacid

两个人是3天

tm__xk

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

schuma

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

tm__xk

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

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

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)