26
$\begingroup$

I'm sure everybody knows of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$.

The implementation of the algorithm in computers usually calls for the use of $\pi$, or a trigonometric function, which, even if they are implemented as truncated series, sort of defeats the purpose.

To circumvent this issue, there is the well-known rejection-method algorithm: draw coordinates in the unit square, and see whether they belong to the unit quarter circle. This consists in drawing two uniform reals $x$ and $y$ in (0,1), and counting them only if $x^2+y^2 < 1$. In the end, the number of coordinates that have been kept divided by the total number of coordinates is an approximation of $\pi$.

This second algorithm is usually passed off as Buffon's needle, thought it is considerably different. Unfortunately, I have not been able to track down who originated it. Does anybody have any information (documented, or at worst undocumented) as to who/when this idea originated?

$\endgroup$
  • 6
    $\begingroup$ I think its the right place. $\endgroup$ – Tyson Williams Jul 1 '12 at 18:05
  • 1
    $\begingroup$ @vzn: Thank you for your comment! Indeed this is what I believe, especially considered Von Neumann's other experiments, in particular those summarized in "Various Techniques Used in Connection With Random Digits" (a favorite "paper" of mine). I do hope this information is not classified... though you may be right on this point as well. $\endgroup$ – Jérémie Jul 5 '12 at 22:06
  • 1
    $\begingroup$ by the way there is a closely related algorithm where one just uses all the $n^2$ points on a equally spaced unit square grid, $n$ points on a side, where the unit distance is chosen "small" relative to the radius of the circle. also, legitimately, there must definitely be a "first" citation somewhere in the literature, but I cant find it so far. there is a good book "history of Pi" by peter beckman, some of which is online, and I dont see it credited in the online part [google books]. wonder if it is in the offline part? this is also one of my favorite example monte carlo problems. $\endgroup$ – vzn Jul 6 '12 at 4:56
  • 2
    $\begingroup$ Minor nit: $\pi$ should be $\pi/4$ in "the number of coordinates that have been kept divided by the total number of coordinates is an approximation of $\pi$." $\endgroup$ – Huck Bennett Jul 26 '13 at 3:27
  • 1
    $\begingroup$ For a really quirky one, take two random uniform numbers between 0 and 1 and then take their quotient. Estimate the probability it's closer to an even number than an odd number. This should be $\frac{\pi - 1}{4}$ $\endgroup$ – dspyz Feb 20 '14 at 17:10
2
$\begingroup$

The Monte-Carlo method is usually attributed to Metropolis and Ulam, the latter was a mathematician on the Manhattan project.

If my memory is good, Ulam published a paper where he computes pi using the algorithm.

$\endgroup$
  • 1
    $\begingroup$ uh huh which one? $\endgroup$ – vzn Jul 25 '13 at 4:21
  • $\begingroup$ Try checking Ulam's selected works book: Sets, Numbers and Universes... $\endgroup$ – Phil Jul 25 '13 at 4:25
  • 10
    $\begingroup$ A reference would really help. $\endgroup$ – Huck Bennett Jul 25 '13 at 4:44
  • 1
    $\begingroup$ This link to a bibliography may help: math.fullerton.edu/mathews/n2003/montecarlopi/MonteCarloPiBib/… $\endgroup$ – Phil Jul 25 '13 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.