Subscribe to Computing Intelligence

Sunday, April 5, 2009

The Buffon Needle Problem: The Solution to Puzzle Number Two

I will admit, I have been a little disappointed by the lack of attempts to solve puzzle number two. So far, no one has attempted to send in solutions, either incorrect or correct. Rather than waiting around, I assume in vain, for people to send me attempts, I decided it was about time I posted what I find to be an elegant and fascinating solution.

To briefly reiterate the problem, one is trying to come up with an empirical estimate of π based on repeatedly dropping a rod of length L onto a floor with parallel floorboards separated by distance D. I have generated a quick diagram of the situation in Paint (this computer does not have any actual image editors on it other than Gimp which I am still learning how to use, so please forgive the rudimentary ugliness of the diagram), which also introduces the value of x which is the distance from the centre of the rod to the nearest floorboard edge.
Clearly, x can range from 0 to D/2. As one assumes a uniform probability for the position of the rod, the probability density function of x is 1/(D/2) = 2/D. Things are a little less clear when outlining the properties of the random variable θ, as the most obvious choice (for me) would be it can range from 0 to π. This will, however, cause problems later due to the properties of the sine function (namely that sin(0) = sin(π) = 0), so it is best to define θ as the measure of the acute angle. It can thus range from 0 to π/2, and, also assuming uniform probability, the probability density function of θ is 1/(π/2) = 2/π. Since θ and x are independent, the overall probability density function for the needle can be found by multiplying the two independent density functions together, yielding 4/πD.

Since we are interested in the number of times the rod crosses the lines between the floorboards, we need to determine when that happens. With a little bit of geometry, it is fairly clear that whenever x < (L/2)sinθ the rod crosses the floorboards. Thus, to find the expected fraction of crosses, we need to integrate the probability density function 4/πD over the two random variables, first integrating from 0 to (L/2)sinθ with respect to x and then from 0 to π/2 with respect to θ (if anyone knows how to write integrals in html, I would appreciate it if you could tell me). First, integrating 4/πD with respect to x from 0 to (L/2)sinθ results in 2Lsinθ/πD. Integrating this result with respect to θ from 0 to π/2 yields 2Lsin(π/2)/πD = 2L/πD.

Thus, the expected ratio the number of times the rod crosses the division between floorboards divided by the number of times it is dropped is 2L/πD. As one repeatedly drops the rod and counts the number of crosses, the value will converge to this expected value. Since the length of the rod and the distance between the floorboards is easily measurable, it is a simple computation to achieve an estimate for π.

This is actually a physical example of a branch of computational techniques known as Monte Carlo estimation in which a series of random or pseudorandom samples are used to estimate a result. I find it extremely fascinating, and I think it has a measure of profundity that should not be lightly dismissed. The fact that one is able to simply count a binary event and use that ratio to find an estimate for a much more complicated value is absolutely amazing (of course, it should be immediately obvious that one will never be able to find the actual value of π with this method as the estimate will always be a ratio of number of crosses over number of trials and thus will always be a rational number). Probability and statistics is an amazing branch of mathematics, and it is something I wish I were better at.


Peter said...

It looks to me like -D/2<x<D/2.

Mozglubov said...

Negative x doesn't really have meaning, since x is the distance to the nearest edge. If that is the top edge, the distance still has to be a positive value. All you really care about with x is whether it is greater than (L/2)sinθ (in which case the rod does not intersect the division between floorboards) or not (the rod does). If you define x so it is directional and can therefore take on negative values, you end up with a whole mess of trouble trying to get your greater than and less than symbols correct.

Peter said...

Ah, I see. My answer was half your answer, but the range of x isn't going to cause that. I'd integrated from θ from zero to π, double counting the values that will cross a crack. My bad.

And, I don't think there's a good way to do integrals in HTML. W3C offers MathML, but I don't know if it's supported by things like blogger. The "best" option is to use MS Office, OpenOffice, MatLab, etc to create an image file of the formula you want to post. I think I've heard that MathCad is the easiest to use for that.

Mozglubov said...

Yeah, getting the bounds is tricky... I've solved this problem several times, and still sometimes make a mistake with my range of values. The reason I'm fairly confident with my solution given here is because it agrees with the value in my textbook... I may be a semi-competent mathematician at best, but I think Peter Whittle knows his stuff.

As for writing integrals in html, I was afraid that making an image might be the only answer... That's a bit of a pain.

wisefly said...

Har, textbooks solutions should never give you 100% confidence in your answer, especially when it's so easy to set up an experiment! If the downstairs neighbours start to complain, then maybe a computer simulation is in order. Although I don't know how confident we can be in the computer's random number generator...

Mozglubov said...

Note the term 'fairly'... but yeah, also, textbooks often have mistakes and whatnot. So, really, my confidence stems from my tentative confidence in my own mathematical skills, the agreement of my textbook, and the agreement of Wikipedia. While all three have the possibility of error, all three simultaneously having an error (and the same error, at that) has a rather small chance. As for actually performing the experiment, I will be quite impressed if you take the time to do it! Apparently a guy named Mario Lazzarini did it in 1901, but he kind of cheated by setting a nice number of trials to make the fraction more closely resemble pi.