Метод Монте-Карло Пи с фиксированным x

Во всех примерах кодов Монте-Карло, которые я нашел, которые вычисляют число пи, и 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 лучше, почему я никогда не видел ни одного примера кода, написанного таким образом? Связано ли это с выборкой адаптивной важности?


random algorithm montecarlo pi
person HD189733b    schedule 31.12.2016    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Я считаю, что это будет работать, даже если и x, и y генерируются одинаково. В этом случае вы бы разложили однородную сетку точек и посмотрели, какие из них попадают в круг.

Я думаю, вы правы, что для заданного количества точек равномерная выборка будет такой же точной, как и случайная выборка, но значительно быстрее.

Но что, если вы не знаете, сколько очков вы должны использовать? В этом случае я думаю, что случайная выборка лучше, потому что вы можете продолжать добавлять точки, пока общее значение не изменится очень мало. Вы не можете просто увеличить количество баллов, если используете равномерное распределение. Каждый раз, когда вы увеличиваете количество точек, вы должны создать всю сетку.

person murrdpirate    schedule 31.12.2016
comment
Я думаю, что равномерная выборка во всех измерениях намного медленнее в многомерной задаче. Например, в 3D равномерная выборка сходится со скоростью N^{1/3}, что медленнее, чем полностью случайная выборка, которая составляет N^{1/2}. А если только равномерная выборка в одном направлении, я не думаю, что придется делать все заново. Вам нужно только равномерно сэмплировать увеличенное количество точек. - person HD189733b; 31.12.2016
comment
Вдохновленный вашим ответом, я думаю, что для метода равномерной выборки (в 1D) есть проблема, если функция не является гладкой. Этот метод производит выборку только в центре сетки. Если функция значительно изменяется в зоне сетки, результат может быть ненадежным. Это может свидетельствовать о том, что скорость сходимости этого метода зависит от особенности подынтегральной функции. - person HD189733b; 31.12.2016
comment
@ HD189733b Разве N^{1/3} не быстрее? Я не вижу, как случайное распределение было бы лучше. Если бы я хотел вычислить объем сферы, и у меня было ровно 1000 точек для этого, я бы подумал, что оптимальным будет равномерное распределение точек — и не хуже, чем 1000 случайных точек. Подумайте об этом: как бы вы улучшили равномерную сетку? Все неоднородное будет иметь смещения в определенных местах. - person murrdpirate; 31.12.2016
comment
@ HD189733b HD189733b Согласен, равномерная выборка будет проблематичной для негладких функций. - person murrdpirate; 31.12.2016
comment
Да ты прав. Я допустил ошибку. Скорость сходимости для равномерной выборки не N^{-1/3}, а выше, чем N^{-1/2}, по крайней мере, для случая гладкой функции. - person HD189733b; 31.12.2016

arrow_upward
0
arrow_downward

Ваш метод вычисления π действительно действителен. Я уверен, что math.SE даст вам четкое доказательство этого, но в основном это (1) единичный круг интегрируем по Риману (2) индикаторная переменная для каждого среза имеет правильное ожидание (3) неравенство Хеффдинга (например) для показать сходимость по вероятности для суммы.

Дело в том, что этот метод не работает с множествами, не интегрируемыми по Риману. Рассмотрим, например, множество ([0, 1] - Q) ([0, 1] - Q), которое имеет меру 1, но на котором ваш метод будет всегда выбирайте рациональные столбцы x, которых нет в наборе.

См. также последовательности с малым расхождением, и это ваша идея, продвинувшаяся на шаг вперед.

person David Eisenstat    schedule 31.12.2016
comment
Спасибо! Не могли бы вы прокомментировать скорость сходимости? Могу ли я сказать, что полностью равноотстоящая последовательность является крайним случаем последовательностей с низким расхождением? Так что то, что я сделал, на самом деле является крайним случаем метода квази-Монте-Карло, это правда? - person HD189733b; 31.12.2016
comment
После некоторого поиска я не нашел ни одной ссылки на последовательность с низким расхождением или метод квази-Монте-Карло, обсуждаемый в отношении последовательности с равными интервалами. Так что я боюсь, что это утверждение неверно. - person HD189733b; 31.12.2016