Applied Mathematics
Vol.08 No.03(2017), Article ID:74541,5 pages
10.4236/am.2017.83022
Buffon’s Needle Algorithm to Estimate π
Chi-Ok Hwang1*, Yeongwon Kim2, Cheolgi Im1, Sunggeun Lee3
1Division of Liberal Arts and Sciences, GIST College, Gwangju, Korea
2Concentration of Electrical Engineering and Computer Science, GIST College, Gwangju, Korea
3Concentration of Physics, GIST College, Gwangju, Korea
Copyright © 2017 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: December 13, 2016; Accepted: February 28, 2017; Published: March 3, 2017
ABSTRACT
Buffon’s needle experiment was originally devised to get the value of . With the advent of computers, Buffon’s needle algorithm has been used pedagogically as an example of Monte Carlo methods in introduction classes, and there are many Buffon’s needle algorithm implementations available on the internet. However, for the calculation of , the exact value of is used in the programs for Buffon’s needle angle sampling, and hence the example is not demonstrated correctly. This brief note presents a random angle sampling algorithm for the Buffon’s needle. We then compare the Buffon’s needle and Hit-and-Miss integration algorithms using Monte Carlo laboriousness comparison, and find that the Hit-and-Miss algorithm is superior.
Keywords:
Buffon’s Needle, Monte Carlo, Angle Sampling
1. Introduction
Buffon’s needle experiment [1] was originally used to provide . Throwing a needle (see Figure 1) onto a flat plane with equally-spaced parallel lines, the probability that the needle touches the parallel line provides an estimate for is
(1)
and so
(2)
where is the probability, the length of the needle and the spacing with .
Here, we should note that the Buffon’s needle problem becomes an integration problem (see Figure 2) so the probability is just the ratio of areas.
Many variants of the original Buffon’s needle experiment [2] [3] [4] [5] [6] [7] have been developed. Kendall and Moran [2] and Diaconis [3] examined several aspects of the problem for a long needle ( ) and Siniksaran [7] used Mathematics to review various statistical aspects of the experiment.
With the advent of computers, Buffon’s needle has been pedagogically used as an example in Monte Carlo method introductory classes and many websites pro- vide Buffon’s needle algorithm implementations. However, in these programs, the value of is used for the random sampling of the needle angular direction. Thus is used to obtain the value of itself.
This note presents a sampling algorithm for the random direction of the needle that avoids using within the algorithm. We then compare the Buffon’s needle and the Hit-and-Miss integration algorithms using the common Monte Carlo algorithm comparison method, the time consumption (laboriousness) [8] .
Figure 1. Buffon’s needle algorithm with spacing and needle length .
Figure 2. Buffon’s needle problem can be converted to an integration problem.
2. Buffon’s Needle Algorithm
For random direction sampling of the needle, we use a square enclosing a tightly fitted circle (see Figure 3).
Since the directions of the random points inside the circle are uniform, we obtain uniform needle random directions.
3. Comparison with the Hit-and-Miss Algorithm
The Hit-and-Miss integration algorithm can also provide the value of . Using one quadrant of the circle circumscribed by a square (see Figure 4), we can obtain , where, is the probability of hitting the shaded area, when we generate a pair of random numbers to sample a random point inside of the square.
We use the common Monte Carlo algorithm comparison, time consumption (laboriousness): [8] where is the CPU time expended in calculating a single estimate and estimate variance. Figure 5 shows the log-log plot of the number of Monte Carlo steps v.s. the errors of the two algorithms, and Table 1 compare the two algorithms. The Hit-and-Miss algorithm is superior to the Buffon’s needle algorithm for calculation of #Math_28#, which seems reasonable given the Buffon’s needle algorithm requires more numerical operations for a Monte Carlo step. Of course, we can improve Buffon’s algorithm performance using a tighter non-constant proposed probability distribution for the acceptance-rejec- tion sampling method. Using quasi-Monte Carlo random numbers [9] for the angle sampling will also improve the convergence.
4. Conclusion
Buffon’s needle algorithm has been pedagogically used as an introduction to
Figure 3. Needle random direction sampling. After generating a ran- dom point inside the circle, we obtain the random direction vector for the needle.
Figure 4. Hit-and-Miss diagram. Using a pair of random num- bers, we obtain the probability of hitting inside of the marked quadrant.
Figure 5. Monte Carlo steps and estimation errors. The linear regression slopes for Buffon’s needle and Hit-and-Miss algorithms (solid and dotted lines res- pectively) are and with correlation coefficients and respectively.
Table 1. Time consumption of Buffon’s needle and Hit-and-Miss algorithm. Variances were obtained from 100 independent runs and the number of random walks per run was .
Monte Carlo methods. However, is used for needle angle sampling inside the original algorithm. This note presents a method for the needle angle sampling without using and make the Buffon’s needle algorithm a Monte Carlo method to estimate . We compared the Buffon’s needle and Hit-and-Miss integration algorithms and found that the Buffon’s needle algorithm is not superior to the Hit-and-Miss integration algorithm.
Acknowledgements
This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2012R1A1A2003025). Also, later this work was supported by the GIST Research Institute (GRI) in 2017. In addition, this research was a collaborative research project, supercomputing infrastructure service and application, supported by the Korea institute of science and technology information.
Cite this paper
Hwang, C.-O., Kim, Y., Im, C. and Lee, S. (2017) Buffon’s Needle Algorithm to Estimate π. Applied Ma- thematics, 8, 275-279. https://doi.org/10.4236/am.2017.83022
References
- 1. Buffon, G. (1777) Essai da’rithme’tique morale. Histoire Naturelle, Générale, et Particuliére, Supplément, 4, 685.
- 2. Morton, R.A. (1966) The Expected Number and Angle of Intersections between Random Curves in a Plane. Journal of Applied Probability, 3, 559-562. https://doi.org/10.1017/S0021900200114342
- 3. Diaconis, P. (1976) Buffon’s Problem with a Long Needle. Journal of Applied Probability, 13, 614-618.
- 4. Periman, M.D. and Wichura, M.J. (1975) Sharpening Buffon’s Needle. Amer. Stat, 29, 157.
- 5. Solomon, H. (1987) Geometric Probability. SIAM, Philadelphia.
- 6. Wood, G.R. and Robertson, J.M. (1998) Information in Buffon Experiments. Journal of Statistical Planning and Inferences, 66, 415-421.
- 7. Siniksaran, E. (2008) Throwing Buffon’s Needle with Mathematica. The Mathematical Journal, 11, 71.
- 8. Sobol, I.M. (1994) A Primer for the Monte Carlo Method. CRC Press, Washington DC.
- 9. Lemieux, C. (2009) Monte Carlo and Quasi-Monte Carlo Sampling. Springer-Verlag, New York.