2

我基本上坚持相当简单的问题：

扔N个硬币，发现有多少个正面朝上

解决方案的性能不能依赖于 N，所以我们不能只调用Math.random() < 0.5N 次。显然，有高斯分布来拯救。

我使用了 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 = 10Box-Muller 上发疯了：它允许这样的测试结果，我可以从 10 次抛硬币中得到（很少，但有可能）11.17 个正面！:)

毫无疑问，我做错了什么。但究竟是什么？

有测试源和启动它的链接

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

如何在摊销常数时间内获得N 个均匀随机值（离散或连续）的样本均值。高斯分布对于大N是有效的，但是有没有办法让它在小N上工作得很好？或者在哪个N上，解决方案应该从高斯方法切换到其他方法（例如简单的）。

4

2 回答 2

2

数学说，N 次抛硬币的平均值是 N/2，方差是 N/4。

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

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

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

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

于 2016-09-30T15:14:42.587 回答
0

根据批准的答案中讨论的内容，我提出了这个特定的解决方案。

有经验法则n*p >= 10 and n*(1-p) >= 10，但让我们定义更严格的规则。

首先，Box-Muller 将严格限制在 [-6,6]，以确保正确的结果（640 kB 应该......，我的意思是，6 sigma 应该对每个人都足够了）。

然后，使用6常数，我们声明，为了让 Box-Muller 产生有效结果，Math.sqrt(variance) * 6不得超过mean。在分别使用N/2and N/4asmean和reduce 之后variance，我们得到了这样的结果：

Math.sqrt(N) * 6 <= N

N >= 36

虽然这个条件成立，但我们可以安全地使用 capped Box-Muller Gaussian。在任何较小的样本量上，坚持二项式解决方案。

刚刚在统计上检查了这条规则 - 在相对大量（1000 万）的测试中，最小值停止超出样本大小 32 及以上的边界。

于 2016-09-30T20:10:09.350 回答