26

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?

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
Jérémie
  • 638
  • 4
  • 12
  • Is this the right place to ask such questions? (Though I honestly don't have any real hope of finding an answer at all!) – Jérémie Jul 01 '12 at 03:09
  • 6
    I think its the right place. – Tyson Williams Jul 01 '12 at 18:05
  • IIRC, you can find the answer in the second chapter of first volume of The Art of Computer Programming by D.E. Knuth. – Kaveh Jul 02 '12 at 07:50
  • @Kaveh: Thanks for the reference, but unfortunately I checked both the original and 1997 edition, and did not find anything. The index has a reference to "Monte Carlo" which indeed points to the second chapter (section 2.5), but nothing is said about simulating $\pi$ or the method I describe. :( – Jérémie Jul 02 '12 at 15:23
  • agree with you that this is not same as buffon's method although a clever derivation might show they are equivalent. looking up this history, am amazed that nobody is credited. it seems to be a "folklore theorem". however it was likely discovered by the originators of monte carlo methods, ie ulam & von neumann around ~1944. von neumann did some of the 1st computerized calculations of pi. the methods were invented for atomic bomb calculations & it seems quite possible the origins of the method are even classified info...? – vzn Jul 03 '12 at 05:38
  • 1
    @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. – Jérémie Jul 05 '12 at 22:06
  • 1
    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. – vzn Jul 06 '12 at 04:56
  • 2
    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$." – Huck Bennett Jul 26 '13 at 03:27
  • 1
    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}$ – dspyz Feb 20 '14 at 17:10

1 Answers1

2

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.

Phil
  • 116
  • 5