Qui a d'abord proposé d'utiliser l' algorithme de Monte Carlo

Je suis sûr que tout le monde connaît l' expérience de Buffon sur l'aiguille au XVIIIe siècle, qui est l'un des premiers algorithmes probabilistes à calculer . $\pi$

L'implémentation de l'algorithme dans les ordinateurs nécessite généralement l'utilisation de , ou d'une fonction trigonométrique, qui, même si elles sont implémentées sous forme de séries tronquées, défait en quelque sorte l'objectif. $\pi$

Pour contourner ce problème, il existe l'algorithme de méthode de rejet bien connu: dessinez des coordonnées dans le carré unitaire et voyez si elles appartiennent au quart de cercle unitaire. Cela consiste à dessiner deux réels uniformes et dans (0,1), et à les compter uniquement si . Au final, le nombre de coordonnées conservées divisé par le nombre total de coordonnées est une approximation de . $x$ $y$ $x^2+y^2 < 1$ $\pi$

Ce deuxième algorithme est généralement considéré comme l'aiguille de Buffon, pensant qu'il est considérablement différent. Malheureusement, je n'ai pas été en mesure de retrouver qui l'a créé. Quelqu'un a-t-il des informations (documentées ou, au pire, non documentées) sur qui / quand cette idée est née?

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

Je pense que c'est le bon endroit.

Tyson Williams, le

@vzn: Merci pour ton commentaire! En effet, c'est ce que je crois, en particulier compte tenu des autres expériences de Von Neumann, en particulier celles résumées dans "Diverses techniques utilisées en connexion avec des chiffres aléatoires" (un de mes "papiers" préférés). J'espère que cette information n'est pas classée ... même si vous avez peut-être raison sur ce point également.

Jérémie

par ailleurs, il existe un algorithme étroitement lié où l'on utilise simplement tous les

points sur une grille carrée unitaire également espacée,

points sur un côté, où la distance unitaire est choisie "petite" par rapport au rayon du cercle. aussi, légitimement, il doit certainement y avoir une "première" citation quelque part dans la littérature, mais je ne peux pas la trouver jusqu'à présent. il y a un bon livre "history of Pi" de peter beckman, dont certains sont en ligne, et je ne le vois pas crédité dans la partie en ligne [google books]. vous vous demandez si c'est dans la partie hors ligne? c'est aussi l'un de mes problèmes préférés de monte carlo.

n^{2}

$n^2$

n

$n$

vzn

Nit mineur:

doit être

dans "le nombre de coordonnées qui ont été maintenues divisé par le nombre total de coordonnées est une approximation de

π

$\pi$

π / 4

$\pi/4$

π

$\pi$

Huck Bennett

Pour un très original, prenez deux nombres uniformes aléatoires entre 0 et 1, puis prenez leur quotient. Estimez la probabilité qu'il soit plus proche d'un nombre pair que d'un nombre impair. Cela devrait être

\frac{π - 1}{4}

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

dspyz

Qui a d'abord proposé d'utiliser l' algorithme de Monte Carlo

Réponses: