5.2.2 Example: Approximating π

5.2.2  Example: Approximating π

More than 200 years before Metropolis coined the name “Monte Carlo method,” George-Louis Leclerc (Comte de Buffon) communicated several problems to the Academy of Sciences in Paris, including the following.7 If a needle of length l is dropped at random on the middle of a horizontal surface ruled with parallel lines a distance d > l apart, what is the probability that the needle will cross one of the lines? Today, this is known as the problem of Buffon’s needle. To solve it, consider Exhibit 5.1.

Exhibit 5.1: To derive the probability of a needle crossing a line, we describe the positioning of the needle relative to nearby lines with a random vector that has components a ∈ [0,d) and θ ∈ [0,π).

The positioning of the needle relative to nearby lines is described by a random vector with components a ∈ [0,d) and θ ∈ [0,π). The random vector (a, θ) is uniformly distributed on the region [0,d) × [0,π). Accordingly, it has PDF

[5.1]

Let X be a random variable for the number of lines crossed in a single drop of the needle. With d > l, a line will be crossed if and only if a < l sin(θ), so we have:

[5.2]

[5.3]

[5.4]

In this solution, Pierre-Simon Laplace perceived8 an amusing, if inefficient, means of approximating the number π. Suppose Buffon’s experiment is performed with m tosses of the needle. During those tosses the needle is observed to cross a line C times. We have

[5.5]

so the ratio C/m is an unbiased estimator for Pr(X = 1). Substituting this in [5.4] yields the biased estimator for π

[5.6]

In 1864, Captain O. C. Fox performed this experiment three times to occupy himself while recovering from wounds.9 His results are shown in Exhibit 5.2.

Exhibit 5.2: Results of Fox’s needle-dropping experiments.

Fox’s results illustrate two important issues for the Monte Carlo method.

1. After obtaining a poor approximation for π in his first experiment, Fox modified his subsequent experiments by applying a slight rotary motion to the ruled surface between drops. He did this to eliminate any bias arising from his position while dropping the needle. His approximations in subsequent experiments were markedly improved. This same need to eliminate bias exists today with computer implementations of the Monte Carlo method, although biases now arise from inappropriate pseudorandom number generators instead of posture.
2. In his third experiment, Fox used a 5-inch needle and spaced the lines on the surface just 2 inches apart. Now, the needle could cross as many as three lines in a single toss. In 590 tosses, Fox obtained 939 line crossings. Doing so entailed little more effort than his first two experiments, but it yielded a better approximation for π.10 Fox’s innovation was a precursor of today’s variance reduction techniques.