View source for Antimatroid

{{no footnotes|date=March 2011}}
[[Image:Buffon needle.gif|right|frame|The ''a'' needle lies across a line, while the ''b'' needle does not.]]

In [[mathematics]], '''Buffon's needle problem''' is a question first posed in the 18th century by [[Georges-Louis Leclerc, Comte de Buffon]]:
:Suppose we have a [[floor]] made of [[Parallel (geometry)|parallel]] strips of [[wood]], each the same width, and we drop a [[Sewing needle|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; it can be solved using [[integral geometry]]. The solution, in the case where the needle length is not greater than the width of the strips, can be used to design a [[Monte Carlo method]] for approximating the number [[pi|π]].

== Solution ==
The problem in more mathematical terms is: Given a needle of length <math>l</math> dropped on a plane ruled with parallel lines ''t'' units apart, what is the probability that the needle will cross a line?

Let ''x'' be the distance from the center of the needle to the closest line, let ''θ'' be the acute angle between the needle and the lines.

The uniform [[probability density function]] of ''x'' between 0 and ''t'' /2 is
:<math>
\begin{cases}
\frac{2}{t} &:\ 0 \le x \le \frac{t}{2}\\
0 &: \text{elsewhere.}
\end{cases}
</math>

The uniform probability density function of θ between 0 and π/2 is
:<math>
\begin{cases}
\frac{2}{\pi} &:\ 0 \le \theta \le \frac{\pi}{2}\\
0 &: \text{elsewhere.}
\end{cases}
</math>

The two [[random variables]], ''x'' and ''θ'', are independent, so the [[Joint probability distribution|joint probability density function]] is the product
:<math>
\begin{cases}
\frac{4}{t\pi} &:\ 0 \le x \le \frac{t}{2}, \ 0 \le \theta \le \frac{\pi}{2}\\
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 ===
{{Cleanup|reason=the text in the gif should be directly on the wikitext, not in the gif|date=September 2013}} 
[[File:Buffon's (short) needle problem.gif|thumb|center|550px<!-- original size, because large animated GIFs cannot be thumbnailed -->|This GIF image describes the solution of Buffon's Needle Problem for the "short needle" case]]
Suppose <math>l \le t</math>.

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}^{(l/2)\sin\theta}  \frac{4}{t\pi}\,dx\,d\theta = \frac{2 l}{t\pi}.</math>

A particularly nice argument for this result can alternatively be given using "[[Buffon's noodle]]".

=== Case 2: Long needle ===
Suppose <math>l > t</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 <math>m(\theta) </math> is the minimum between
<math>(l/2)\sin\theta</math> and <math>t/2 </math>.

Thus, performing the above integration, we see that,
when <math>t < l</math>,
the probability that the needle will cross a line is

:<math>\frac{2 l}{t\pi} - \frac{2}{t\pi}\left\{\sqrt{l^2 - t^2} + t\sin^{-1}\left(\frac{t}{l}\right)\right\}+1</math>

or

:<math> \frac{2}{\pi} \cos^{-1}\frac{t}{l} + \frac{2}{\pi} \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.

== Using elementary calculus ==
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 <math>P</math> as the product of 2 probabilities: <math>P = P_1 \cdot P_2</math>, where <math>P_1</math> is the probability that the center of the needle falls close enough to a line for the needle to possibly cross it, and <math>P_2</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 <math>l / 2</math> units of either side of the strip. Adding <math>\frac{l}{2}+\frac{l}{2}</math> from both sides and dividing by the whole width <math>t</math>, we obtain <math>P_1 = \frac{l}{t}.</math>

[[File:Buffon's needle corrected.PNG|thumb|right|The red and blue needles are both centered at x. The red one falls within the gray area, contained by an angle of 2θ on each side, so it crosses the vertical line; the blue one does not. The proportion of the circle that is gray is what we integrate as the center ''x'' goes from 0 to 1]]

Now, we assume that the center is within reach of the edge of the strip, and calculate <math>P_2</math>. To simplify the calculation, we can assume that <math>l = 2</math>.

Let ''x'' and ''θ'' be as in the illustration in this section. Placing a needle's center at ''x'', the needle will cross the vertical axis if it falls within a range of 2θ radians, out of π radians of possible orientations. This represents the gray area to the left of ''x'' in the figure. For a fixed ''x'', we can express ''θ'' as a function of ''x'': <math>\theta\left(x\right) = \cos^{-1}\left(x\right)</math>. Now we can let x move from 0 to 1, and integrate:

:<math>P_2 = \int_0^1 \frac{2\theta(x)}{\pi}\,dx = \frac{2}{\pi}\int_0^1 \cos^{-1}(x)\,dx = \frac{2}{\pi}\cdot 1 = \frac{2}{\pi}.</math>

Multiplying both results, we obtain <math>P = P_1\cdot P_2 = \frac{l}{t}\frac{2}{\pi} = \frac{2 l}{t\pi}</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 <math>l\cos\theta</math> (where <math>\theta</math> 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 <math>t</math>. The probability that the farthest end of the needle is located no more than a distance <math>l\cos\theta</math> away from the line (and thus that the needle crosses the line) out of the total distance <math>t</math> it can move in its region for <math>0 \le \theta \le \pi/2</math> is given by

<math>P = \frac{\int_0^{\frac{\pi}{2}} l\cos\theta d\theta}{\int_0^{\frac{\pi}{2}} t d\theta} = \frac{l}{t}\frac{\int_0^{\frac{\pi}{2}} \cos\theta d\theta}{\int_0^{\frac{\pi}{2}} d\theta} = \frac{l}{t}\frac{1}{\frac{\pi}{2}}=\frac{2l}{t\pi}</math>, as above.

== Estimating π ==
In the first, simpler case above, the formula obtained for the probability <math>P</math> can be rearranged to: <math>\pi = \frac{2 l}{t P}</math>. Thus, if we conduct an experiment to estimate <math>P</math>, we will also have an estimate for π.

Suppose we drop ''n'' needles and find that ''h'' of those needles are crossing lines, so <math>P</math> is approximated by the fraction <math>h / n</math>. This leads to the formula:

:<math>\pi \approx \frac{2l\cdot n}{t h}.</math>

In 1901, Italian mathematician [[Mario Lazzarini]] performed the Buffon's needle experiment.  Tossing a needle 3408 times, he obtained the well-known estimate 355/113 for π, which is a very accurate value, differing from π by no more than 3×10<sup>−7</sup>. This is an impressive result, but is something of a cheat, as follows.

Lazzarini chose needles whose length was 5/6 of the width of the strips of wood.  In this case, the probability that the needles will cross the lines is <math>\frac{5}{3 \pi}</math>.  Thus if one were to drop ''n'' needles and get ''x'' crossings, one would estimate π as
:π ≈ 5/3 · ''n''/''x''.

π is very nearly 355/113; in fact, there is no better rational [[Pi#Numerical approximations|approximation]] with fewer than 5 digits in the numerator and denominator.  So if one had ''n'' and ''x'' such that:
:355/113 = 5/3 · ''n''/''x''
or equivalently,
:''x'' = 113''n''/213
one would derive an unexpectedly accurate approximation to π, simply because the fraction 355/113 happens to be so close to the correct value.  But this is easily arranged.  To do this, one should pick ''n'' as a multiple of 213, because then 113''n''/213 is an integer; one then drops ''n'' needles, and hopes for exactly ''x'' = 113''n''/213 successes.

If one drops 213 needles and happens to get 113 successes, then one can triumphantly report an estimate of π 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 3408 = 213 · 16 trials, making it seem likely that this is the strategy he used to obtain his "estimate".

==References==
* {{cite journal|doi = 10.2307/2690682|last = Badger|first = Lee|title=Lazzarini's Lucky Approximation of π|journal= Mathematics Magazine|volume=67|issue=2|date=April 1994|pages=83–91|jstor=2690682|publisher = Mathematical Association of America}}
* {{cite journal|last = Ramaley|first = J. F.|title = Buffon's Noodle Problem|journal = The American Mathematical Monthly|volume = 76|issue = 8|date=October 1969|pages = 916–918|doi = 10.2307/2317945|jstor = 2317945|publisher = Mathematical Association of America}}
* {{cite book|last = Mathai|first = A. M.|title = An Introduction to Geometrical Probability|year = 1999|publisher = Gordon & Breach|location = Newark|url = http://books.google.com/?id=FV6XncZgfcwC | isbn=978-90-5699-681-9 |page=5}}
* {{cite journal| last = Dell|first = Zachary| author2 = Franklin, Scott V.|title = The Buffon-Laplace needle problem in three dimensions|journal = Journal of Statistical Mechanics: Theory and Experiment|month = September| volume = 09| issue = 9| pages = 010| year = 2009| doi = 10.1088/1742-5468/2009/09/P09010| bibcode = 2009JSMTE..09..010D}}
* Schroeder, L. (1974). "Buffon's needle problem: An exciting application of many mathematical concepts". ''Mathematics Teacher'', 67 (2), 183–6.

==External links==
* [http://www.cut-the-knot.org/fta/Buffon/buffon9.shtml Buffon's Needle] at [[cut-the-knot]]
* [http://www.cut-the-knot.org/ctk/August2001.shtml Math Surprises: Buffon's Noodle] at [[cut-the-knot]]
* [http://www.mste.uiuc.edu/reese/buffon/buffon.html MSTE: Buffon's Needle]
* [http://www.angelfire.com/wa/hurben/buff.html Buffon's Needle Java Applet]
* [http://www.metablake.com/pi.swf Estimating PI Visualization (Flash)]
* [http://www.slideshare.net/cypztm/buffons-needle-fun-and-fundamentals Buffon's needle: fun and fundamentals (presentation)] at [[slideshare]]
* [http://animation.yihui.name/prob:buffon_s_needle Animations for the Simulation of Buffon's Needle] by Yihui Xie using the [[R (programming language)|R]] package [http://cran.r-project.org/package=animation animation]
* [http://www.ventrella.com/Buffon/index.html 3D Physical Animation Java Applet] by Jeffrey Ventrella
* {{cite web|last=Padilla|first=Tony|title=∏ Pi and Buffon's Needle|url=http://www.numberphile.com/pi/pi_matches.html|work=Numberphile|publisher=[[Brady Haran]]}}

[[Category:Applied probability]]
[[Category:Integral geometry]]
[[Category:Named probability problems]]