Wer hat zuerst vorgeschlagen, mit dem Monte-Carlo-Algorithmus

Ich bin sicher, dass jeder von Buffons Nadelexperiment im 18. Jahrhundert weiß , das ist einer der ersten probabilistischen Algorithmen, die berechnen . $\pi$

Die Implementierung des Algorithmus in Computern erfordert normalerweise die Verwendung von oder einer trigonometrischen Funktion, die, selbst wenn sie als verkürzte Reihe implementiert werden, den Zweck irgendwie zunichte macht. $\pi$

Um dieses Problem zu umgehen, gibt es den bekannten Ablehnungsalgorithmus: Zeichnen Sie Koordinaten in das Einheitsquadrat und prüfen Sie, ob sie zum Einheitsviertelkreis gehören. Dies besteht darin, zwei gleichförmige Reelle und in (0,1) zu zeichnen und sie nur zu zählen, wenn . Am Ende ist die Anzahl der Koordinaten, die durch die Gesamtzahl der Koordinaten geteilt wurden, eine Näherung von . $x$ $y$ $x^2+y^2 < 1$ $\pi$

Dieser zweite Algorithmus wird normalerweise als Buffons Nadel ausgegeben, obwohl er sich erheblich unterscheidet. Leider konnte ich nicht feststellen, von wem es stammt. Hat jemand irgendwelche Informationen (dokumentiert oder im schlimmsten Fall nicht dokumentiert) darüber, wer / wann diese Idee entstanden ist?

ds.algorithms reference-request randomized-algorithms ho.history-overview monte-carlo Jérémie
quelle

Ich denke, es ist der richtige Ort.

Tyson Williams

@vzn: Danke für deinen Kommentar! Tatsächlich ist es das, was ich glaube, besonders in Bezug auf Von Neumanns andere Experimente, insbesondere jene, die in "Verschiedene Techniken, die in Verbindung mit zufälligen Ziffern verwendet werden" (einem meiner bevorzugten "Papiere") zusammengefasst sind. Ich hoffe, diese Informationen sind nicht klassifiziert ... obwohl Sie in diesem Punkt vielleicht auch Recht haben.

Jérémie

Übrigens gibt es einen eng verwandten Algorithmus, bei dem man nur alle

Punkte auf einem gleich beabstandeten quadratischen Einheitsgitter verwendet,

Punkte auf einer Seite, bei der der Einheitsabstand im Verhältnis zum Radius des Kreises "klein" gewählt wird. auch, zu Recht, muss es definitiv irgendwo in der Literatur ein "erstes" Zitat geben, aber ich kann es bis jetzt nicht finden. es gibt ein gutes buch "history of pi" von peter beckman, von dem einige online sind, und ich sehe es nicht im online-teil [google books] gutgeschrieben. frage mich, ob es im Offline-Teil ist? Dies ist auch eines meiner Lieblingsbeispiele für Probleme mit Monte Carlo.

n^{2}

$n^2$

n

$n$

VZN

Minor nit:

sollte

in "Die Anzahl der Koordinaten, die durch die Gesamtzahl der Koordinaten dividiert wurden, ist eine Annäherung an

π

$\pi$

π / 4

$\pi/4$

π

$\pi$

Huck Bennett

Nehmen Sie für eine wirklich skurrile, zwei zufällige einheitliche Zahlen zwischen 0 und 1 und nehmen Sie dann ihren Quotienten. Schätzen Sie die Wahrscheinlichkeit, dass es näher an einer geraden als an einer ungeraden Zahl liegt. Dies sollte

\frac{π - 1}{4}

$\frac{\pi - 1}{4}$

dspyz

Wer hat zuerst vorgeschlagen, mit dem Monte-Carlo-Algorithmus

Antworten: