random - 无无理操作的正态分布随机函数

Question

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

由于我提到的限制，任何接受有理数并输出无理数的操作都需要从头开始重新实现，以根据 Racket 的 native 分数生成近似值，不是 基于 float 。我查看了各种正常随机函数的算法，但在这些算法中，即使是像 Box-Muller 变换这样的“最简单”的算法，也涉及平方根、对数和三角函数等内容。迭代平均很容易，所以平方根不是问题，但我不想在这里重新发明更多的轮子。

我可以使用哪些算法来生成近似正态随机数而不调用无理运算，如根、对数和三角函数？

Answer 1

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

在仔细研究了几个关于正态分布随机数的不同 SO 帖子之后，我发现对我来说最好的解决方案实际上是最幼稚的解决方案:滥用中心极限定理。任何分布的随机变量加起来都可以很好地近似于正态分布。在 Racket 中，我的解决方案竟然是令人愉快的简洁

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

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

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，这样我们就可以在单个乘法步骤中将钟形曲线拉长或压扁所需的量。 p>

如果您对随机变量样本求和 由此产生的近似正态分布的标准差等于

哪里是变量本身的标准差。^* 从 0 到 1 的均匀随机分布的标准差等于 ^† 所以用这个代替 我们看到我们想要的只是

很容易计算出

^* 参见 "Central Limit Theorem"在 Wolfram MathWorld 上。等式在恒等式 (2) 下给出，这里乘以 N 给出总和的标准差而不是平均值。

^† 参见 "Continuous uniform distribution"在维基百科上。右边的表，“方差”平方根。

但这不会将您的范围限制在 ±6 个标准偏差内吗？

是的，但是你的分布范围必须在某个地方被截断，除非你有无限的内存力，±6σ 是 A) almost as good as Box-Muller on a 32-bit machine B) 已经很大了。