algorithm - 固定 x 的 Monte Carlo pi 方法

Question

在我发现的所有计算 pi 的蒙特卡洛示例代码中，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) 的速度收敛。第二种方法误差稍小，第二种代码运行速度稍快。所以在我看来，第二种方法更好。而对于更高维空间的采样，我认为总是可以在一个维度上选择一个固定列表，然后在其他维度上随机采样。这是真的吗？

是否有任何引用可以证明固定 x 方法也是正确的？

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

Answer 1

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

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

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