Saturday, December 4, 2010

Buffon Needle Drop

There is a very beautiful problem in probability theorem. It is known as the "Buffon Needle Drop". You can read the Wikipedia page if you like here.

As much as I love Wikipedia, I do not like their explanation. Everywhere I looked at that gave a solution to the Buffon Needle Drop gives a rather complicated argument. I perfer simple arguments. I came up with what I think is the simplest solution to the Buffon Needle Drop. It uses nothing but the most basic trigonometry and calculus.

I sometimes write mathematical posts to my standard readers in the hope that it would interest them. Mathematics is the most beautiful thing that I know of and I hope that I can pass its beauty off to other people. So I sometimes write math stuff which is very elementary but interesting. This is a very interesting problem. If you taken basic calculus (I guess it is called Calculus I in colleges) in college or high-school you should be able to follow this solution.

Problem: Consider a grid of parallel horizontal lines. Say that these lines are 1 unit apart (say an inch, whatever, it does not matter). Consider a needle that is 1 unit in length. Drop this needle on this grid of parallel lines. What is the probability that this needle intersects one of the parallel grid lines? (The answer is extremely surprising!)

Before solving the problem it is helpful to take a sheet of paper and draw various possibilities that can come up. Draw a few parallel lines and then draw a line segment the same length as the distance between the parallel lines. Try to draw this line segment (represented as the needle) in such a way that it ends up intersecting the grid lines. And then try to draw this line segment in such a way that it does not intersect any grid line.

Solution: A drop of the needle on this grid of lines is determined by two variables. The first one is its angle of drop. Let x be the measurement (in radians, remember in mathematics angles are measured in radians) of the angle of the drop. The angle will be measured that it makes with respect to the horizontal grid lines. So for example, if x=0 then the angle is zero and so the needle is positioned horizontally. If $x=\frac{\pi}{2}$ then the needle is positioned vertically.

The second variable the determines the needle is the location of its top point. The "top point" does not refer to the tip of the needle. Remember the needle is just a symbol for the line segment. The "top point" is the point that is higher up. If x is the angle of the needle strictly between 0 and $\frac{\pi}{2}$ then the needle slopes up and to the right. Therefore, the top point in this instance is the right point of the needle. If x is strictly between $\frac{\pi}{2}$ and $\pi$ then the angle is now obtuse. And so the needle slopes down and to the left. Therefore, in this case the top point in this instance is the left point of the needle.

Let us work in the case when x is acute. The second case is when x is obtuse, which is entirely similar to the first case. When we can understand the acute case the obtuse case will immediately follow.

The second variable, let us call it P, will measure the position of the top point of the needle. When we drop a needle on the grid its top point ends up in between two parallel horizontal lines. Let P measure the distance (vertical distance) between the top point and the bottom parallel line. Clearly, P is some number between 0 and 1, because the top point, in between two parallel lines, must be somewhere in between them - since the distance between these lines is 1 it follows that the distance from the top point to the bottom line is some number between 0 and 1. We call this number P.

Together these two variables, x (the angle) and P (the position), entirely determine where the needle is at. The angle determines how the needle is angled and the position of its top point determines how far or close it is to the parallel grid lines.

Let us fix an angle x. And as we said let us pretend that x is acute (so that our lines slope up and to the right). We only do this to make the pictures more accurate. We will draw some lines that will be have their top point as the right point. Of course the same argument is used when x is obtuse. I am just stressing this case to make the pictures look more honest.

For this fixed x let us draw a needle that has its top point sitting on the bottom parallel line. Clearly this needle intersects the line. If we move up the needle ever so slightly we get an intersection somewhere inside the line. If we keep on moving up this needle up eventually the bottom point will hit the bottom parallel line, which is still an intersection. But if we move up this needle just a bit more, then we no longer get an intersection.

What we just observed is geometrically represented in Figure 1 in the picture that is attached this post.

In Figure 1 the red line on the bottom shows that needle with angle x that has its top point (represented as a bold point) on the bottom parallel line. If you move this line up ever so slightly then its top point moves up also, and it still intersects the line somewhere inside. The last red line on top is the case when the top point has been moved so much that the bottom point is on the parallel line.

Notice the distance that was travelled by the top point from the bottom red line to the top red line. The top point travelled a distance of sin(x). Remember that x is the angle of the red lines. Basic trigonometry says that the opposite length of a right trangle (the distance travelled in this case) is the sine of the angle times the length of the hypotenuse. In this case the hypotenuse is the length of the red line which is assumed to have length of 1 unit. Therefore, the total distance the top point travelled is sin(x). (In case you are wondering, yes, the horizontal length of the red line is cos(x) because the cosine tells us the adjacent side length, but this is not needed in the solution).

If we move this top red line just a bit more, we get the blue line, which does not intersect the parallel lines at all.

It is easy to see from this geometric argument that for only for $P<\sin x$ does the needle intersect the parallel line. Because if $\sin x <. P<. 1$ then the top point would have moved high enough that the bottom point is away from the bottom line, it will be just like the blue line in the picture in Figure 1.

We have discovered an important condition! For angle x, the needle intersects a parallel line only if $P<\sin x$. This is all the trigonometry that we need.

Now consider a graph. Where the y-axis is P and the x-axis is x (the angle). Do not be confused with this graph. This is not the standard xy-graph. Because the y-axis does not depend on the x-axis (as with most graphs that are drawn). Rather it is just a graph of points. The tip point P can be anywhere between $0<.P<.1$. While the angle varies between all values $0<.x<.\pi$. The set of all points in this graph form a rectangle. To see this just draw the lines P=0,P=1,x=0, and $x=\pi$. These four lines form a rectangle. The region inside this rectangle represents all the possible outcomes of a thrown needle. Because any thrown needle has an angle x and a position P, which corresponds to a point in this rectangle.

Any needle thrown will have an angle and a location, therefore a needle will correspond to a point on this rectangle that we drawn. Now draw the curve $\sin x$. Remember our condition for intersection. A needle will intersect a parallel line only if $P<\sin x$, we proved this above. This means that the only needles that intersect correspond to all the points below the curve. All of what we said is represented graphically in Figure 2, with region below $\sin x$ shaped in.

Now it is easy to see what the propability of intersection is. The probability of intersection is equal to the probability of landing into that shaded region. What is the probability? Very easy. The entire rectangle has area of length times height. The length is $\pi$ and the height is 1. So the total area of the rectangle is $\pi$. If we can compute the area of the shaded region we would have the answer. We would have to just divide the shaded area by $\pi$ (total area) to know the probability of landing into the shaded region.

But what is the shaded area? Well, this is elementary calculus in high-school. Remember, the area below the curve, is equal to the integral of the curve.

Thus, we need to calculate $$\int_0^{\pi} \sin x dx$$. Seriously, this is the easiest kind of an integral one can hope for. You wish you would get such easy questions on a math final. What is it? Well, find an anti-derivative. Which is $-\cos x$. And so the area is $-\cos (\pi) - (-\cos 0)$. Now just recall that $\cos \pi = -1$ and $\cos 0 = 1$. So the shaded area works out to be 2.
This means that the probability of the needle intersecting a line is $\frac{2}{\pi}$.

Wow! What a surprising answer. It is amazing how $\pi$ appears in the answer. Do you remember basic probability problems in high-school? They always involved fractions as the answer. But this is a special kind of probability problem. It does not have a rational (fraction) answer to it (since pi is irrational).