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?

Improve this question
$\endgroup$
9
  • 6
    $\begingroup$ I think its the right place. $\endgroup$
    – Tyson Williams
    Jul 1, 2012 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, 2012 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, 2012 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, 2013 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, 2014 at 17:10

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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