Getting pi by dropping needles on the floor

Rule a floor with parallel lines, evenly spaced. Nothing curved is involved at any stage, which is what makes the result worth the trouble. Take a needle exactly as long as the gap between lines. Drop it, from a height, with no attempt at aim. Note whether it comes to rest crossing a line. Repeat.

The proportion that cross approaches $2/\pi \approx 0.6366$. So the count can be inverted to estimate $\pi$ itself, using nothing but a floor, a needle, and patience.

$$\pi \approx \frac{2 \times \text{needles dropped}}{\text{needles crossing}}$$

Which is a strange thing for a floor to know. There is no circle in the setup. There is no curve of any kind — the needle is straight, the floorboards are straight, and the only quantities involved are lengths and a count.

Georges-Louis Leclerc, Comte de Buffon, posed the problem in 1733 and published it in 1777, in a work otherwise concerned with natural history — one of several occasions on which a constant turned up where nobody had put one.

Where the circle is hiding #

The circle is in the angle.

A needle’s position, once it lands, is fully described by two numbers: the distance $d$ from its centre to the nearest line, and the angle $\theta$ it makes with the lines. Everything else is irrelevant — which line it is near, where along the line it sits, none of it affects whether it crosses.

Take the needle’s length and the line spacing both to be 1. The needle reaches a distance $\tfrac{1}{2}\sin\theta$ perpendicularly from its centre in each direction. So it crosses a line exactly when

$$d \le \tfrac{1}{2}\sin\theta.$$

Now plot the two coordinates against each other. The angle runs from $0$ to $\pi$ and the distance from $0$ to $\tfrac12$, so every possible landing is a point in a rectangle of area $\pi/2$. The crossings are the points under a half sine wave.

The area under the curve is

$$\int_0^{\pi}\tfrac{1}{2}\sin\theta \, d\theta = 1,$$

and the area of the whole rectangle is $\pi/2$. Since both coordinates are uniformly distributed, the probability of crossing is the ratio:

$$P = \frac{1}{\pi/2} = \frac{2}{\pi}.$$

There is the circle. It arrived with $\sin\theta$, which is what a circle looks like from the side, and it arrived because the needle can land at any orientation — and “any orientation” is a statement about a circle of directions, whether or not one is drawn.

That is worth generalising, because it is one of the more reliable diagnostic rules in mathematics. Whenever $\pi$ appears in a problem with no visible circle, something in the problem is free to rotate. The $4/\pi$ in front of a square wave is the same phenomenon: the coefficients come from integrating over a full period, and a period is a lap. Angles integrated over their full range produce $\pi$ the way lengths integrated over an interval produce the interval’s length. It is not a coincidence and it is not deep; it is what rotation costs.

Notice also that the probability calculation is an area under a curve divided by another area. The integral is doing the work, and the randomness is only a means of sampling it.

It converges, slowly #

The estimate does improve as more needles are dropped.

How fast? Like every Monte Carlo method, the error shrinks in proportion to $1/\sqrt{N}$. To gain one decimal place, the number of trials must increase a hundredfold.

That is bad. Four thousand needles gets roughly two correct digits. A million would get about three. Getting to the ten digits that Archimedes-style polygon methods reached by hand in the sixteenth century would require something on the order of $10^{20}$ needle drops, which at one drop per second is longer than the universe has existed.

So Buffon’s needle is a genuinely terrible way to compute $\pi$, and it is important to say so, because it is often presented as though it were a clever technique rather than a beautiful curiosity. Every method of computing $\pi$ that anyone actually uses is deterministic and converges exponentially faster.

There is a famous cautionary tale attached. In 1901 Mario Lazzarini reported an experiment with 3,408 tosses yielding $\pi \approx 355/113$, accurate to six decimal places. That is far better than $1/\sqrt{N}$ permits — the result is around a thousand times more accurate than the method can support. The consensus is that the trial count was chosen after the fact, so that stopping at exactly the right moment would produce the famous approximation $355/113$ that Lazzarini already had in mind. It is a nice demonstration that a result matching a known answer is not thereby validated.

The estimate is not even centred on the answer #

There is a second problem with the method, subtler than the slowness and rarely mentioned alongside it. The quantity the needles measure is not $\pi$. It is $2/\pi$.

The crossing proportion is an honest estimator of $2/\pi$: run the experiment many times and the average of the proportions lands on $0.6366\ldots$ exactly, with no systematic error in either direction. But the answer wanted is $\pi$, and getting it requires taking a reciprocal — and averaging and inverting do not commute.

Reciprocation is convex, and a convex function applied to a spread-out quantity returns more than the function of its average. So the average of $2n/c$ across many experiments sits above $\pi$, and it does so for every finite number of drops. The bias shrinks as the sample grows — roughly like $1/n$, faster than the $1/\sqrt n$ noise, which is why it goes unnoticed — but at no point does it vanish. An experimenter running the procedure a thousand times and averaging the thousand answers converges on a number slightly larger than $\pi$, not on $\pi$.

The extreme case makes the mechanism plain. Drop three needles and suppose none crosses. The estimate is $6/0$, which is not a large number but no number at all. The estimator has positive probability of being infinite, and a quantity that is sometimes infinite has no finite average — which is the honest version of “biased upward”. Only when the chance of zero crossings becomes negligible does the average become finite at all.

None of this matters much in practice, because the bias is buried far beneath the noise. It matters as an illustration of something that does: an unbiased measurement of one quantity is not an unbiased measurement of a function of it. Estimating a rate and reporting a lifetime, estimating a variance and reporting a standard deviation, estimating a probability and reporting odds — each is the same manoeuvre, and each moves the answer by a little more than the arithmetic suggests.

How much noise, exactly #

The $1/\sqrt N$ has been quoted twice now without the constant in front of it, and the constant is worth having, because every numerical claim in the last two sections rests on it and it takes two lines.

Each drop is a coin flip with probability $p = 2/\pi$, so the crossing count $c$ has variance $np(1-p)$. The estimate is $\hat\pi = 2n/c$; propagating that spread through the reciprocal gives a relative standard deviation of

$$\frac{\sigma_{\hat\pi}}{\pi} = \sqrt{\frac{1-p}{np}} = \frac{0.7555}{\sqrt n}.$$

One number then reproduces everything asserted above. At the hundred and twenty needles of the opening figure it is $6.9\%$, or $\pi \pm 0.22$ — which makes an estimate of $2.89$ an unremarkable draw rather than a poor one. At four thousand it is $1.2\%$, or $\pi \pm 0.038$, which is the two digits claimed. At a million it is $\pi \pm 0.0024$. Ten correct digits needs $n \approx 5.7 \times 10^{19}$, which is where the $10^{20}$ came from. Forty thousand simulated runs of four thousand drops give a spread of $0.0377$ against the $0.0375$ predicted, and the same expression pins the bias of the previous section at $\pi(1-p)/np$ — at four hundred drops that is $+0.0045$, and forty thousand runs at that size average $3.1461$, high by exactly that.

There is a design consequence buried in the formula, and it justifies a choice made in this essay’s first paragraph and never remarked on. The relative error falls as $p$ rises, so the best needle is the one that crosses most often — and for a needle no longer than the gap, $p = 2L/\pi d$ is largest when $L = d$. The needle is exactly as long as the line spacing because that is the least noisy version of the experiment, not because it makes the formula tidy. Halving it takes $p$ to $1/\pi$ and the constant to $1.463$, very nearly doubling the standard deviation at the same number of drops — which is to say, throwing away about three-quarters of the work.

The needle need not be straight #

The best argument for the formula uses no integration at all, and it comes from letting go of the one feature that seemed essential.

Return to the crossing count rather than the crossing probability. Break the needle in the middle and bend it. Each half is now a shorter needle at its own angle, and the number of crossings of the whole is the sum of the crossings of the parts — a line crossed by the bent object is crossed by one piece or the other. Expected values add whether or not the things added are independent, so the expected crossing count of the bent needle is the sum of the two halves’ expected counts.

Keep breaking. Any curve at all, smooth or jagged, is a limit of short segments joined end to end, and its expected number of crossings is the sum of theirs. Each tiny segment is so short that it crosses at most once, so for a segment the expected count and the crossing probability are the same number — and that number is proportional to its length. Therefore, for any shape:

$$\mathbb{E}[\text{crossings}] = c \cdot (\text{length}),$$

with one constant $c$ for every curve there is. The shape has dropped out of the problem entirely.

Now fix the constant with a single well-chosen shape. Take a circle whose diameter equals the line spacing. Whatever way it falls, it meets the nearest line in exactly two points — never one, never three — so its expected crossing count is exactly 2, with no averaging required and no uncertainty to speak of. Its length is $\pi$ times the spacing. Setting $2 = c \cdot \pi$ gives $c = 2/\pi$, and the needle formula follows for a straight needle as a special case of a result proved with a round one.

This is Barbier’s argument, and it is a small marvel. The circle that was hiding in the integral has been dragged out and made the load-bearing object, the calculus has disappeared, and the reason $\pi$ appears is now unmissable: it was smuggled in as the circumference of the one shape whose answer could be read off without any work. The same trick — pick the instance where the unknown constant is free — recurs throughout integral geometry, and it is why a curve of constant width has a circumference that does not depend on its shape either.

What the picture cannot show #

The scatter of needles shows a proportion and cannot show a rate. Eighty-three crossings out of a hundred and twenty gives $\pi \approx 2.89$, which looks respectable until it is compared with what four thousand needles buys: about two correct digits. The picture gives no sense at all of how slowly that improves, and the slowness is the essay’s main point about the method.

It is equally silent about the bias. A frame showing traces that stray further above $\pi$ than below is suggestive, but the asymmetry it displays is a property of the ensemble of all possible runs, and any drawing shows a handful of them. Five traces cannot distinguish a systematically off-centre estimator from five runs that happened to wander upward, and no number of extra traces would settle it by eye.

Nor can it show the independence assumption, which is where real experiments go wrong. Needles dropped by a human hand are not independent — there is a preferred orientation, a preferred landing region, and a tendency to stop when the answer looks good. Lazzarini’s 1901 result is the standard cautionary tale, and nothing in a picture of needles would reveal that the trial count had been chosen after the fact.

The ladder from here #

Rungs above: the short-needle and long-needle cases separated properly, with the long-needle formula that involves an arcsine. Buffon–Laplace, with a grid of lines in both directions. Integral geometry and Crofton’s formula, of which this is the simplest instance. Importance sampling, and how Monte Carlo is made less slow. Variance reduction. Markov chain Monte Carlo. Quasi-random sequences, which beat $1/\sqrt{N}$ by giving up randomness. The Metropolis algorithm and its origin in the same Los Alamos work. And the deterministic integral this method is approximating, where the same quantity is computed exactly.

Randomness as a computational tool #

What Buffon’s needle genuinely demonstrates is the idea underneath all Monte Carlo methods: a deterministic quantity can be computed by taking the average of a random process designed to have that quantity as its mean.

The integral here is easy and nobody needs needles to evaluate it; rectangles would do, and faster. But the technique does not care about dimension, and that is where it earns its place. Deterministic numerical integration in twenty dimensions is hopeless — a grid with ten points per axis has $10^{20}$ cells. Monte Carlo’s error is $1/\sqrt{N}$ regardless of dimension. It is slow everywhere and equally slow everywhere, which in high dimensions makes it the only thing that works.

This was recognised at Los Alamos in the 1940s, where Stanisław Ulam — the same one who later doodled a spiral of primes — and John von Neumann developed the method for neutron diffusion calculations, on problems with far too many dimensions for grids. Ulam’s account is that the idea came to him while playing solitaire during an illness, wondering what the chances of winning were and realising that dealing out a hundred hands would answer it faster than the combinatorics would.

The name came from the casino in Monaco where Ulam’s uncle borrowed money to gamble.

The method’s reputation has since inverted. In 1946 it was a desperate expedient for problems that admitted no other attack; today it is the default for high-dimensional integration across physics, finance and statistics, and the deterministic methods are the specialists. What changed was not the mathematics — the error still falls like $1/\sqrt N$, exactly as slowly as it did then — but the arithmetic of what a machine can do while nobody is watching.

The mirror #

The Galton board and Buffon’s needle are the two halves of the same idea, run in opposite directions.

In the Galton board, randomness is the input and a precise, predictable shape is the output — order assembled out of noise by aggregation. In Buffon’s needle, an exact constant is the target and randomness is the tool deliberately chosen to hit it.

Both work for the same underlying reason. A large number of independent trials has properties that no single trial has, and those properties are as sharp as anything in deterministic mathematics — provided the trials really are independent, and provided nobody chooses when to stop.