随机将人群分成6组

3

我正在为三角形格点上的粒子扩散细胞自动机设计算法。这意味着每个单元格有6个相邻单元格。

每个单元格都有一定数量的粒子。

在每次迭代中,每个单元格将其粒子传播到相邻单元格。

由于有数十万(有时是数百万)个单元格,每个单元格中有大量的粒子n(n >> 100),我在进行高效计算方面遇到了很多麻烦。

我正在寻找一种将数字随机分成6部分的算法


一种有效但效率低下的方法:

生成与单元格中的粒子数相同的随机数,从区间(0,6)的均匀分布中抽取。

  • 如果数字在(0,1)之间:向邻居1传播粒子。
  • 如果数字在(1,2)之间:向邻居2传播粒子。
  • 如果数字在(2,3)之间:向邻居3传播粒子。
  • 等等...

这适用于“小”的粒子数量(n < 50),但会变得非常计算密集。


我的理论方法:

调用要分配的粒子数n。

从均值为0,方差为1的正态(高斯)分布中生成5个随机数。将这些数字称为r0、r1、r2、r3和r4。

r0 = n/2 + r0*(n/4) // this transforms r0 to a random number drawn from a normal distribution with mean n/2 and variance n/2

r0有效地将n个粒子的种群分成两组,每组都要分配给它们各自的三个相邻者。一个的大小为r0,另一个的大小为n-r0。

r1 = r0/3 + r0*(r0/9) // this transforms r1 to a random number drawn from a normal distribution with mean r0/3 and variance r0/3

r1有效地将r0个粒子的总数分成两组,一组分配给单个邻居,另一组分配给两个邻居。前者的数量为r1,后者的数量为r0-r1。

r2 = (r0 - r1)/2 + r2*((r0 - r1)/4) // this transforms r2 to a random number drawn from a normal distribution with mean (r0 - r1)/2 and variance (r0 - r1)/2
有效地将(r0-r1)个粒子的总数分成两组,每组分别分发给单个邻居。

现在,应该根据正态分布将数字r0、r1和r2从n个粒子的总数中分离出3个随机部分。

以同样的方式继续,将(n-r0)个粒子的总数分成三部分。


这种方法在我看来是有道理的,但我认为我的方差可能偏差很大,因此我得到了奇怪的结果,其中太多的粒子被“分裂”到一个邻居组中,没有留下其他邻居。这会引入奇怪的各向异性效应。

背景:许多均匀分布的组合很好地逼近高斯分布。这个算法是一种尝试修改Bastien Chopard在《物理系统的元胞自动机建模》第5.7章(第213页)中描述的算法。

如果您能帮助我找到方法中的错误或提供另一种类似有效的方法,我将非常感激。

我没有指定编程语言,因为我只是在寻找一般的算法。我使用的是Java(Processing 3.5),但如果您能提供任何语言,我都可以接受。


你可能在寻找的关键词是"多项式分布" - Ilmari Karonen
你可能会在交叉验证.SE上得到更有见地的答案(注意:在那里提问之前,请仔细阅读网站指南,以确定它是否适合在那里提问。我很少在交叉验证上活跃,所以不确定我的建议是否正确)。 - amit
1个回答

3
据我从文献综述中了解到,现有技术的算法是由Brown和Bromberg(1983年的论文“用于从多项分布中生成随机变量的高效两阶段过程”)提出的,该算法可针对您的问题进行专门优化。
对于某个常数,使用速率为的Poisson变量样本六个独立的。如果它们的总和大于,则重新绘制它们,直到它们的总和小于或等于。根据这些变量的要求传播粒子,并使用您的低效方法传播其余部分。应在<1/6>左右; 如果太高,我们会多次绘制变量,如果太低,则会为低效算法增加过多的工作量。

由于在模拟的整个生命周期内需要大量的样本,因此我们不必费太多力气来降低绘制泊松变量的设置成本。对于每个可能的n,使用别名方法设置以样本截断泊松分布,其速率为cn,前提是结果不超过n


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接