Enis Siniksaran

It has long been known that Buffon’s needle experiments can be used to estimate . Three main factors influence these experiments: grid shape, grid density, and needle length. In statistical literature, several experiments depending on these factors have been designed to increase the efficiency of the estimators of and to use all the information as fully as possible. We wrote the package BuffonNeedle to carry out the most common forms of Buffon’s needle experiments. In this article we review statistical aspects of the experiments, introduce the package BuffonNeedle, discuss the crossing probabilities and asymptotic variances of the estimators, and describe how to calculate them using Mathematica.

Introduction

Buffon’s needle problem is one of the oldest problems in the theory of geometric probability. It was first introduced and solved by Buffon [1] in 1777. As is well known, it involves dropping a needle of length at random on a plane grid of parallel lines of width units apart and determining the probability of the needle crossing one of the lines. The desired probability is directly related to the value of , which can then be estimated by Monte Carlo experiments. This point is one of the major aspects of its appeal. When is treated as an unknown parameter, Buffon’s needle experiments can be seen as valuable tools in applying the concepts of statistical estimation theory, such as efficiency, completeness, and sufficiency. For instance, in order to obtain better estimators of , Kendall and Moran [2] and Diaconis [3] examine several aspects of the problem with a long needle (). Morton [4] and Solomon [5] provide the general extension of the problem. Perlman and Wishura [6] investigate a number of statistical estimation procedures for for the single, double, and triple grids. In their study, they show that moving from single to double to triple grid, the asymptotic variances of the estimators get smaller and hence more efficient estimators can be obtained. Wood and Robertson [7] introduce the concept of grid density and provide an alternative idea. They show that Buffon’s original single grid is actually the most efficient if the needle length is held constant (at the distance between lines on the single grid) and the grids are chosen to have equal grid density (i.e., equal length of grid material per unit area). In [8], Wood and Robertson investigate the ways of maximizing the information in Buffon’s experiments.

We organize this article as follows. In the first three sections, we review Buffon’s experiments on single, double, and triple grids and their statistical issues. In the next section, we introduce the features of the package BuffonNeedle. The functions in the package implement Monte Carlo experiments for the three types of grids. The results of each experiment are given in a table and in a picture. When the number of the needles thrown on each grid is large, very nice pictures exhibit the interface between chance and necessity. In the last two sections, we describe how to calculate the crossing probabilities in single- and double-grid experiments and the asymptotic variances of the estimators for each grid using Mathematica.

Single-Grid Experiment

The single-grid form is Buffon’s well-known original experiment. A plane (table or floor) has parallel lines on it at equal distances from each other. A needle of length () is thrown at random on the plane. Figure 1 shows a single grid with two needles of length representing two possible outcomes. The probabilities of crossing zero lines and one line are

(1)

where and . These results can be found in many probability and statistics textbooks, for instance [5, 9, 10]. They are also explained in the “Calculating the Crossing Probabilities in Single and Double Grids” section of this article.

Figure 1. Buffon’s needles on a single grid.

From equation (1), we can write

(2)

Let be the number of times in independent tosses that the needle crosses any line. Then the proportion of crossings , a point estimator of , becomes . Hence, we can write the point estimator of in equation (2) as

(3)

The random variable is binomially distributed with the parameters and . is the uniformly minimum variance unbiased estimator (UMVUE). Furthermore, it is the maximum likelihood estimator (MLE) of and hence has 100% asymptotic efficiency in this experiment [6]. The variance of is then

(4)

which is minimized by taking as close as possible to 1. Choosing needle length () ensures this purpose. In this case, the variance of becomes

(5)

In Buffon’s experiments, the parameter of main interest is rather than . The estimator of this parameter, , is called Buffon’s estimator and can be obtained from equation (3) as

(6)

It can also be expressed in terms of

(7)

where is the number of times in tosses that the needle does not cross any line. Using equation (6) or (7) and Monte Carlo methods, we can obtain empirical estimates of for various values of . The best estimate is expected at (). Standard theory [11] ensures that Buffon’s estimator is an asymptotically unbiased, 100% efficient estimator of . Applying the delta method shows that its asymptotic variance is

(8)

which is, as expected, minimized at . For this value of , the asymptotic variance of is

(9)

If it is evaluated at , we have

(10)

Double-Grid Experiment

In the double-grid experiment, also called the Laplace extension of Buffon’s problem, a plane is covered with two sets of parallel lines where one set is orthogonal to the other.

Figure 2. Buffon’s needles on a double grid.

In Figure 2, we see a double-grid plane and three needles of length crossing zero, one, and two lines. These crossing probabilities are

(11)

Let be the number of times in tosses that the needle crosses exactly lines (). Perlman and Wichura [6] showed that the random variable is distributed binomially with the parameters and and is completely sufficient for where is . They also showed that the random variable

(12)

is the UMVUE and has 100% asymptotic efficiency with the variance

(13)

As in the case of a single grid, the variance of is minimized by , or equivalently by . Replacing with in the right-hand side of equation (12), we have

(14)

Then Buffon’s estimator, , can be expressed as

(15)

which can be used to obtain empirical estimates of . By the delta method, we can obtain the asymptotic variance of as

(16)

which is minimized at . For this value of , it becomes

(17)

When evaluated at , it is

(18)

Compare the last equation with equation (10). Buffon’s estimator in the double-grid experiment is times as efficient as that in the single-grid experiment.

Triple-Grid Experiment

In the triple-grid experiment, a plane is covered with equilateral triangles of altitude and hence of side .

Figure 3. Buffon’s needles on a triple grid.

Figure 3 shows a triple-grid plane and four needles of length crossing zero, one, two, and three lines. In [7], the crossing probabilities are given as

(19)

Let denote the number of times in tosses that the needle crosses exactly lines (). For this experiment, Perlman and Wichura [6] investigated the random variable which is distributed binomially with the parameters and where . They proposed, among others, the following unbiased estimator of as a function of

(20)

By replacing with , as in the other experiments, we obtain the same estimator as a function of

(21)

The variance of is

(22)

As in the cases of the single- and double-grid experiments, the variance of is minimized by taking ().

From equation (21), Buffon’s estimator can be written as

(23)

For this experiment, the asymptotic variance of Buffon’s estimator is

(24)

For and , it is

(25)

Comparing this with equations (10) and (18), we can infer that Buffon’s estimator in the triple-grid experiment is times as efficient as in the double-grid experiment and times as efficient as in the single-grid experiment (see Table 1). Now, we can conclude that when we increase the complexity of the grid, we can obtain tighter estimators of . Wood and Robertson [7] investigated this conclusion. They introduced the notion of grid density, which is the average length of grid in a unit area and showed that when the experiments are standardized, Buffon’s estimator in a single grid is the most efficient. In their approach, when , the single grid has unit grid density, the double grid has grid density of two, and the triple grid has grid density of three. Hence, the standardization of experiments corresponds to in the single grid, in the double grid and, finally, in the triple grid. Replacing these values of in equations (8), (16), and (24) and evaluating them at yields the values of given in Table 2. As Wood and Robertson claimed, the tightest estimator is obtained in the single-grid experiment.

Grid Type Single (r=1) Double (r=1) Triple (r=1); AVar(pi^^) 5.63/n 0.466/n 0.015781/n
Table 1. Asymptotic variances of Buffon’s estimator for three grids.
Grid Type Single (r=1) Double (r=1/2) Triple (r=1/3); AVar(pi^^) 5.63/n 7.85/n 5.91/n
Table 2. Asymptotic variances of Buffon’s estimator for three standardized grids.

The Package

The BuffonNeedle package is designed to throw needles on single, double, and triple grids. Copy the file BuffonNeedle.m (see Additional Material) into the Mathematica AddOns Applications folder. The following command loads the program.

There are three functions in this package: , , and . Here, is the number of needles and is the ratio of needle length to grid height (i.e., ), where can be any integer, while is a real number on the interval .

implements a single-grid Buffon’s experiment. It gives a table showing the number and frequency ratios of the two possible outcomes, together with the theoretical probabilities and the estimate of defined in equation (7). The function also gives a picture of the simulation results. In the picture, the midpoints of the needles crossing any line are colored red, while those of needles crossing no line are colored green. The functions and carry out similar processes for double and triple grids, respectively. In the picture of a double-grid experiment, the midpoints of the needles are colored green, blue, and red to show the three possible outcomes of zero, one, and two crossings. The estimate of in this experiment is defined in equation (15). As in the other two cases, in a triple-grid experiment carried out by the function , the four possible outcomes of zero, one, two, and three crossings are represented by four different colors of the midpoints of the needles. The estimate of given in the table is defined in equation (23).

For each grid, as gets larger, it could be expected that the difference between the estimated and actual values of would get smaller. You can also check some statistical results discussed in the previous sections by trying different values of . Additionally, for large values of , very nice pictures that exhibit the interface between randomness and determinism can be obtained. Some examples for various values of and are given below.

Calculating the Crossing Probabilities in Single and Double Grids

In this section, we show how to calculate the crossing probabilities in single- and double-grid experiments using Mathematica.

Single-Grid Probabilities

In the single-grid experiment, two independent random variables with uniform distribution are defined to determine the relative position of the needle to the lines: the distance of the needle’s midpoint to the closest line and the acute angle formed by the needle (or its extension) and the line (Figure 4). It is seen that can take any value between 0 and and can take any value between 0 and . The density functions of and are then given by

Since and are independent, the joint density function is the product of the density function of alone and the density function of alone:

for , .

From Figure 4, it is clear that the needle crosses the line when . The probability of this event is then

As there are two possible outcomes in the single-grid experiment, the probability that the needle does not cross any line is given by

which can alternatively be calculated by

The probabilities and can be written as a function of and as in equation (1).

Figure 4. The random variables in the single-grid experiment.

Double-Grid Probabilities

In the double-grid experiment, three independent random variables with uniform distribution can be defined to determine the relative position of the needle to the lines: the distance of the needle’s midpoint to the closest horizontal line, the distance of the needle’s midpoint to the closest vertical line, and the acute angle formed by the needle and the horizontal line, as in Figure 5. It is seen that and can take any value between 0 and and can take any value between 0 and . The density functions of , , and are given by

As in the case of the single-grid experiment, the joint density function of , , and is the product of the density functions of , , and :

for , , .

In the double-grid experiment, there are four possible outcomes:

  • The needle crosses a horizontal line while not crossing a vertical line.
  • The needle crosses a vertical line while not crossing a horizontal line.
  • The needle crosses both a vertical line and a horizontal line or, equivalently, the needle crosses two lines.
  • The needle crosses neither a vertical line nor a horizontal line or, equivalently, the needle crosses no line.

The needle crosses a horizontal line but does not cross a vertical line when and . The probability of this event is given by

The needle crosses a vertical line but does not cross a horizontal line when and . The probability of this event is given by

Thus, the probability that the needle crosses exactly one line is

The needle crosses both the vertical line and the horizontal line when and . The probability of this event is

Finally, the needle crosses neither the vertical line nor the horizontal line when and . The probability of this event is

The probabilities , , and can be written as functions of and , as in equation (11).

Figure 5. The random variables in the double-grid experiment.

Delta Method and Asymptotic Variance

Let a random variable be a function of the random variable , that is, . When the function is nonlinear, it may not be possible to compute the true mean and the true variance of . One can, however, calculate estimates of the true mean and true variance. The delta method is a very useful way to find such estimates [12, 13] and is based on the Taylor expansion about the mean of . Let the mean of be and the variance . Then the Taylor expansion of the function about to the third term is

(26)

Taking the expectation of both sides, we obtain the approximate mean of as

(27)

From the well-known identity of statistics

(28)

the approximate variance, also called asymptotic variance, of is

(29)

Thus, we can say that the random variable is distributed with the approximate mean and the approximate variance .

Buffon’s estimator is a nonlinear function of the random variable (); hence, the delta method can be used to find its asymptotic variance. From the previous sections, for each grid, we know and . Then, in equation (29), substituting , , and from equations (5), (13), and (22), we can obtain the asymptotic variances of in equations (8), (16), and (24) for each grid.

Alternatively, asymptotic variances of can be computed as follows [7, 11]

(30)

Here is the Fisher information number, given by

(31)

where is the probability that the needle crosses lines. These probabilities given in equations (1), (11), and (19) actually define a list for each grid as follows:

From equations (30) and (31), one can define the following functions to obtain the asymptotic variances:

For each grid, therefore, the asymptotic variances are

Substituting and factoring the expressions, we have

which were previously given in equations (8), (16), and (24), respectively. For and , we obtain the same values given in Table 1 for each grid.

For the standardized experiments of Wood and Robertson [7], we can obtain the asymptotic variances given in Table 2 by substituting , , and for single, double, and triple grids, respectively.

Acknowledgments

I would like to thank the reviewers whose comments led to a substantial improvement in this article. I would also like to thank my colleague, M. H. Satman, for creating some of the functions in the package BuffonNeedle. Thanks to Dr. Aylin Aktukun for reading and commenting on numerous versions of this manuscript. This work is supported by the Scientific Research Projects Unit of Istanbul University.

References

[1] G. L. Buffon, “Essai d’arithmétique morale,” Histoire naturelle, générale, et particulière, Supplément 4, 1777 pp. 685-713.
[2] M. G. Kendall and P. A. P. Moran, Geometrical Probability, New York: Hafner, 1963.
[3] P. Diaconis, “Buffon’s Problem with a Long Needle,” Journal of Applied Probability, 13, 1976 pp. 614-618.
[4] R. A. Morton, “The Expected Number and Angle of Intersections Between Random Curves in a Plane,” Journal of Applied Probability, 3, 1966 pp. 559-562.
[5] H. Solomon, Geometric Probability, Philadelphia: Society for Industrial and Applied Mathematics, 1978.
[6] M. D. Perlman and M. J. Wichura, “Sharpening Buffon’s Needle,” American Statistician, 29(4), 1975 pp. 157-163.
[7] G. R. Wood and J. M. Robertson, “Buffon Got It Straight,” Statistics and Probability Letters, 37,1998 pp. 415-421.
[8] G. R. Wood and J. M. Robertson, “Information in Buffon Experiments,” Journal of Statistical Planning and Inferences, 66,1998 pp. 21-37.
[9] M. R. Spiegel, Probability and Statistics, Schaum’s Outline of Probability and Statistics, New York: McGraw-Hill, 1975 pp. 67-68.
[10] J. V. Uspensky, Introduction to Mathematical Probability, New York: McGraw-Hill, 1937, p. 252.
[11] C. R. Rao, Linear Statistical Inference and Its Applications, 2nd ed., New York: Wiley & Sons, 1973.
[12] G. W. Oehlert, “A Note on the Delta Method,” American Statistician, 46, 1992 pp. 27-29.
[13] J. A. Rice, Mathematical Statistics and Data Analysis, 2nd ed., Belmont, CA: Duxbury Press, 1994 p. 149.
E. Siniksaran, “Throwing Buffon’s Needle with Mathematica,” The Mathematica Journal, 2011. dx.doi.org/doi:10.3888/tmj.11.1-4.

Additional Material

BuffonNeedle.m

Available at www.mathematica-journal.com/data/uploads/2011/11/BuffonNeedle.m.

About the Author

Enis Siniksaran is an assistant professor at Istanbul University, Department of Econometrics. His research interests include geometric approaches to statistical methods, robust statistical methods, and the methodology of econometrics. He has been working with Mathematica since 1998. For details on his recent work dealing with the geometry of classical test statistics, in which all symbolic and numerical computations and graphical work are done using Mathematica, see library.wolfram.com/infocenter/Articles/5962.

Enis Siniksaran
Istanbul Universitesi, Iktisat Fak., Ekonometri Bolumu
Beyazt, 34452, Istanbul, Turkey
saran@istanbul.edu.tr