Buffon's Needle, the Easy Way
Buffon's needle is a popular probability problem. Rule lines on the floor a distance d apart and toss a needle of length l<d onto it. What is the probability that the needle crosses a line? A solution is described at wikipedia but it involves a double integral and some trigonometry. Nowhere does it mention that there is a less familiar but much simpler proof, though if you follow the links you'll find it. In addition, the usual solution involves π but gives little intuition as to why π appears. The simpler proof reveals that it appears naturally as a ratio of the circumference of a circle to its diameter. I've known this problem since I was a kid and yet I hadn't seen the simpler proof until a friend sold me his copy of Introduction to Geometric Probability for $5 a few days ago.
So instead of solving Buffon's needle problem we'll solve what appears to be a harder problem: when thrown, what is the expectation of the number of times a rigid curved (in a plane) wire length l (no restriction on l) crosses one of our ruled lines d apart? Here's an example of one of these 'noodles'. It crosses the ruled lines three times:
Expectation is linear in the sense that E(A+B) = E(A)+E(B). So if we imagine the wire divided up into N very short segments of length l/N the expectation for the whole wire must be the sum of the expectations for all of the little pieces. If the wire is well behaved, for N large enough the segments are close to identical straight line segments. Here's a zoomed up view of a piece of our noodle:
For a small straight line segment the expectation must simply be a function of the length of the segment. The expectation for the whole wire is the expectation for one segment multiplied by the number of segments. In other words, the expectation is proportional to the length of the wire and we can write E(l)=kl for some constant k.
Now we know it's proportional to the length, we need to find the constant of proportionality, k. We need to 'calibrate' by thinking of a noodle shape where we know in advance exactly how many times it will cross the ruled lines. The following picture gives the solution:
A circle of diameter d will almost always cross the lines in two places. The length of this wire is πd so E(πd)=2 and k=2/πd.
The expected number of crossings for a wire of length l is 2l/πd. A needle of length l<d can intersect only zero or one times. So the expected value is in fact the probability of intersecting a line. The solution is 2l/πd.
No integrals needed.
The expected number of crossings is an example of an invariant measure, something I've talked about before. There are only a certain number of functions of a noodle that are additive and invariant under rotations and just knowing these facts is almost enough to pin down the solution.
Now I can leave you with a puzzle to solve. In the UK, a 50p coin is a 7 sided curvilinear polygon of constant width. Being constant width means a vending machine can consistently measure its width no matter how the coin is oriented in its plane. Can you use a variation of the argument above to compute the circumference of a 50p coin as a function of its width?
So instead of solving Buffon's needle problem we'll solve what appears to be a harder problem: when thrown, what is the expectation of the number of times a rigid curved (in a plane) wire length l (no restriction on l) crosses one of our ruled lines d apart? Here's an example of one of these 'noodles'. It crosses the ruled lines three times:
Expectation is linear in the sense that E(A+B) = E(A)+E(B). So if we imagine the wire divided up into N very short segments of length l/N the expectation for the whole wire must be the sum of the expectations for all of the little pieces. If the wire is well behaved, for N large enough the segments are close to identical straight line segments. Here's a zoomed up view of a piece of our noodle:
For a small straight line segment the expectation must simply be a function of the length of the segment. The expectation for the whole wire is the expectation for one segment multiplied by the number of segments. In other words, the expectation is proportional to the length of the wire and we can write E(l)=kl for some constant k.
Now we know it's proportional to the length, we need to find the constant of proportionality, k. We need to 'calibrate' by thinking of a noodle shape where we know in advance exactly how many times it will cross the ruled lines. The following picture gives the solution:
A circle of diameter d will almost always cross the lines in two places. The length of this wire is πd so E(πd)=2 and k=2/πd.
The expected number of crossings for a wire of length l is 2l/πd. A needle of length l<d can intersect only zero or one times. So the expected value is in fact the probability of intersecting a line. The solution is 2l/πd.
No integrals needed.
The expected number of crossings is an example of an invariant measure, something I've talked about before. There are only a certain number of functions of a noodle that are additive and invariant under rotations and just knowing these facts is almost enough to pin down the solution.
Puzzle
Now I can leave you with a puzzle to solve. In the UK, a 50p coin is a 7 sided curvilinear polygon of constant width. Being constant width means a vending machine can consistently measure its width no matter how the coin is oriented in its plane. Can you use a variation of the argument above to compute the circumference of a 50p coin as a function of its width?
posted by sigfpe at Saturday, October 31, 2009
12 Comments:
Expectation is linear in the sense that E(A+B) = E(A)+E(B). So if we imagine the wire divided up into N very short segments of length l/N the expectation for the whole wire must be the sum of the expectations for all of the little pieces.
I don't understand this - that's only when A and B are independent, isn't it? Clearly, this isn't the case here -- as you discuss later, a line forming a circle of diameter d has probability 1 of crossing a line, a straight line of length pi*d will have a non-zero probability of not crossing a line.
Or?
Cool proof (but I wonder much effort does it take to formalise the linear approximation bit).
What do you mean by "constant width"? Do you mean, given a 50p coin and a ruler both in fixed orientatio but you can slide them around, that the greatest width measurable is the same, no matter the orientation?
ketil,
Remember expectation is a sum or integral so it's always linear regardless of independence.
Fergal,
Imagine putting the coin in a box and sliding the left and right sides of the box as close as possible. The distance between the sides is the width. For a 50p coin the minimum width is independent if the orientation.
This comment has been removed by the author.
"For a 50p coin the minimum width is independent if the orientation."
Surely maximum. When you can't squeeze the sides of the box together any further you have minimised the width of the box, not the coin.
It wasn't until I'd gone and figured out the answer via basic geometry that I realised your clarification of "width" almost gives away the answer. That said, proving it via geometry is quite easy given one theorem about angles in a circle.
@ketil: A straight line of length pi*d also has a non-zero chance of crossing 3 lines. This must happen often enough to offset the times it crosses 0 or 1 lines.
I don't think this argument is complete. Let me ask the following (possibly stupid) question:
Let's modify the problem so that we are dealing with one line, not an infinite number of parallel lines spaced a uniform distance apart. And let's restrict ourselves to a line segment, not some arbitrary well-behaved curve. Now, what's the expected number of intersections between the line and the segment?
Clearly, the expected value must be between 0 and 1, because the only possible outcomes is that they don't intersect, or that they intersect in exactly one location. However, your reasoning would seem to suggest that by choosing a sufficiently long line segment, the expected number of intersections could be greater than one.
Now, I haven't worked out the resolution in detail, but I suspect the resolution to this paradox is carefully considering the probability distribution for the location of the line segment: first of all you can't have a uniform distribution over an infinite plane, so let's say we choose the distance from an endpoint of the segment to the line according to a Gaussian distribution centered on the line, and choose the orientation uniformly. If we were to "tack on" another line segment onto the end of the first, it's probability distribution should be a flatter curve, again centered on the line.
It seems to me that your argument would have to depend upon the translational symmetry of your parallel lines: in effect you can have a uniform distribution over the entire plane by choosing a uniform distribution inside a given box that can tile the plane.
Leon,
You're right that fully writing out a pair consisting of (1) a rigorous statement of the problem and (2) a rigorous proof of the solution, would require quite a bit more work.
This assumes translational symmetry and clearly there is no translationally symmetric probability distribution. Nonetheless, if someone gave me this as a problem in the real world (for a big enough floor) I wouldn't hesitate to consider a uniform distribution for the position relative to the nearest line.
Interestingly, Geometric Probability Theory seems to take the line that it's expectation that's fundamental. In that case there's no difficulty with assuming translation invariance. But I need to read more of the book to find out, so take that with a pinch of salt.
Reminds me of a story that I heard about a probability prof trying to make the same point in a class using a more emphatic approach:
The prof brought a plate of spaghatti to class, threw the spaghatti on the floor, drew a square, counted the number of strands that cross the square and gave an estimate for pi!
randomdeterminism, since a square is not a collection of equally spaced parallel lines, I'm confused about how the professor's spaghetti can reveal an approximation of pi.
"A circle of diameter d will almost always cross the lines in two places."
Not "almost".
As for "little intuition as to why π appears" -- when I first learned of Buffon's needle I thought it was obvious, because a vertical needle of length d is sure to cross a line and a horizontal needle is sure not to, and the probability is obviously related to the angle, most likely to sin(θ).
"since a square is not a collection of equally spaced parallel lines"
Uh, seriously?
Post a Comment
<< Home