Saturday, March 14, 2015

In honor of Pi Day : Estimating the value of pi via Buffon's Needle

Last year we estimated the value of $\pi$ via Monte Carlo simulation. This year, we'll be revisiting the same exercise but using a different approach : Buffon's Needle. This approach is actually one of the oldest geometrical probability problems and it involves dropping needles on a lined sheet of paper and calculating the probability of the needles crossing lines in the page. This technique was first used by 18th century mathematician Georges-Louis Leclerc, Comte de Buffon.

In this scenario, we'll be dropping a bunch of randomly generated needles of length 1 on a grid with vertical lines. The spacing between the vertical lines is also of length 1. It turns out that you can estimate the value of $\pi$ by taking the fraction of the number of needles you dropped (Drops) and those that crossed any of the vertical lines (Hits) and multiplying by twice the length of a needle. See this ipython notebook for code used.

The following two graphs show our grid with 100 and 1000 randomly generated needles respectively



Let's work through the math:

$ 2 \times needlelength \times  \frac{Drops}{Hits}  \approx   \pi  $

where length of needle is 1 and the length of the spacing between the vertical grid lines is also 1

The graphs below were generated from a few hundred trials. For each trial, we increased the number of randomly generated needles. We can see the estimated value of  $\pi$ is about 3.12 which is a bit off from the true value of 3.14. I suspect there might be something going on with how the random needle center coordinates are generated since the needle graphs above are showing some symmetry. Regardless, we are still within 1% of the true value of $\pi$.




It's actually pretty cool to see how the value of $\pi$ sneaks out from the woodwork. There's probably a more intuitive way to explain how $\pi$ shows up in places we least expect

For all the code used for this analysis, visit this ipython notebook