xxiv. Buffon's Needle

Problem (Buffon, 1777). A floor has parallel lines at distance $d$. A needle of length $\ell$ is dropped at random. What is the probability that it crosses a line?

Answer. For a short needle ($\ell \le d$): $P=\frac{2\ell }{\pi d}$. Dropping $n$ needles and counting $h$ crossings gives the estimate $\pi \approx \frac{2\ell n}{dh}$.

Variant	Result
short needle, $\ell \le d$	$P=\frac{2\ell }{\pi d}$
long needle, $\ell >d$	$P=1+\frac{2}{\pi }\left(\frac{\ell }{d}(1-\sqrt{1-d^2/{\ell }^2})-\arcsin \frac{d}{\ell }\right)$
expected number of crossings, any $\ell$	$\frac{2\ell }{\pi d}$
Buffon’s noodle: any rigid curve of length $L$	expected crossings $\frac{2L}{\pi d}$, whatever its shape
Barbier’s theorem	every convex curve of constant width $w$ has perimeter $\pi w$
estimating $\pi$ with $n$ throws, $\ell =d$	relative standard error $\approx 0.95/\sqrt{n}$: six digits need about $10^{12}$ throws
Laplace’s grid (two families of lines, cells $a\times b$, $\ell <\min (a,b)$)	$P=\frac{2\ell (a+b)-{\ell }^2}{\pi ab}$

const double PI = acos(-1.0);
 
double buffonProb(double l, double d) {             // probability that a needle of length l crosses a line (spacing d)
    if (l <= d) return 2 * l / (PI * d);
    double r = d / l;
    return 1 + 2 / PI * (l / d * (1 - sqrt(1 - r * r)) - asin(r));
}
 
// Monte Carlo estimate of pi. The direction is sampled by rejection from the unit disk, so pi is never used.
double estimatePi(long long n, double l, double d, mt19937_64& rng) {
    uniform_real_distribution<double> U(-1, 1), X(0, d / 2);
    long long hits = 0;
    for (long long i = 0; i < n; i++) {
        double ux, uy, r2;
        do { ux = U(rng); uy = U(rng); r2 = ux * ux + uy * uy; } while (r2 > 1 || r2 == 0);
        double s = fabs(uy) / sqrt(r2);              // |sin theta| of a uniform direction
        hits += X(rng) <= l / 2 * s;                 // centre-to-nearest-line distance vs half the vertical extent
    }
    return 2 * l * n / (d * hits);                   // valid for l <= d
}

Proof: the crossing probability, both cases

By symmetry let $x\in [0,d/2]$ be the distance from the needle’s centre to the nearest line and $\theta \in [0,\pi /2]$ its acute angle with the lines; both are uniform and independent. The needle crosses iff $x\le \frac{\ell }{2}\sin \theta$. Hence
$P=\frac{2}{\pi }{\int }_0^{\pi /2}\min (1,\frac{\ell }{d}\sin \theta )d\theta .$
If $\ell \le d$ the minimum is always the second term and $P=\frac{2}{\pi }\cdot \frac{\ell }{d}{\int }_0^{\pi /2}\sin \theta d\theta =\frac{2\ell }{\pi d}$. If $\ell >d$, let ${\theta }_0=\arcsin (d/\ell )$; the integrand is $\frac{\ell }{d}\sin \theta$ on $[0,{\theta }_0]$ and $1$ after, giving $\frac{2}{\pi }(\frac{\ell }{d}(1-\cos {\theta }_0)+\frac{\pi }{2}-{\theta }_0)$ with $\cos {\theta }_0=\sqrt{1-d^2/{\ell }^2}$, which is the formula. The code’s sampler draws $(\pm |\sin \theta |)$ of a uniform direction because a uniform point of the unit disk has a uniform angle. Checked: closed form against Simpson integration of the integral for $\ell /d\in [0.05,5]$, and the Monte Carlo estimate within $4$ standard errors.

Proof: Buffon's noodle and Barbier's theorem

Let $E(L)$ be the expected number of crossings of a rigid segment of length $L$ thrown at random. Cutting a segment into two pieces, each piece is itself thrown uniformly, and crossings add (a crossing at the joint has probability $0$), so by linearity of expectation $E(a+b)=E(a)+E(b)$. $E$ is monotone, so $E(L)=cL$. A polygonal curve is a union of segments, each thrown uniformly, so its expected crossings are $c$ times its length; a rectifiable curve is a limit of inscribed polygons and the crossing counts converge, so the same holds. A circle of diameter $d$ crosses the lines exactly twice with probability $1$, so $c\cdot \pi d=2$, $c=\frac{2}{\pi d}$. For $\ell \le d$ a needle crosses at most once, so its crossing probability equals its expected crossings $\frac{2\ell }{\pi d}$, re-deriving Buffon’s formula.

Barbier. A convex curve of constant width $w$, thrown on lines at spacing $w$, crosses exactly twice with probability $1$ (its projection orthogonal to the lines is an interval of length exactly $w$). So $2=\frac{2P}{\pi w}$ and the perimeter is $P=\pi w$ (the Reuleaux triangle included).

Error. The number of hits is binomial with $p=\frac{2\ell }{\pi d}$; $\hat{p}$ has relative standard deviation $\sqrt{(1-p)/(np)}$, and $\hat{\pi }=\frac{2\ell }{d\hat{p}}$ has the same relative error to first order. For $\ell =d$, $p=2/\pi$ and $\sqrt{(1-2/\pi )/(2/\pi )}\approx 0.95$. Lazzarini’s 1901 claim of $\frac{355}{113}$ from 3408 throws is far beyond this accuracy (it stopped at a lucky moment).

Laplace’s grid. The needle misses both families iff it misses each. With independent uniform offsets in $x$ and $y$ and angle $\theta$, the vertical extent $\ell \sin \theta$ must fit in $b$ and the horizontal $\ell \cos \theta$ in $a$: $P(\text{miss})=\frac{2}{\pi }{\int }_0^{\pi /2}(1-\frac{\ell \cos \theta }{a})(1-\frac{\ell \sin \theta }{b})d\theta =1-\frac{2}{\pi }(\frac{\ell }{a}+\frac{\ell }{b}-\frac{{\ell }^2}{2ab})$, using $\int \cos =\int \sin =1$ and $\int \sin \theta \cos \theta =\frac{1}{2}$. The complement is the stated formula.

Related notes

• Randomized Algorithms (Monte Carlo)
• Root Finding and Integration
• Probability and Expectation