P6.6.2Buffon's needle
A classic problem, first posed by Georges-Louis Leclerc, Comte de Buffon, can be stated as follows:
Given a plane ruled with parallel lines a distance \(d\) apart, what is the probability that a needle of length \(l \le d\) dropped at random onto the plane will cross a line?
The problem can be solved analytically, yielding the answer \(2l/\pi d\); show that this solution is given approximately for the case \(l=d\) using a random simulation (Monte Carlo) method: that is, by simulating the experiment with a large number of random orientations of the needle.
A related problem involves dropping a circular coin of radius \(a\) onto a floor consisting of square tiles, each of side \(d\). Show that the probability of a coin crossing a tile edge is \(1 - (d-2a)^2/d^2\) and confirm it with a Monte Carlo simulation.
Show solution
Let a needle land randomly such that the smallest distance of its centre to the nearest line is \(x\). Then the needle will cross the line if \(x \le \frac{l}{2}\sin\theta\) as shown in the diagram below:
\(\theta\) and \(x\) (\(0 \le \theta < \frac{\pi}{2}\), \(0 \le x < \frac{d}{2}\)) are independent random variables which we may select from a uniform distribution. For the simulation with \(l=d\), we are free to pick \(d\) to be any convenient value, so let \(d=1\).
import numpy as np
d, l = 1, 1
ntrials = 10000
x = d / 2 * np.random.random_sample(ntrials)
theta = np.pi / 2 * np.random.random_sample(ntrials)
p = np.sum(x <= l / 2 * np.sin(theta)) / ntrials
pexact = 2 * l / np.pi / d
print(f"d = {d:g}, l = {l:g}")
print(f"Monte Carlo estimate: {p:.5f}, exact answer: {pexact:.5f}")
The output is:
d = 1, l = 1
Monte Carlo estimate: 0.64450, exact answer: 0.63662