监狱长给犯人们出的难题

noski

你算的是四个人没有任何约定，每个人都随机的去选的吗？每个人选中的概率是1/2没有异议，那么为什么模拟结果不是1/16呢？
我怀疑是不是计算机中的随机数发生器有规律可循的缘故？

lulijie

对于21楼的质疑，我仔细考虑一下，觉得没理由不是独立事件，得到的概率应该等于1/16。
问题出在哪里?又重新运行多次，得到的概率分别是7.5%、11.2%。波动还挺大的，按理说1千万次的模拟，概率波动不应这么大？真的应该像Noski所说的随机序列生成器出了问题。
每个人随机选号码箱的号码组合，我设计了一个子程序，每运行一下子程序，就随机生成一个号码组合。
这个子程序是，先初始化随机序列生成器(以免每次生成相同的随机数序列)，再运用随机函数，随机生成号码组合。
按理说这个子程序设计应该没问题，但后来证实恰恰是这个子程序出了问题。问题在 初始化随机序列生成器。
因为每个人随机设定他选择的号码组合，都要调用一次那个子程序，而每调用一下子程序，就初始化一次随机序列生成器。
最后造成每个随机数序列都不是完整的，每每被中断。
--------------------------------------------------------------------------
最后删除子程序中的初始化随机序列生成器的语句，将初始化随机序列生成器语句直接放在主程序调用随机函数之前。
重新运行程序，
    1百万次，成功62640次
    1千万次，成功624466次。概率非常接近 1/16=0.625

noski

赞！看来一个程序里只要将随机数生成器初始化一次就够了，这可真是一个隐蔽的BUG。。

lulijie

计算p(4)，但如果这三个人约定好，1选1和2，2选2和3，3选3和4，4选4和1，那么这时P(4)就等于1/12?
---------------------------------
电脑模拟：1百万次，成功83375次，非常接近1/12。
P(4)中最大的概率是不是1/12，还有其他方案更佳么？
推广到P(m),概率最大的方案到底如何呢？    P(m)采用noski定义

lulijie

p(4)，方案：1选1、2，2选1、2，3选3、4，4选3、4，
    模拟1百万次，成功167006次，概率接近于1/6。
所以P(4)的最大值不小于1/6。

小魔豆

每次都恢复原样，和独立操作有什么区别啊。他们商量个屁啊。

noski

这个方法比我那个有效，那么来猜测一下：
m为偶数的时候，约定前一半人选前一半的数字，后一半人选后一半的数字，那么概率：
P(m) = (m/2)! * (m/2)! / m!
验证一下：P(2) = 1/2，P(4)=1/6，P(6) = 1/20 ……

lulijie

p(6)，方案：第1、2、3个人选1、2、3号码，第4、5、6个人选4、5、6号码，
    模拟1百万次，成功50044次，概率接近于1/20。
比其他方案概率好像都大。
----------------------------------------------
所以我的感觉对于P(m)，最佳方案是：将m个箱子随便平分成两组，一半的人都选这一组号码，另一半人都选另一组号码。这样的方案全部成功的概率最大。最大概率等于1/ C(m,m/2) 。        C(m,2/m)是组合数。
这样P(2)=1/C(2,1)=1/2
       P(4)=1/C(4,2)=1/6
      P(6)=1/C(6,3)=1/20
对于楼主的m=100
   最大概率=1/C(100,50)≈1/10^29
---------------------------------------------------
不知我的感觉对不对。

lulijie

哈哈，楼上的观点和我想法一样阿，不知能不能证明。

如来佛猪

不知道能不能改变 箱子的位置..改变了会被 监狱长复原吗?