将人口随机分成 6
Randomly splitting a population in 6
我正在研究三角网格上元胞自动机的粒子扩散算法。这意味着每个单元格都有 6 个邻居。
每个细胞都有一定数量的粒子。
每个单元格在每次迭代中将其粒子传播到相邻单元格。
我在有效地执行此操作时遇到了很多麻烦，因为有数十万（或有时数百万）个细胞，每个细胞中都有大量粒子 n (n >> 100)。
我正在寻找一种将数字随机分成 6 个部分的算法
一种可行但效率低下的方法：
生成与一个单元格中的粒子一样多的随机数，从区间 (0,6) 上的均匀分布中抽取。
- 如果数字在(0,1)：将粒子扩散到邻居1。
- 如果数字在(1,2)：将粒子扩散到邻居2。
- 如果数字在(2,3)：将粒子扩散到邻居3。
- 等...
这适用于 'small' 个粒子数 (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
r2 effectivle 将 (r0 - r1) 个粒子群分成两组，每组分配给一个邻居。
数字 r0、r1 和 r2 现在应该从 n 个粒子群中随机分成 3 个部分，每个部分都服从正态分布。
以同样的方式继续，将人口 (n - r0) 分成三部分。
这种方法对我来说似乎很有意义，但我相信我的方差可能离这里很远，所以我得到了奇怪的结果，其中有太多粒子 'split off' 到达一组邻居并且none 留给其他邻居。这引入了奇怪的各向异性效果。
背景：许多均匀分布的组合很好地近似于高斯分布。该算法是尝试修改Bastien Chopard在“物理系统的元胞自动机建模”第5.7章（第213页）中描述的算法
任何帮助发现我的方法中的错误或不同的，同样有效的方法将不胜感激。
我没有指定 im 编码的语言，因为我只是在寻找一个通用的算法。我使用的是 java（Processing 3.5），但如果您能以任何语言提供，那对我来说没问题。
据我查阅文献可以看出，最先进的算法是 Brown 和 Bromberg 提出的算法（“从多项分布生成随机变量的高效两阶段程序”，来自 1983 年） ，专门针对您的问题。
对于某个常数 c，样本六个独立 Poisson 随速率 cn 变化。如果它们的总和大于n，则重新绘制它们直到它们的总和小于或等于n。按照这些变量的指示传播粒子，并使用低效的方法传播其余部分。 c 应该在 1/6 的范围内；太高，我们绘制变量的次数太多，太低，我们为低效算法做了太多工作。
由于在整个模拟过程中需要大量样本，因此我们不必费力地降低绘制泊松变量的设置成本。对于每个可能的 n，设置 alias method 以在结果不超过 n.
的情况下以 cn 的比率对截断的泊松分布进行采样
我正在研究三角网格上元胞自动机的粒子扩散算法。这意味着每个单元格都有 6 个邻居。
每个细胞都有一定数量的粒子。
每个单元格在每次迭代中将其粒子传播到相邻单元格。
我在有效地执行此操作时遇到了很多麻烦，因为有数十万（或有时数百万）个细胞，每个细胞中都有大量粒子 n (n >> 100)。
我正在寻找一种将数字随机分成 6 个部分的算法
一种可行但效率低下的方法：
生成与一个单元格中的粒子一样多的随机数，从区间 (0,6) 上的均匀分布中抽取。
- 如果数字在(0,1)：将粒子扩散到邻居1。
- 如果数字在(1,2)：将粒子扩散到邻居2。
- 如果数字在(2,3)：将粒子扩散到邻居3。
- 等...
这适用于 'small' 个粒子数 (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
r2 effectivle 将 (r0 - r1) 个粒子群分成两组，每组分配给一个邻居。
数字 r0、r1 和 r2 现在应该从 n 个粒子群中随机分成 3 个部分，每个部分都服从正态分布。
以同样的方式继续，将人口 (n - r0) 分成三部分。
这种方法对我来说似乎很有意义，但我相信我的方差可能离这里很远，所以我得到了奇怪的结果，其中有太多粒子 'split off' 到达一组邻居并且none 留给其他邻居。这引入了奇怪的各向异性效果。
背景：许多均匀分布的组合很好地近似于高斯分布。该算法是尝试修改Bastien Chopard在“物理系统的元胞自动机建模”第5.7章（第213页）中描述的算法
任何帮助发现我的方法中的错误或不同的，同样有效的方法将不胜感激。
我没有指定 im 编码的语言，因为我只是在寻找一个通用的算法。我使用的是 java（Processing 3.5），但如果您能以任何语言提供，那对我来说没问题。
据我查阅文献可以看出，最先进的算法是 Brown 和 Bromberg 提出的算法（“从多项分布生成随机变量的高效两阶段程序”，来自 1983 年） ，专门针对您的问题。
对于某个常数 c，样本六个独立 Poisson 随速率 cn 变化。如果它们的总和大于n，则重新绘制它们直到它们的总和小于或等于n。按照这些变量的指示传播粒子，并使用低效的方法传播其余部分。 c 应该在 1/6 的范围内；太高，我们绘制变量的次数太多，太低，我们为低效算法做了太多工作。
由于在整个模拟过程中需要大量样本，因此我们不必费力地降低绘制泊松变量的设置成本。对于每个可能的 n，设置 alias method 以在结果不超过 n.
cn 的比率对截断的泊松分布进行采样