Buffon's needle problem
In probability theory, Buffon's needle problem is a question first posed in the 18th century by Georges-Louis Leclerc, Comte de Buffon:<ref>Histoire de l'Acad. Roy. des. Sciences (1733), 43–45; Histoire naturelle, générale et particulière Supplément 4 (1777), p. 46.</ref>
- Suppose we have a floor made of parallel strips of wood, each the same width, and we drop a needle onto the floor. What is the probability that the needle will lie across a line between two strips?
Buffon's needle was the earliest problem in geometric probability to be solved;<ref>Template:Cite journal</ref> it can be solved using integral geometry. The solution for the sought probability Template:Mvar, in the case where the needle length Template:Mvar is not greater than the width Template:Mvar of the strips, is
- <math>p=\frac{2}{\pi} \cdot \frac{l}{t}.</math>
This can be used to design a Monte Carlo method for approximating the number [[pi|Template:Pi]], although that was not the original motivation for de Buffon's question.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> The seemingly unusual appearance of [[pi|Template:Pi]] in this expression occurs because the underlying probability distribution function for the needle orientation is rotationally symmetric.
SolutionEdit
The problem in more mathematical terms is: Given a needle of length Template:Mvar dropped on a plane ruled with parallel lines Template:Mvar units apart, what is the probability that the needle will lie across a line upon landing?
Let Template:Mvar be the distance from the center of the needle to the closest parallel line, and let Template:Mvar be the acute angle between the needle and one of the parallel lines.
The uniform probability density function (PDF) of Template:Mvar between 0 and Template:Math is
- <math>f_X(x)=
\begin{cases} \dfrac{2}{t} &:\ 0 \le x \le \dfrac{t}{2}\\[4px] 0 &: \text{elsewhere.} \end{cases} </math>
Here, Template:Math represents a needle that is centered directly on a line, and Template:Math represents a needle that is perfectly centered between two lines. The uniform PDF assumes the needle is equally likely to fall anywhere in this range, but could not fall outside of it.
The uniform probability density function of Template:Mvar between 0 and Template:Math is
- <math>f_\Theta(\theta)=
\begin{cases} \dfrac{2}{\pi} &:\ 0 \le \theta \le \dfrac{\pi}{2}\\[4px] 0 &: \text{elsewhere.} \end{cases} </math>
Here, Template:Math represents a needle that is parallel to the marked lines, and Template:Math radians represents a needle that is perpendicular to the marked lines. Any angle within this range is assumed an equally likely outcome.
The two random variables, Template:Mvar and Template:Mvar, are independent,<ref>The problem formulation here avoids having to work with Regular conditional probability densities.</ref> so the joint probability density function is the product
- <math>f_{X,\Theta}(x,\theta)=
\begin{cases} \dfrac{4}{t\pi} &:\ 0 \le x \le \dfrac{t}{2}, \ 0 \le \theta \le \dfrac{\pi}{2}\\[4px] 0 &: \text{elsewhere.} \end{cases} </math>
The needle crosses a line if
- <math>x \le \frac {l}{2} \sin\theta.</math>
Now there are two cases.
Case 1: Short needle (Template:Math)Edit
Integrating the joint probability density function gives the probability that the needle will cross a line:
- <math>P = \int_{\theta=0}^\frac{\pi}{2} \int_{x=0}^{\frac{l}{2}\sin \theta} \frac{4}{t\pi}\,dx\,d\theta = \frac{2 l}{t\pi}.</math>
Case 2: Long needle (Template:Math)Edit
Suppose Template:Math. In this case, integrating the joint probability density function, we obtain:
- <math>\int_{\theta=0}^\frac{\pi}{2} \int_{x=0}^{m(\theta)} \frac{4}{t\pi}\,dx\,d\theta,</math>
where Template:Math is the minimum between Template:Math and Template:Math.
Thus, performing the above integration, we see that, when Template:Math, the probability that the needle will cross at least one line is
- <math>P = \frac{2l}{t\pi} - \frac{2}{t\pi}\left(\sqrt{l^2 - t^2} + t\arcsin \frac{t}{l} \right)+1</math>
or
- <math>P = \frac{2}{\pi} \arccos \frac{t}{l} + \frac{2}{\pi}\cdot\frac{l}{t} \left(1 - \sqrt{1 - \left( \frac t l \right)^2 } \right). </math>
In the second expression, the first term represents the probability of the angle of the needle being such that it will always cross at least one line. The right term represents the probability that the needle falls at an angle where its position matters, and it crosses the line.
Alternatively, notice that whenever Template:Mvar has a value such that Template:Math, that is, in the range Template:Math, the probability of crossing is the same as in the short needle case. However if Template:Math, that is, Template:Math the probability is constant and is equal to 1.
- <math>\begin{align}
P &= \left(\int_{\theta=0}^{\arcsin \frac{t}{l}} \int_{x=0}^{\frac{l}{2}\sin\theta} \frac{4}{t\pi}dxd{\theta}\right) + \left(\int_{\arcsin\frac{t}{l}}^\frac{\pi}{2} \frac{2}{\pi}d{\theta}\right) \\[6px] &= \frac{2l}{t\pi} - \frac{2}{t\pi}\left(\sqrt{l^2 - t^2} + t\arcsin \frac{t}{l}\right) + 1 \end{align}</math>
Using elementary calculusEdit
The following solution for the "short needle" case, while equivalent to the one above, has a more visual flavor, and avoids iterated integrals.
We can calculate the probability Template:Mvar as the product of two probabilities: Template:Math, where Template:Math is the probability that the center of the needle falls close enough to a line for the needle to possibly cross it, and Template:Math is the probability that the needle actually crosses the line, given that the center is within reach.
Looking at the illustration in the above section, it is apparent that the needle can cross a line if the center of the needle is within Template:Math units of either side of the strip. Adding Template:Math from both sides and dividing by the whole width Template:Mvar, we obtain Template:Math.
Now, we assume that the center is within reach of the edge of the strip, and calculate Template:Math. To simplify the calculation, we can assume that <math>l = 2</math>.
Let Template:Mvar and Template:Mvar be as in the illustration in this section. Placing a needle's center at Template:Mvar, the needle will cross the vertical axis if it falls within a range of Template:Math radians, out of Template:Pi radians of possible orientations. This represents the gray area to the left of Template:Mvar in the figure. For a fixed Template:Mvar, we can express Template:Mvar as a function of Template:Mvar: Template:Math. Now we can let Template:Mvar range from 0 to 1, and integrate:
- <math>\begin{align}
P_2 &= \int_0^1 \frac{2\theta(x)}{\pi}\,dx \\[6px] &= \frac{2}{\pi}\int_0^1 \cos^{-1}(x)\,dx \\[6px] &= \frac{2}{\pi}\cdot 1 = \frac{2}{\pi}. \end{align}</math>
Multiplying both results, we obtain Template:Math as above.
There is an even more elegant and simple method of calculating the "short needle case". The end of the needle farthest away from any one of the two lines bordering its region must be located within a horizontal (perpendicular to the bordering lines) distance of Template:Math (where Template:Mvar is the angle between the needle and the horizontal) from this line in order for the needle to cross it. The farthest this end of the needle can move away from this line horizontally in its region is Template:Mvar. The probability that the farthest end of the needle is located no more than a distance Template:Math away from the line (and thus that the needle crosses the line) out of the total distance Template:Mvar it can move in its region for Template:Math is given by
- <math>\begin{align}
P &= \frac{\displaystyle\int_0^\frac{\pi}{2} l\cos\theta \, d\theta}{\displaystyle\int_0^\frac{\pi}{2} t \, d\theta} \\[6px] &= \frac l t\cdot\frac{\displaystyle\int_0^\frac{\pi}{2} \cos\theta \, d\theta}{\displaystyle\int_0^\frac{\pi}{2} d\theta} \\[6px] &= \frac l t\cdot\frac{1}{\,\frac{\pi}{2}\,} \\[6px] &=\frac{2l}{t\pi}. \end{align}</math>
Without integralsEdit
The short-needle problem can also be solved without any integration, in a way that explains the formula for Template:Mvar from the geometric fact that a circle of diameter Template:Mvar will cross the distance Template:Mvar strips always (i.e. with probability 1) in exactly two spots. This solution was given by Joseph-Émile Barbier in 1860<ref>Template:Cite book</ref> and is also referred to as "Buffon's noodle".
Estimating Template:PiEdit
Template:Math.
In the first, simpler case above, the formula obtained for the probability Template:Mvar can be rearranged to
- <math>\pi = \frac{2l}{tP}.</math>
Thus, if we conduct an experiment to estimate Template:Mvar, we will also have an estimate for Template:Pi.
Suppose we drop Template:Mvar needles and find that Template:Mvar of those needles are crossing lines, so Template:Mvar is approximated by the fraction Template:Math. This leads to the formula:
- <math>\pi \approx \frac{2l\cdot n}{t h}.</math>
In 1901, Italian mathematician Mario Lazzarini performed Buffon's needle experiment. Tossing a needle 3,408 times, he obtained the well-known approximation Template:Sfrac for Template:Pi, accurate to six decimal places.<ref>Template:Cite journal</ref> Lazzarini's "experiment" is an example of confirmation bias, as it was set up to replicate the already well-known approximation of Template:Sfrac (in fact, there is no better rational approximation with fewer than five digits in the numerator and denominator, see also Milü), yielding a more accurate "prediction" of Template:Pi than would be expected from the number of trials, as follows: <ref name="Badger1994">Lee Badger, 'Lazzarini's Lucky Approximation of Template:Pi', Mathematics Magazine 67, 1994, 83–91.</ref>
Lazzarini chose needles whose length was Template:Sfrac of the width of the strips of wood. In this case, the probability that the needles will cross the lines is Template:Math. Thus if one were to drop Template:Mvar needles and get Template:Mvar crossings, one would estimate Template:Pi as
- <math>\pi \approx \frac 53 \cdot \frac nx</math>
So if Lazzarini was aiming for the result Template:Sfrac, he needed Template:Mvar and Template:Mvar such that
- <math>\frac{355}{113} = \frac 53 \cdot \frac nx,</math>
or equivalently,
- <math>x = \frac{113 n}{213}.</math>
To do this, one should pick Template:Mvar as a multiple of 213, because then Template:Math is an integer; one then drops Template:Mvar needles, and hopes for exactly Template:Math successes. If one drops 213 needles and happens to get 113 successes, then one can triumphantly report an estimate of Template:Pi accurate to six decimal places. If not, one can just do 213 more trials and hope for a total of 226 successes; if not, just repeat as necessary. Lazzarini performed Template:Nowrap trials, making it seem likely that this is the strategy he used to obtain his "estimate".
The above description of strategy might even be considered charitable to Lazzarini. A statistical analysis of intermediate results he reported for fewer tosses leads to a very low probability of achieving such close agreement to the expected value all through the experiment. This makes it very possible that the "experiment" itself was never physically performed, but based on numbers concocted from imagination to match statistical expectations, but too well, as it turns out.<ref name="Badger1994" />
Dutch science journalist Hans van Maanen argues, however, that Lazzarini's article was never meant to be taken too seriously as it would have been pretty obvious for the readers of the magazine (aimed at school teachers) that the apparatus that Lazzarini said to have built cannot possibly work as described.<ref name="vMaanen2018">Hans van Maanen, 'Het stokje van Lazzarini' (Lazzarini's stick), "Skepter" 31.3, 2018.</ref>
Laplace's extension (short needle case)Edit
Now consider the case where the plane contains two sets of parallel lines orthogonal to one another, creating a standard perpendicular grid. We aim to find the probability that the needle intersects at least one line on the grid. Let Template:Mvar and Template:Mvar be the sides of the rectangle that contains the midpoint of the needle whose length is Template:Mvar. Since this is the short needle case, Template:Math, Template:Math. Let Template:Math mark the coordinates of the needle's midpoint and let Template:Mvar mark the angle formed by the needle and the Template:Mvar-axis. Similar to the examples described above, we consider Template:Mvar, Template:Mvar, Template:Mvar to be independent uniform random variables over the ranges Template:Math, Template:Math, Template:Math.
To solve such a problem, we first compute the probability that the needle crosses no lines, and then we take its complement. We compute this first probability by determining the volume of the domain where the needle crosses no lines and then divide that by the volume of all possibilities, Template:Mvar. We can easily see that Template:Math.
Now let Template:Math be the volume of possibilities where the needle does not intersect any line. Developed by J.V. Uspensky,<ref name="Uspensky">J.V. Uspensky, 'Introduction to Mathematical Probability', 1937, 255.</ref>
- <math>V^* = \int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} F(\varphi)\,d\varphi</math>
where Template:Math is the region where the needle does not intersect any line given an angle Template:Mvar. To determine Template:Math, let's first look at the case for the horizontal edges of the bounding rectangle. The total side length is Template:Mvar and the midpoint must not be within Template:Math of either endpoint of the edge. Thus, the total allowable length for no intersection is Template:Math or simply just Template:Math. Equivalently, for the vertical edges with length Template:Mvar, we have Template:Math. The ± accounts for the cases where Template:Mvar is positive or negative. Taking the positive case and then adding the absolute value signs in the final answer for generality, we get
- <math>F(\varphi) =(a - l\cos\varphi)(b - l\sin\varphi) = ab - bl \cos \varphi - al|\sin \varphi|+ \tfrac{1}{2}l^2|\sin 2\varphi|.</math>
Now we can compute the following integral:
- <math>V^* = \int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} F(\varphi)\,d\varphi = \pi ab-2bl-2al+l^2 .</math>
Thus, the probability that the needle does not intersect any line is
- <math>\frac{V^*}{V}= \frac{\pi ab-2bl-2al+l^2}{\pi a b} = 1 - \frac{2l(a+b)-l^2}{\pi a b}.</math>
And finally, if we want to calculate the probability, Template:Mvar, that the needle does intersect at least one line, we need to subtract the above result from 1 to compute its compliment, yielding
- <math>P = \frac{2l(a+b)-l^2}{\pi a b}</math>.
Comparing estimators of Template:PiEdit
As mentioned above, Buffon's needle experiment can be used to estimate Template:Pi. This fact holds for Laplace's extension too since Template:Pi shows up in that answer as well. The following question then naturally arises and is discussed by E.F. Schuster in 1974.<ref name="estimatorComp">E. F. Schuster, Buffon's Needle Experiment, The American Mathematical Monthly, 1974, 29-29.</ref> Is Buffon's experiment or Laplace's a better estimator of the value of Template:Pi? Since in Laplace's extension there are two sets of parallel lines, we compare Template:Mvar drops when there is a grid (Laplace), and Template:Math drops in Buffon's original experiment.
Let Template:Mvar be the event that the needle intersects a horizontal line (parallel to the Template:Mvar-axis)
- <math> x =
\begin{cases} 1 &: \text{intersection occurs}\\ 0 &: \text{no intersection} \end{cases} </math> and let Template:Mvar be the event that the needle intersects a vertical line (parallel to the Template:Mvar-axis)
- <math> y =
\begin{cases} 1 &: \text{intersection occurs}\\ 0 &: \text{no intersection} \end{cases} </math>
For simplicity in the algebraic formulation ahead, let Template:Math such that the original result in Buffon's problem is Template:Math. Furthermore, let Template:Math drops.
Now let us examine Template:Math for Laplace's result, that is, the probability the needle intersects both a horizontal and a vertical line. We know that
- <math>P(AB) = 1 - P(AB') - P(A'B) - P(A'B').</math>
From the above section, Template:Math, or the probability that the needle intersects no lines is
- <math>P(A'B') = 1 - \frac{2l(a+b)-l^2}{\pi a b} = 1 - \frac{2l(4l)-l^2}{4 l^2 \pi} = 1 - \frac{7}{4\pi} .</math>
We can solve for Template:Math and Template:Math using the following method:
- <math>\begin{align}
P(A) &= \frac{1}{\pi} = P(AB) + P(AB') \\[4px] P(B) &= \frac{1}{\pi} = P(AB) + P(A'B). \end{align}</math>
Solving for Template:Math and Template:Math and plugging that into the original definition for Template:Math a few lines above, we get
- <math> P(AB) = 1 - 2\left(\frac{1}{\pi}-P(AB)\right) - \left(1 - \frac{7}{4\pi}\right) = \frac{1}{4\pi}</math>
Although not necessary to the problem, it is now possible to see that Template:Math. With the values above, we are now able to determine which of these estimators is a better estimator for Template:Pi. For the Laplace variant, let Template:Mvar be the estimator for the probability that there is a line intersection such that
- <math>\hat{p} = \frac{1}{100}\sum_{n=1}^{100}\frac{x_n+y_n}{2}</math>.
We are interested in the variance of such an estimator to understand the usefulness or efficiency of it. To compute the variance of Template:Mvar, we first compute Template:Math where
- <math>\operatorname{Var}(x_n + y_n) = \operatorname{Var}(x_n) +\operatorname{Var}(y_n) + 2\operatorname{Cov}(x_n,y_n).</math>
Solving for each part individually,
- <math>\begin{align}
\operatorname{Var}(x_n) = \operatorname{Var}(y_n) &= \sum_{i = 1}^2 p_i\bigl(x_i-\mathbb{E}(x_i)\bigr)^2 \\[6px] &= P(x_i=1)\left(1-\frac{1}{\pi}\right)^2 + P(x_i=0)\left(0-\frac{1}{\pi}\right)^2 \\[6px] &= \frac{1}{\pi}\left(1-\frac{1}{\pi}\right)^2 + \left(1-\frac{1}{\pi}\right)\left(-\frac{1}{\pi}\right)^2 = \frac{1}{\pi}\left(1-\frac{1}{\pi}\right). \\[12px]
\operatorname{Cov}(x_n,y_n) &= \mathbb{E}(x_ny_n) - \mathbb{E}(x_n)\mathbb{E}(y_n) \end{align}</math>
We know from the previous section that
- <math>\mathbb{E}(x_ny_n) = P(AB) = \frac{1}{4\pi}</math>
yielding
- <math>\operatorname{Cov}(x_n,y_n) = \frac{1}{4\pi} - \frac{1}{\pi}\cdot\frac{1}{\pi} = \frac{\pi-4}{4\pi^2} < 0</math>
Thus,
- <math> \operatorname{Var}(x_n+y_n) = \frac{1}{\pi}\left(1-\frac{1}{\pi}\right) + \frac{1}{\pi}\left(1-\frac{1}{\pi}\right) + 2\left(\frac{\pi-4}{4\pi^2}\right) = \frac{5\pi - 8}{2\pi^2} </math>
Returning to the original problem of this section, the variance of estimator Template:Mvar is
- <math>\operatorname{Var}(\hat{p}) = \frac{1}{200^2}(100)\left(\frac{5\pi - 8}{2\pi^2}\right) \approx 0.000\,976.</math>
Now let us calculate the number of drops, Template:Mvar, needed to achieve the same variance as 100 drops over perpendicular lines. If Template:Math then we can conclude that the setup with only parallel lines is more efficient than the case with perpendicular lines. Conversely if Template:Mvar is equal to or more than 200, than Buffon's experiment is equally or less efficient, respectively. Let Template:Mvar be the estimator for Buffon's original experiment. Then,
- <math> \hat{q} = \frac{1}{M}\sum_{m=1}^M x_m </math>
and
- <math> \operatorname{Var}(\hat{q}) = \frac{1}{M^2}(M)\operatorname{Var}(x_m) = \frac{1}{M}\cdot\frac{1}{\pi}\left(1-\frac{1}{\pi}\right) \approx \frac{0.217}{M}</math>
Solving for Template:Mvar,
- <math> \frac{0.217}{M} = 0.000\,976 \implies M \approx 222.</math>
Thus, it takes 222 drops with only parallel lines to have the same certainty as 100 drops in Laplace's case. This isn't actually surprising because of the observation that Template:Math. Because Template:Mvar and Template:Mvar are negatively correlated random variables, they act to reduce the total variance in the estimator that is an average of the two of them. This method of variance reduction is known as the antithetic variates method.
See alsoEdit
ReferencesEdit
BibliographyEdit
- Template:Cite journal
- Template:Cite journal
- Template:Cite book
- Template:Cite journal
- Schroeder, L. (1974). "Buffon's needle problem: An exciting application of many mathematical concepts". Mathematics Teacher, 67 (2), 183–6.
- Uspensky, James Victor. "Introduction to mathematical probability." (1937).
External linksEdit
- Buffon's Needle Problem at cut-the-knot
- Math Surprises: Buffon's Noodle at cut-the-knot
- MSTE: Buffon's Needle
- Buffon's Needle Java Applet
- Estimating PI Visualization (Flash)
- Buffon's needle: fun and fundamentals (presentation) at slideshare
- Animations for the Simulation of Buffon's Needle by Yihui Xie using the R package animation
- 3D Physical Animation by Jeffrey Ventrella
- {{#invoke:citation/CS1|citation
|CitationClass=web }}