100囚徒集徽章
有一天，国王决定实行大赦，给100个囚徒每人发了一个徽章。这100个囚徒关在独立的房间里，每天随机有2个囚徒可以同时放风，放风时，这两个囚徒可以相互交换徽章，放风结束后，2个囚徒将回到自己的房间，留在放风场所里的东西将被清空。若某囚徒集齐了所有的100个徽章，大家将被释放。问什么策略下，囚徒被释放的天数期望值最小，其精确的期望值T(100)为多少？ 我的策略：放风时，手中徽章少的囚徒将自己的所有徽章都交给对方，徽章一样多的，随便选一个囚徒将他的所有徽章都交给对方。
用电脑模拟100囚徒放风过程，模拟10000次后，平均天数为9748.4804.
根据以上策略，若囚徒总人数n为2，那么第1天放风，将集齐所有的徽章，所以期望值T(2)=1. 正解应该是$(1+...+99)*(2-1/100)=4950\times 1.99=9850.5$。
能否多模拟几下，看看误差是否会变小？
#####
你是对的，应该是$(1+...+99)*(2-2/100)=4950\times 1.98=9801$。 我觉得T（n）=(n-1)^2
T(100)=99^2=9801 本帖最后由 gogdizzy 于 2013-6-24 11:03 编辑
按照楼主给的策略：
第一次合并期望$\binom{100}{2} / \binom{100}{2}$
第二次合并期望$\binom{100}{2} / \binom{99}{2}$
...
第99次合并期望$\binom{100}{2} / \binom{2}{2}$
加起来得( 100 * 99 ) * ( 1/99 - 1/100 + 1/98 - 1/99 + ... + 1/1 - 1/2 ) = ( 100 * 99 ) * ( 1 - 1/100 ) = 9801
所以楼主的公式是对的。
页:
[1]