Кто первым предложил использовать алгоритм Монте-Карло

26

Я уверен, что все знают об эксперименте Буффона с иглой в 18-м веке, это один из первых вероятностных алгоритмов для вычисления .π

Реализация алгоритма на компьютерах обычно требует использования или тригонометрической функции, которая, даже если они реализованы в виде усеченных рядов, в некотором роде не справляется с этой задачей.π

Чтобы обойти эту проблему, есть хорошо известный алгоритм метода отклонения: нарисуйте координаты в единичном квадрате и посмотрите, принадлежат ли они к четверти окружности. Это состоит в том, чтобы нарисовать два одинаковых вещественных числа и в (0,1) и считать их, только если . В итоге число сохраненных координат, деленное на общее количество координат, является приближением .y x 2 + y 2 < 1 πxyx2+y2<1π

Этот второй алгоритм обычно выдается за иголку Буффона, хотя он и сильно отличается. К сожалению, я не смог отследить, кто его создал. У кого-нибудь есть какая-либо информация (документированная или, в худшем случае, недокументированная) о том, кто / когда возникла эта идея?

Жереми
источник
6
Я думаю, что это правильное место.
Тайсон Уильямс
1
@vzn: Спасибо за ваш комментарий! Действительно, это то, во что я верю, особенно если учесть другие эксперименты фон Неймана, в частности те, которые кратко изложены в «Различных методах, используемых в связи со случайными цифрами» (моя любимая «статья»). Я надеюсь, что эта информация не засекречена ... хотя вы можете быть правы и в этом вопросе.
Жереми
1
кстати, существует тесно связанный алгоритм, в котором просто используются все точек на одинаково расположенной единичной квадратной сетке, точек на стороне, где единичное расстояние выбрано «маленьким» относительно радиуса круга. также, законно, где-то в литературе обязательно должна быть «первая» цитата, но я пока не могу ее найти. Есть хорошая книга «История Пи» Питера Бекмана, некоторые из которых находятся в сети, и я не вижу, чтобы она была зачислена в онлайн-часть [google books]. интересно, если это в автономной части? это также одна из моих любимых проблем Монте-Карло. nn2n
vzn
2
Minor nit: должно быть в «число координат, которые были разделены на общее количество координат, является приближением ». π / 4 πππ/4π
Гек Беннетт
1
Для действительно необычного, возьмите два случайных равномерных числа от 0 до 1, а затем возьмите их частное. Оцените вероятность того, что она ближе к четному числу, чем к нечетному. Это должно бытьπ14
dspyz

Ответы:

2

Метод Монте-Карло обычно приписывают Метрополису и Уламу, последний был математиком по манхэттенскому проекту.

Если у меня хорошая память, Улам опубликовал статью, в которой он вычисляет число Пи, используя алгоритм.

Фил
источник
1
ага какой?
vzn
Попробуйте проверить выбранную книгу работ Улама: Наборы, числа и вселенные ...
Фил
10
Ссылка действительно поможет.
Гек Беннетт
1
Эта ссылка на библиографию может помочь: math.fullerton.edu/mathews/n2003/montecarlopi/MonteCarloPiBib/…
Фил