From Buffon's Needle to Buffon's Noodle | Hacker News Reader

From Buffon's Needle to Buffon's Noodle

mbmccoy.dev

37 points_alternator_13 comments

I'm wary of asking questions (my curiosity is bounded), but what changes if you limit the range of allowed angles to multiples of, say, 10°? How about 90°, does pi go away then?

Author here. If I understand the question, the answer is that the average number of lines that the "noodle" intersects depends only on the length of the noodle. If you change the angles between the segments, the average stays the same.

So taking the limit of a large number of segments converging to a circle of diameter W leads to the result that the average number of intersections must be 2L/\pi.

I was thinking along these lines: suppose it's a needle, but it can't rotate. It always falls at the same angle. Then there's no noodle, and no apparent connection to circles. Is pi still involved? Next, suppose there are two perpendicular angles that are permitted, and the needle always falls at one of those. That means you can have square noodles, but rotations still aren't allowed, so the squares must always be aligned the same way, and the only suggestion of a circle is if you consider a square to be an approximation to a circle. Then three angles, hexagonal noodles. Does an approximation to pi therefore slowly creep in as you increase the sides on the polygon?

For the first question, the answer is just cos(\theta)*L/W, where theta is the angle off horizontal (assuming the floorboards are vertical). So a trig function shows up, if not pi.

If you don't allow rotations, but somehow still take a polygonal limit to circles, I suspect you'll end up with the same answer. But the limit is necessarily restricted relative to highly symmetric polygons going this route.

In general, rotational symmetry gives a ton of power to simplify the math, and leads to highly general results like arbitrary "noodles" having the same average crossing count as needles of the same length.

> Does an approximation to pi therefore slowly creep in as you increase the sides on the polygon?

Yes, under some assumptions. As the sibling comment points out, if there’s a single allowed angle theta then the expected number of intersections is cos(theta) * L/W (-pi/2 < theta < pi/2). You can get from this fact to the standard Buffon’s needle result by integrating wrt theta to find the average probability over thetas with a uniform distribution on (-pi/2 < theta < pi/2): \int 1/pi * cos(theta) * L/W d theta.

Now suppose you have two angles, theta_1 and theta_2. The expected number of intersections for each of them is as above, and if the needle falls at one or the other with equal probability then the overall expectation is 1/2 * cos(theta_1) * L/W + 1/2 * cos(theta_2) * L/W. Passing to the case with n distinct angles with equal probabilities we have \sum_i 1/n cos(theta_i) * L/W.

Now if we make the further assumption that the angles are evenly distributed over (-pi/2 < theta < pi/2), i.e. they are the angles of the sides of a regular n-gon, then we can interpret that sum as a Riemann sum. If we write it as

1/pi \sum_i pi/n cos(theta_i) * L/W

Then pi/n is the delta_i term in the riemann sum, and the limit is

lim_{n -> inf} 1/pi \sum_i pi/n cos(theta_i) * L/W = 1/pi \int cos(theta) * L/W d theta.

We can pull the L/W out, leaving \int_-pi/2^pi/2 cos(theta) d theta = sin(pi/2) - sin(-pi/2) = 2, giving the final result of 2/pi * L/W.

Essentially, as we increase the number of allowable angles we are approximating an integral of the cosine function (times constants) from -pi to pi, which is where the pi creeps in. The angles don’t need to be strictly evenly spaced for this to work—if they are independent randomly selected from the uniform distribution then it will also work, as you’re then performing a monte carlo integration.

Pretty neat! However, if you wanted to know the _probability_ of a noodle crossing any line in the long noodle case (L/W > 1), the expression is more complex (and I believe would require an integral) :).

It's interesting that the number of crossings is independent of whether L/W is less than or greater than 1, but the probability of crossings is equal to 2pi * L/W only in the short case. This makes sense since in the short case the noodle can at most cross a single line.

This is the crux of the observation. For needles of length less than W, the probability that it crosses a floorboard is equal to the average number of floorboards it crosses. (Exercise for the reader ;))

The point is that the "right" quantity to be considering for the problem is the average number crossings, since that naturally extends to curved noodles, lines of any length, and even circles. The number of crossings is also known as the Euler characteristic of the intersection, and there's a rather deep and beautiful theory of geometric probability that takes this as the jumping off point.

That's the menace of expected-value problems. They are easy-to-solve variants of more interesting hard-to-solve problems.

Is the probability actually more interesting though? I find the symmetry of this type of result extremely compelling, beautiful even. Buffon himself restricted his attention to the case where the needle was short enough that "probability" and "expectation" had the same answer. Put simply, math is best when complicated-seeming things suddenly become simple.

Why is the simulation always exactly 2 for a closed polygon, but has error for the almost-full circle?

I think it's because only the closed polygon is totationally symmetric, so you don't get errors from the edge case at the edge of the finite sample space. But I'm not sure.

The illustration is missing the more interesting visualization of how linearity of expectation applies to all possible rotations and translations of all segments of the needle/noodle. Each noodle is equivalent to a curve of discs, like a string of pearls. And those pearls do not even need to be connected!

The simulation is always 2 for the closed circle of width W. Actually if you run it enough, the simulation will occasionally end up not perfectly equal to 2 because it's a 50 sided polygon, not a true circle. ;)

But for a perfect circle of diameter W, it will alway hit exactly two vertical lines.

Very cool. I was expecting it to make circles bigger rather than making needles smaller. Take a near-circle consisting of N lines. As N tends to infinity, the near-circle would have a diameter close to N*L/π, so would touch N*L/πW + O(1) lines twice each.

That was a delicious read. I love this kind of mathematical writing.

Reply on news.ycombinator.com