Buffon's Needle
From Math Images
(46 intermediate revisions not shown.) | |||
Line 1: | Line 1: | ||
- | {{Image Description | + | {{Image Description Ready |
|ImageName=Buffon's Needle | |ImageName=Buffon's Needle | ||
|Image=BuffonNeedle 700.gif | |Image=BuffonNeedle 700.gif | ||
- | |ImageIntro=The Buffon's Needle problem is a mathematical method of approximating the value of pi <math>(\pi = 3.1415...) </math>involving repeatedly dropping needles on a sheet of lined paper and observing how often the needle | + | |ImageIntro=The Buffon's Needle problem is a mathematical method of approximating the value of pi <math>(\pi = 3.1415...) </math>involving repeatedly dropping needles on a sheet of lined paper and observing how often the needle intersects a line. |
- | |ImageDescElem=The method was first used to approximate | + | |ImageDescElem=The method was first used to approximate π by Georges-Louis Leclerc, the Comte de Buffon, in 1777. Buffon was a mathematician, and he wondered about the probability that a needle would lie across a line between two wooden strips on his floor. To test his question, he apparently threw bread sticks across his shoulder and counted when they crossed a line. |
+ | Calculating the probability of an intersection for the Buffon's Needle problem was the first solution to a problem of <balloon title="A probability problem is ''geometric'' if the probability can be computed as the ratio of two areas or volumes."> geometric probability</balloon>. The solution can be used to design a method for approximating the number π. | ||
- | Subsequent mathematicians have used | + | Subsequent mathematicians have used this method with needles instead of bread sticks, or with computer simulations. We will show that when the distance between the lines is equal the length of the needle, an approximation of π can be calculated using the equation |
<math> | <math> | ||
- | \pi \approx {2 | + | \pi \approx {2\times \mbox{number of drops} \over \mbox{number of hits}} |
</math> | </math> | ||
- | |ImageDesc=====Will the Needle | + | |ImageDesc=====Will the Needle Intersect a Line?==== |
- | [[Image: | + | [[Image:situation2.jpg|right]] |
- | [[Image:willtheneedlecross | + | [[Image:willtheneedlecross ps10.jpg|right]] |
- | To prove that the Buffon's Needle experiment will give an approximation of | + | To prove that the Buffon's Needle experiment will give an approximation of π, we can consider which positions of the needle will cause an intersection. Since the needle drops are random, there is no reason why the needle should be more likely to intersect one line than another. As a result, we can simplify our proof by focusing on a particular strip of the paper bounded by two horizontal lines. |
+ | The variable θ is the acute angle made by the needle and an imaginary line parallel to the ones on the paper. Since we are considering the case where the interline distance equals l, we might as well take that common distance to be 1 unit. | ||
+ | Finally, ''d'' is the distance between the center of the needle and the nearest line. Also, there is no reason why the needle is more likely to fall at a certain angle or distance, so we can consider all values of θ and d equally probable. | ||
- | + | We can extend line segments from the center and tip of the needle to meet at a right angle. A needle will cut a line if the length of the green arrow, ''d'', is shorter than the length of the leg opposite θ. More precisely, it will intersect when | |
+ | <math> d \leq \left( \frac{1}{2} \right) \sin(\theta). \ </math> | ||
- | + | See case 1, where the needle falls at a relatively small angle with respect to the lines. Because of the small angle, the center of the needle would have to fall very close to one of the horizontal lines in order to intersect it. In case 2, the needle intersects even though the center of the needle is far from both lines because the angle is so large. | |
- | + | ||
- | + | ||
- | + | ||
- | See case 1, where the needle falls at a relatively small angle with respect to the lines. | + | |
====The Probability of an Intersection==== | ====The Probability of an Intersection==== | ||
- | + | In order to show that the Buffon's experiment gives an approximation for π, we need to show that there is a relationship between the probability of an intersection and the value of π. If we graph the possible values of θ along the X axis and ''d'' along the Y, we have the <balloon title="In probability theory, the sample space of an experiment is the set of all possible outcomes."> sample space</balloon> for the trials. In the diagram below, the sample space is contained by the dashed lines. | |
- | + | ||
- | + | Each point on the graph represents some combination of an angle and a distance that a needle might occupy. | |
[[image:Minigraph.jpg]] | [[image:Minigraph.jpg]] | ||
- | There will be an intersection if <math> | + | There will be an intersection if <math> d \leq \left ( \frac{1}{2} \right ) \sin(\theta) \ </math>, which is represented by the blue region. The area under this curve represents all the combinations of distances and angles that will cause the needle to intersect a line. Since each of these combinations is equally likely, the probability is proportional to the area – that's what makes this a geometric probability problem. The area under the blue curve, which is equal to 1/2 in this case, can found by evaluating the integral |
- | <math>\int_0^{\frac {\pi}{2}} \frac{1}{2} \sin(\theta) d\theta</math> | + | <math>\int_0^{\frac {\pi}{2}} \frac{1}{2} \sin(\theta) d\theta = \frac {1}{2}</math> |
Then, the area of the sample space can be found by multiplying the length of the rectangle by the height. | Then, the area of the sample space can be found by multiplying the length of the rectangle by the height. | ||
Line 47: | Line 46: | ||
<math> \frac {1}{2} * \frac {\pi}{2} = \frac {\pi}{4}</math> | <math> \frac {1}{2} * \frac {\pi}{2} = \frac {\pi}{4}</math> | ||
- | The | + | The probability is equal to the ratio of the two areas in this case because each possible value of θ and ''d'' is equally probable. The probability of an intersection is |
- | <math>P_{hit} = \cfrac{ \frac{1}{2} }{\frac{\pi}{4}} = \frac {2}{\pi} = .6366197. | + | <math>P_{hit} = \cfrac{ \frac{1}{2} }{\frac{\pi}{4}} = \frac {2}{\pi} = .6366197\ldots.\qquad \mbox{and thus} \qquad \pi = \frac 2{P_{hit}}.</math> |
+ | Thus, in order to approximate <math>\pi</math>, it remains only to approximate <math>P_{hit}</math>. | ||
- | |||
- | + | ====Using Random Samples to Approximate π==== | |
- | + | The original goal of the Buffon's needle method, approximating π, can be achieved by using probability to solve for π. If a large number of trials is conducted, the proportion of times a needle intersects a line will be close to the probability of an intersection. That is, the number of line hits divided by the number of drops will equal approximately the probability of hitting the line. | |
- | + | <math>P_{hit} \approx \frac {\mbox{number of hits}}{\mbox{number of drops}} </math> | |
- | + | So, | |
- | + | <math> \pi = \frac{2}{P_{hit}} \approx \frac {2}{\frac {\mbox{number of hits}}{\mbox{number of drops}}} = \frac {2 * {\mbox{number of drops}}}{\mbox{number of hits}} </math> | |
- | + | ||
- | <math> \pi \approx \frac {2 * {\mbox{number of drops}}}{\mbox{number of hits}} </math> | + | |
====Watch a Simulation==== | ====Watch a Simulation==== | ||
- | http://mste.illinois.edu/reese/buffon/bufjava.html | + | <center>{{#iframe:http://mste.illinois.edu/reese/buffon/bufjava.html|405|500|thumb}}</center> |
|AuthorName=Wolfram MathWorld | |AuthorName=Wolfram MathWorld | ||
|SiteURL=http://mathworld.wolfram.com/BuffonsNeedleProblem.html | |SiteURL=http://mathworld.wolfram.com/BuffonsNeedleProblem.html | ||
Line 77: | Line 74: | ||
====Monte Carlo Methods==== | ====Monte Carlo Methods==== | ||
- | The Buffon's needle problem was the first recorded use of a Monte Carlo method. These methods employ repeated random sampling to approximate a probability, instead of computing the probability directly. Monte Carlo calculations are especially useful when the nature of the problem makes a direct calculation impossible or unfeasible, and they have become more common as the introduction of computers makes randomization less laborious. | + | The Buffon's needle problem was the first recorded use of a Monte Carlo method. These methods employ repeated random sampling to approximate a probability, instead of computing the probability directly. Monte Carlo calculations are especially useful when the nature of the problem makes a direct calculation impossible or unfeasible, and they have become more common as the introduction of computers makes randomization and conducting a large number of trials less laborious. |
- | + | π is an irrational number, which means that its value cannot be expressed exactly as a fraction a/b, where a and b are integers. This also means that a normal decimal repetition of pi is non-terminating and non-repeating, and mathematicians have been challenged with trying to determine increasingly accurate approximations. The timeline below shows the improvements in approximating π throughout history. In the past 50 years especially, improvements in computer capability allow more decimal places to be determined. Nonetheless, better methods of approximation are still desired. | |
- | [[Image:history of | + | [[Image:history of pi2.jpg|800px]] |
- | A recent study conducted the Buffon's Needle experiment to approximate | + | A recent study conducted the Buffon's Needle experiment to approximate π using computer software. The researchers administered 30 trials for each number of drops, and averaged their estimates for π. They noted the improvement in accuracy as more trials were conducted. |
[[Image:box1.jpg]] | [[Image:box1.jpg]] | ||
- | These results show that Buffon's Needle approximation is | + | These results show that the Buffon's Needle method approximation is relatively tedious. Compared to other computation techniques, Buffon's method is impractical because the estimates converge towards π rather slowly. Even when a large number of needles were dropped, this experiment gave a value of π that was inaccurate in the third decimal place. |
+ | |||
+ | Regardless of the impracticality of the Buffon's Needle method, the historical significance of the problem as a Monte Carlo method means that it continues to be widely recognized. | ||
====Generalization of the problem==== | ====Generalization of the problem==== | ||
- | [[Image:picture 1. | + | [[Image:picture 1.png|right]] |
+ | |||
+ | |||
+ | The Buffon’s needle problem has been generalized so that the probability of an intersection can be calculated for a needle of any length and paper with any spacing. For a needle shorter than the distance between the lines, it can be shown by a similar argument to the case where ''d'' = 1 and ''l'' = 1 that the probability of a intersection is <math> \frac {2*l}{\pi*d} </math>. Note that this expression agrees with the normal case, where ''l'' =1 and ''d'' =1, so these variables disappear and the probability is <math> \frac {2}{\pi} </math>. | ||
- | The | + | The generalization of the problem is useful because it allows us to examine the relationship between length of the needle, distance between the lines, and probability of an intersection. The variable for length is in the numerator, so a longer needle will have a greater probability of an intersection. The variable for distance is in the denominator, so greater space between lines will decrease the probability of an intersection. |
- | |||
To see how a longer needle will affect probability, follow this link: | To see how a longer needle will affect probability, follow this link: | ||
Line 105: | Line 106: | ||
====Needles in Nature==== | ====Needles in Nature==== | ||
- | Applications of the Buffon's Needle method are even found | + | Applications of the Buffon's Needle method are even found in nature. The Centre for Mathematical Biology at the University of Bath found uses of the Buffon's Needle algorithm in a recent study of ant colonies. The researchers found that an ant can estimate the size of an anthill by visiting the hill twice and noting how often it recrosses its first path during the second trip. |
[[Image:one ant track.jpg|right]] | [[Image:one ant track.jpg|right]] | ||
Line 111: | Line 112: | ||
Ants generally nest in groups of about 50 or 100, and the size of their nest preference is determined by the size of the colony. When a nest is destroyed, the colony must find a suitable replacement, so they send out scouts to find new potential homes. | Ants generally nest in groups of about 50 or 100, and the size of their nest preference is determined by the size of the colony. When a nest is destroyed, the colony must find a suitable replacement, so they send out scouts to find new potential homes. | ||
- | In the study, scout ants were provided with "nest cavities of different sizes, shapes, and configurations in order to examine preferences" [2]. From | + | In the study, scout ants were provided with "nest cavities of different sizes, shapes, and configurations in order to examine preferences" [2]. From observations that ants prefer nests of a certain size related to the number of ants in the colony, researchers were able to draw the conclusion that scout ants must have a method of measuring areas. |
A scout initially begins exploration of a nest by walking around the site to leave tracks. Then, the ant will return later and walk a new path that repeatedly intersects the first tracks. The first track will be laced with a chemical that causes the ant to note each time it crosses the original path. The researchers believe that these scout ants can calculate an estimate for the nest's area using the number of intersections between its two visits. | A scout initially begins exploration of a nest by walking around the site to leave tracks. Then, the ant will return later and walk a new path that repeatedly intersects the first tracks. The first track will be laced with a chemical that causes the ant to note each time it crosses the original path. The researchers believe that these scout ants can calculate an estimate for the nest's area using the number of intersections between its two visits. | ||
- | + | The ants can measure the size of their hill using a related and fairly intuitive method: If they are constantly intersecting their first path, the area must be small. If they rarely reintersects the first track, the area of the hill must be much larger so there is plenty of space for a non-intersecting second path. | |
+ | |||
+ | [[Image:willtheneedlecross ps4.jpg|left]] | ||
[[Image:Willtheneedlecross_ps5.jpg|left]] | [[Image:Willtheneedlecross_ps5.jpg|left]] | ||
- | This idea can be related back to the generalization of the problem by imagining if the parallel lines | + | ''"In effect, an ant scout applies a variant of Buffon's needle theorem: The estimated area of a flat surface is inversely proportional to the number of intersections between the set of lines randomly scattered across the surface."'' [7] |
+ | |||
+ | This idea can be related back to the generalization of the problem by imagining if the area between the lines was increased by making the parallel lines much further apart. A larger distance between the two lines would mean a much smaller probability of intersection. We can see in case 3 that when the distance between the lines is greater than the length of the needle, even very large angle won’t necessarily cause an intersection. | ||
- | + | This natural method of random motion allows the ants to gauge the size of their potential new hill regardless of its shape. Scout ants are even able to asses the area of a hill in complete darkness. The animals show that algorithms can be used to make decisions where an array of restrictions may prevent other methods from being effective. | |
- | + | COOL LINK! : http://www.youtube.com/watch?feature=player_embedded&v=sJVivjuMfWA | |
}} | }} | ||
Line 139: | Line 144: | ||
[7] http://math.tntech.edu/techreports/TR_2001_4.pdf | [7] http://math.tntech.edu/techreports/TR_2001_4.pdf | ||
- | | | + | |
+ | |Pre-K=No | ||
+ | |Elementary=No | ||
+ | |MiddleSchool=Yes | ||
+ | |HighSchool=Yes | ||
+ | |InProgress=No | ||
}} | }} |
Current revision
Buffon's Needle |
---|
Buffon's Needle
- The Buffon's Needle problem is a mathematical method of approximating the value of pi involving repeatedly dropping needles on a sheet of lined paper and observing how often the needle intersects a line.
Contents |
Basic Description
The method was first used to approximate π by Georges-Louis Leclerc, the Comte de Buffon, in 1777. Buffon was a mathematician, and he wondered about the probability that a needle would lie across a line between two wooden strips on his floor. To test his question, he apparently threw bread sticks across his shoulder and counted when they crossed a line.Calculating the probability of an intersection for the Buffon's Needle problem was the first solution to a problem of geometric probability. The solution can be used to design a method for approximating the number π.
Subsequent mathematicians have used this method with needles instead of bread sticks, or with computer simulations. We will show that when the distance between the lines is equal the length of the needle, an approximation of π can be calculated using the equation
A More Mathematical Explanation
Will the Needle Intersect a Line?
To prove that the Buffon's Needle experiment will give an approximation of π, we can consider which positions of the needle will cause an intersection. Since the needle drops are random, there is no reason why the needle should be more likely to intersect one line than another. As a result, we can simplify our proof by focusing on a particular strip of the paper bounded by two horizontal lines.
The variable θ is the acute angle made by the needle and an imaginary line parallel to the ones on the paper. Since we are considering the case where the interline distance equals l, we might as well take that common distance to be 1 unit. Finally, d is the distance between the center of the needle and the nearest line. Also, there is no reason why the needle is more likely to fall at a certain angle or distance, so we can consider all values of θ and d equally probable.
We can extend line segments from the center and tip of the needle to meet at a right angle. A needle will cut a line if the length of the green arrow, d, is shorter than the length of the leg opposite θ. More precisely, it will intersect when
See case 1, where the needle falls at a relatively small angle with respect to the lines. Because of the small angle, the center of the needle would have to fall very close to one of the horizontal lines in order to intersect it. In case 2, the needle intersects even though the center of the needle is far from both lines because the angle is so large.
The Probability of an Intersection
In order to show that the Buffon's experiment gives an approximation for π, we need to show that there is a relationship between the probability of an intersection and the value of π. If we graph the possible values of θ along the X axis and d along the Y, we have the sample space for the trials. In the diagram below, the sample space is contained by the dashed lines.
Each point on the graph represents some combination of an angle and a distance that a needle might occupy.
There will be an intersection if , which is represented by the blue region. The area under this curve represents all the combinations of distances and angles that will cause the needle to intersect a line. Since each of these combinations is equally likely, the probability is proportional to the area – that's what makes this a geometric probability problem. The area under the blue curve, which is equal to 1/2 in this case, can found by evaluating the integral
Then, the area of the sample space can be found by multiplying the length of the rectangle by the height.
The probability is equal to the ratio of the two areas in this case because each possible value of θ and d is equally probable. The probability of an intersection is
Thus, in order to approximate , it remains only to approximate .
Using Random Samples to Approximate π
The original goal of the Buffon's needle method, approximating π, can be achieved by using probability to solve for π. If a large number of trials is conducted, the proportion of times a needle intersects a line will be close to the probability of an intersection. That is, the number of line hits divided by the number of drops will equal approximately the probability of hitting the line.
So,
Watch a Simulation
Why It's Interesting
Teaching Materials
- There are currently no teaching materials for this page. Add teaching materials.
References
[1] http://www.maa.org/mathland/mathtrek_5_15_00.html
[2] http://mste.illinois.edu/reese/buffon/bufjava.html
[3] http://www.absoluteastronomy.com/topics/Monte_Carlo_method
[4] The Number Pi. Eymard, Lafon, and Wilson.
[5] Monte Carlo Methods Volume I: Basics. Kalos and Whitlock.
[6] Heart of Mathematics. Burger and Starbird
[7] http://math.tntech.edu/techreports/TR_2001_4.pdf
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.