【RMC】满足泊松分布的随机数生成器及其分析
大家好，我是流火智。由于一些历史原因，我一直对随机数生成器这种东西念念不忘，今天算是突发奇想的去做了两个同类的随机数生成器，同时做了这类生成器的一些分析，就发到了这里来。
这类生成器的原理很简单，一句话概括的话，就是用竹子的随机生长来产生随机数。
红石部分的内容就不多介绍了，结构比较简单，红石灯所在的位置是输出端，不需要外部输入。第一个生成器是单片的，可以通过简单的复制来扩展，第二个生成器是比较紧凑的，也可以通过简单的复制来扩展，游戏版本是1.16.4。剩下直接看截图就能差不多看明白，当然存档也在本文末尾提供了。
这个东西比较有意思的部分主要是体现在游戏原理与数学理论上，本文剩下的内容也是对这部分进行分析。
红石部分的内容就不多介绍了，结构比较简单，红石灯所在的位置是输出端，不需要外部输入。第一个生成器是单片的，可以通过简单的复制来扩展，第二个生成器是比较紧凑的，也可以通过简单的复制来扩展，游戏版本是1.16.4。剩下直接看截图就能差不多看明白，当然存档也在本文末尾提供了。
这个东西比较有意思的部分主要是体现在游戏原理与数学理论上，本文剩下的内容也是对这部分进行分析。
首先，这类随机数生成器是伪随机，本质上是把mc的代码中的随机数“提取”出来，由于mc程序内部的随机数应该是伪随机（至少我这么相信），所以这个生成器提取的随机数也是伪随机。不过由于现代计算机技术的成熟，基于实践目的的话，伪随机数和真正的随机数的差别可以忽略不记，所以这类生成器产生的随机数是一个相当好的随机。
这个生成器的原理如下：mc在每个游戏刻会对临近的区块执行区块刻，每个受到区块刻的区别会随机选定三个方块执行随机刻，而竹子（以及甘蔗，仙人掌等）如果收到了随机刻，就会尝试生长（引自：https://minecraft-zh.gamepedia.com/%E5%88%BB）。因此竹子会反应mc程序中提供的随机性，同时竹子是mc中生长最快的植物，平均每204.8秒就会生长一次（引自：https://minecraft-zh.gamepedia.com/%E7%AB%B9%E5%AD%90），所以竹子是一个相当好的快速产生随机数的植物。
这个生成器的原理如下：mc在每个游戏刻会对临近的区块执行区块刻，每个受到区块刻的区别会随机选定三个方块执行随机刻，而竹子（以及甘蔗，仙人掌等）如果收到了随机刻，就会尝试生长（引自：https://minecraft-zh.gamepedia.com/%E5%88%BB）。因此竹子会反应mc程序中提供的随机性，同时竹子是mc中生长最快的植物，平均每204.8秒就会生长一次（引自：https://minecraft-zh.gamepedia.com/%E7%AB%B9%E5%AD%90），所以竹子是一个相当好的快速产生随机数的植物。
根据以上原理不难看出，在每一个游戏刻，单个竹子被选定的概率相当低，但是游戏刻十分短暂，只有0.05秒（引自：https://minecraft-zh.gamepedia.com/%E5%88%BB），因此在一段合理的时间内（比如200秒），游戏刻的总数相当的多，因此在一个合理的时间内，竹子的生长次数是一个正常的数（比如一次），这种概率分布属于泊松分布。给定一个固定的时间间隔T，这类分布的概率密度函数为：f(x)=[(u^x)*e^(-u)]/(x!) （其中自变量x是代表成长次数的自然数，u是数学期望（mean），e是自然对数，！是阶乘）。（注1：概率密度函数大概可以理解为不同成长次数的可能性）（注2：数学期望可以理解为每段时间中竹子平均生长了多少次）
泊松分布作为二项式分布的极限，其期望满足关系： u=mp （m是尝试次数，p是成功率）。如果在一个游戏刻内一个竹子生长的成功率是m，那么两个竹子中有一个生长的成功率为：2m-m^2，由于m非常小，m^2可以忽略不计，因此两个竹子中有一个生长的成功率约为：2m
以上讨论可以很容易的推广到任意整数个竹子的情况，可以看出，对n个竹子，其期望u’和单个竹子的期望u满足关系：u’=n*u，然后取极限来推广到泊松分布的情况，可以得出同样的u’=n*u关系。
以上讨论可以很容易的推广到任意整数个竹子的情况，可以看出，对n个竹子，其期望u’和单个竹子的期望u满足关系：u’=n*u，然后取极限来推广到泊松分布的情况，可以得出同样的u’=n*u关系。
对于单个竹子在T时间内的概率密度来说，很明显期望u满足关系：u=rT（r代表生长速率，即生长数/时间）。根据前文提到的wiki上的数据，成长率约为：1/205 （次/s）（引自：https://minecraft-zh.gamepedia.com/%E7%AB%B9%E5%AD%90），可以得出单个竹子在一秒内的期望是0.00488。由于实践上红石器件运行速度有限，2秒的期望0.009756会更加符合实践需要，所以后文的时间间隔T被设定为2秒。（到任意时间的推广是直接的）
根据关系：u’=n*u，对于100个竹子，在2秒内的期望为0.9756，红石实践上这0.03的误差往往并不显著，因此取整为1，同时在泊松分布下，标准差和期望满足关系：σ=u^0.5，可得标准差σ为1。（注3：标准差大概可以理解为实际产生的随机数和理论上的数学期望的平均差距）即100个竹子组成的随机数生成器，对两秒的时间间隔来说，可以产生期望和标准差为1的符合泊松分布的随机数。
下图是期望为1的泊松分布的概率密度函数和累积分布函数的图像：（注4：累积分布函数在这个竹子问题里可以理解为有多少可能性竹子的成长次数落在了从0到自变量所代表的值的范围内）
下图是期望为1的泊松分布的概率密度函数和累积分布函数的图像：（注4：累积分布函数在这个竹子问题里可以理解为有多少可能性竹子的成长次数落在了从0到自变量所代表的值的范围内）
前文提到的第二个生成器（紧凑的生成器）便满足竹子数为100这个条件，因此上文中针对100个竹子的讨论适用于这个生成器。
对于上述讨论的推广是显然的，即对于包含n个竹子的随机数生成器，其概率密度函数为：f(x)=[(u^x)*e^(-u)]/(x!) ，其中期望u=n*r*T，标准差σ=u^0.5
对于第一个有14个竹子的生成器，在两秒的区间内，可得期望u为0.137，标准差σ为0.36。而在20秒的区间内，可得期望u为1.366，标准差σ为1.16
由于当u足够大时，泊松分布趋向于高斯分布（正态分布），因此这类随机数生成器也可以用来生成符合高斯分布的随机数。
对于上述讨论的推广是显然的，即对于包含n个竹子的随机数生成器，其概率密度函数为：f(x)=[(u^x)*e^(-u)]/(x!) ，其中期望u=n*r*T，标准差σ=u^0.5
对于第一个有14个竹子的生成器，在两秒的区间内，可得期望u为0.137，标准差σ为0.36。而在20秒的区间内，可得期望u为1.366，标准差σ为1.16
由于当u足够大时，泊松分布趋向于高斯分布（正态分布），因此这类随机数生成器也可以用来生成符合高斯分布的随机数。
以下是存档
链接：https://pan.baidu.com/s/1WbXSsadohWTwoHm-Ulpn2Q
提取码：cl5x
链接：https://pan.baidu.com/s/1WbXSsadohWTwoHm-Ulpn2Q
提取码：cl5x