没有无理运算的正态分布随机函数

Question

我正在开发一款游戏，我想要确定性的演示播放，该播放可以在以不同方式处理浮点数的架构之间移植。我使用的是 Racket 语言，它作为一种原始数据类型，方便地具有有理数分数的非浮点表示。我想用它们来实现一个近似正态分布的随机函数，该函数接受平均值和标准差参数（偏度将是镀金的）。

由于我提到的限制，任何接受有理数并输出无理数的操作都需要从头开始重新实现，以基于 Racket 的本机分数生成近似值，而不是基于浮点。我研究了各种用于正态随机函数的算法，但其中许多“最简单”的算法（例如 Box-Muller 变换）都涉及平方根、对数和三角函数等内容。迭代平均很容易，所以平方根不是问题，但我不想重新发明比这里需要的更多的轮子。 我可以使用哪些算法来生成近似正态随机数

而无需调用根、对数和三角函数等无理运算？

我在输入这个问题后但在发送之前就确定了一个解决方案，所以我将分享我的知识问答风格。

Answer 1

在仔细研究了几篇关于正态分布随机数的不同 SO 帖子后，我发现对我来说最好的解决方案实际上是最天真的解决方案：滥用中心极限定理。任何分布的随机变量加起来都可以很好地近似正态分布。在 Racket 中，我的解决方案非常简洁

(define (random/normal μ σ)
  (+ (* (- (for/sum ([i 12])
                    (random/uniform 0 1))
           6)
        σ)
     μ))

其中

random/uniform

是我生成均匀随机有理数的函数。 在中缀命令式伪代码中，这意味着：

Function random_normal(μ, σ):
  iterations := 12
  sum := 0
  for i from 1 to iterations:
    sum += random_uniform(0, 1)
  sum -= iterations / 2          # center the distribution on 0
  return σ * sum + μ

为什么需要 12 次迭代？一些 SO 答案提到了这个解决方案，但没有解释为什么 12 是一个神奇的数字。当我们将这些数字相加时，

我们希望该随机和的标准差等于 1

，这样我们就可以在单个乘法步骤中将钟形曲线拉伸或压扁所需的量。

如果对随机变量样本进行求和

，则所创建的近似正态分布的标准差等于

其中

是变量本身的标准差。* 从 0 到 1 的均匀随机分布的标准差等于 †，因此通过将其替换为 ，我们可以看到我们想要的只是

很容易就能实现

*

请参阅 Wolfram MathWorld 上的

“中心极限定理”^{。方程在恒等式 (2) 下给出，此处乘以} N 给出总和而不是平均值的标准差。 †

请参阅维基百科上的

“连续均匀分布”^{。右表，“方差”} 开平方。 但这是否会将您的范围限制为 ±6 个标准差？

确实如此，但是分布的范围必须在某个地方被截断，除非你有无限的内存，并且 ±6σ 是 A)

几乎与 32 位机器上的 Box-Muller 一样好

和 B) 已经很大了。