random - 处理正态(高斯)分布

Question

我基本上陷入了相当简单的问题:

Toss N coins and discover, how many of them land heads

解的性能一定不能依赖于N，所以我们不能只调用Math.random() < 0.5 N次。显然，高斯分布可以解决这个问题。

我使用了 Box-Muller 方法:

function gaussian_random(mean, variance) {
  var s;
  var x;
  var y;
  do {
    x = Math.random() * 2.0 - 1.0;
    y = Math.random() * 2.0 - 1.0;
    s = Math.pow(x, 2) + Math.pow(y, 2);
  } while ( (s > 1) || (s == 0) );

  var gaussian = x * Math.sqrt(-2*Math.log(s)/s);
  return mean + gaussian * Math.sqrt(variance);
}

数学表明，N 次抛硬币的平均值是 N/2方差为 N/4

然后，我做了测试，抛 N 个硬币 M 次，给出最小、最大和平均正面朝上的次数。

我比较了朴素方法(Math.random()多次)和高斯 Box-Muller 方法的结果。

有典型的测试输出:

Toss 1000 coins, 10000 times
Straight method: 
Elapsed time: 127.330 ms
Minimum: 434
Maximum: 558
Average: 500.0306
Box-Muller method: 
Elapsed time: 2.575 ms
Minimum: 438.0112461962819
Maximum: 562.9739632480057
Average: 499.96195358695064

Toss 10 coins, 10000 times
Straight method: 
Elapsed time: 2.100 ms
Minimum: 0
Maximum: 10
Average: 5.024
Box-Muller method: 
Elapsed time: 2.270 ms
Minimum: -1.1728354576573263
Maximum: 11.169478925333504
Average: 5.010078819562535

正如我们在 N = 1000 上看到的那样它几乎完美契合。

但是，关于N = 10 Box-Muller 发疯了:它允许这样的测试结果，我可以从 10 次抛硬币中得到(非常罕见，但有可能)11.17 个正面! :)

毫无疑问，我做错了什么。但到底是什么？

有source of test ，并链接到launch it

更新x2:看来，之前我没有很好地描述问题。它有一个通用版本:

How to get sample mean of N uniform random values (either discrete or continuous) in amortized constant time. Gaussian distribution is efficient for large N, but is there a way to make it work good on small N? Or on which exactly N, solution should switch from Gaussian method to some other (for exampled straightforward).

Answer 1

Math says, that mean of N coin tosses is N/2 and variance is N/4.

数学只说明它是一枚公平的硬币。而且解决方案不可能不依赖于 N。

假设所有 throw 都是相互独立的，对于精确行为，使用二项式分布而不是正态分布。二项式有两个参数:N 是抛硬币的次数，p 是获得正面(或反面，如果您愿意)的概率。在伪代码中...

function binomial(n, p) {
  counter = 0
  successes = 0
  while counter < n {
    if Math.random() <= p
       successes += 1
    counter += 1
  }
  return successes
}

对于大 N 有更快的算法，但这很简单并且在数学上是正确的。