Monte Carlo 固定 x 的 pi 方法

Question

在我找到的所有计算 pi 的 Monte Carlo 示例代码中，x 和 y 都是在 0 和 1 之间随机生成的。例如，示例代码如下所示

  Ran rdm(time(NULL));
  double x, y;
  int sum=0;
  for(int i=0;i<N;i++)
  {
    x=rdm.doub();         // Both x and y are generated randomly
    y=rdm.doub();
    if(x*x+y*y<1)
      sum++;
  }
  return 4.*sum/N;

我不明白随机生成两个轴而不是选择一个固定且统一的 x 列表然后只随机生成 y 的意义是什么，如下面的示例代码。

  Ran rdm(time(NULL));
  double x=0.5/N, dx=1./N, y;   //x is a fixed sequential list
  int sum=0;
  for(int i=0;i<N;i++)
  {
    y=rdm.doub();               // only y is generated randomly
    if(x*x+y*y<1)
      sum++;
    x+=dx;
  }
  return 4.*sum/N;

这两个例子我都试过了。两种方法都以 ~ 1/sqrt(N) 的速度收敛。第二种方法误差稍小，第二种代码运行速度稍快。所以在我看来，第二种方法更好。而对于更高维度的采样space，我认为总是可以在一个维度上选择一个固定列表，然后在其他维度上随机采样。这是真的吗？

有没有参考可以证明固定x的方法也是正确的？

如果固定x方法更好，为什么我从来没有见过这样写的示例代码？它与自适应重要性采样有关吗？

Answer 1

你计算π的方法确实有效。我相信 math.SE 会给你一个清晰的证明，但它基本上是 (1) 单位圆盘是黎曼可积的 (2) 每个切片的指示变量都有正确的期望 (3) Hoeffding 不等式（例如) 以显示总和的概率收敛。

事实是，这种方法不适用于黎曼不可积的集合。例如，考虑集合 ([0, 1] - Q) × ([0, 1] - Q)，它有测度1 但您的方法将始终对不在集合中的有理 x 列进行采样。

另见 low-discrepancy sequences，这是你的想法更进一步。

Answer 2

我相信即使 x 和 y 统一生成也能正常工作。在那种情况下，您将布置一个统一的点网格并查看哪些点落在圆圈内。

我认为您是对的，对于给定的点数，均匀采样与随机采样一样准确，但速度要快得多。

但是如果您不知道应该使用多少点怎么办？这种情况下，我觉得随机抽样比较好，因为可以一直加分，直到整体值变化很小。如果您使用的是均匀分布，则不能简单地增加点数。任何时候增加点数，都必须创建一个完整的网格。

Monte Carlo 固定 x 的 pi 方法

Monte Carlo pi method with fixed x

algorithm

random

montecarlo

pi