Archive for Buffon’s needle

The answer is e, what was the question?!

Posted in Books, R, Statistics with tags , , , , , on February 12, 2016 by xi'an

Sceaux, June 05, 2011A rather exotic question on X validated: since π can be approximated by random sampling over a unit square, is there an equivalent for approximating e? This is an interesting question, as, indeed, why not focus on e rather than π after all?! But very quickly the very artificiality of the problem comes back to hit one in one’s face… With no restriction, it is straightforward to think of a Monte Carlo average that converges to e as the number of simulations grows to infinity. However, such methods like Poisson and normal simulations require some complex functions like sine, cosine, or exponential… But then someone came up with a connection to the great Russian probabilist Gnedenko, who gave as an exercise that the average number of uniforms one needs to add to exceed 1 is exactly e, because it writes as

\sum_{n=0}^\infty\frac{1}{n!}=e

(The result was later detailed in the American Statistician as an introductory simulation exercise akin to Buffon’s needle.) This is a brilliant solution as it does not involve anything but a standard uniform generator. I do not think it relates in any close way to the generation from a Poisson process with parameter λ=1 where the probability to exceed one in one step is e⁻¹, hence deriving  a Geometric variable from this process leads to an unbiased estimator of e as well. As an aside, W. Huber proposed the following elegantly concise line of R code to implement an approximation of e:

1/mean(n*diff(sort(runif(n+1))) > 1)

Hard to beat, isn’t it?! (Although it is more exactly a Monte Carlo approximation of

\left(1-\frac{1}{n}\right)^n

which adds a further level of approximation to the solution….)

Buffon needled R exams

Posted in Books, Kids, R, Statistics, University life with tags , , , , , , , on November 25, 2013 by xi'an

Here are two exercises I wrote for my R mid-term exam in Paris-Dauphine around Buffon’s needle problem. In the end, the problems sounded too long and too hard for my 3rd year students so I opted for softer questions. So recycle those if you wish (but do not ask for solutions!)

cannonball approximation to pi

Posted in Statistics with tags , , , , , on October 8, 2011 by xi'an

This year, my daughter started writing algorithms in her math class (she is in seconde, which could correspond to the 10th grade). The one she had to write down last weekend was Buffon’s neddle and the approximation of π by Monte Carlo (throwing cannon balls was not mentioned!). Here is the short R code I later wrote to show her the outcome (as the class has not yet learned a computer language):

n=10^6
counter=0
#uniforms over the unit square
ray=runif(n)^2+runif(n)^2
#proportion within the quarter circle
conv=cumsum((ray<1))/(1:n)
plot(conv,type="l",col="steelblue",ylim=c(pi/4-2/sqrt(n),
     pi/4+2/sqrt(n)),xlab="n",ylab="proportion")
abline(h=pi/4,col="gold3")

and here is an outcome of the convergence of the approximation to π/4:

Buffon versus Bertrand in R

Posted in R, Statistics with tags , , , on April 8, 2011 by xi'an

Following my earlier post on Buffon’s needle and Bertrand’s paradox, above are four outcomes corresponding to four different generations (among many) of the needle locations. The upper right-hand side makes a difference in the number of hits (out of 1000). The R code corresponding to this generation was made in the métro, so do not expect subtlety: Continue reading

When Buffon meets Bertrand

Posted in R, Statistics, Travel with tags , , , , , on April 7, 2011 by xi'an

When Peter Diggle gave his “short history” of spatial statistics this morning (I typed this in the taxi from Charles de Gaulle airport, after waiting one hour for my bag!), he started with a nice slide about Buffon’s needle (and Buffon’s portrait), since Julian Besag was often prone to give this problem as a final exam to Durham students (one of whom is responsible for the candidate’s formula). This started me thinking about how this was open to a Bertrand’s paradox of its own. Indeed, randomness for the needle throw can be represented in many ways:

  • needle centre uniformly distributed over the room (or the perpendicular to the boards) with a random orientation (with a provision to have the needle fit);
  • needle endpoint uniformly distributed over the room (again a uniform over the perpendicular is enough) with a random orientation (again with a constraint);
  • random orientation from one corner of the room and a uniform location of the centre on the resulting line (with constraints on both ends for the needle to fit);
  • random orientation from one corner of the room and a uniform location of one endpoint on the resulting line, plus a Bernoulli generation to decide on the orientation (with constraints on both ends for the needle to fit);
  • &tc.

I did not have time to implement those different generation mechanisms in R, but have little doubt they should lead to different probabilities of intersection between the needle and one of the board separations. I actually found a web-page at the University of Alabama Huntsville addressing this problem through exercises (plus 20,000 related entries! Including von MisesProbability, Statistics and Truth itself. A book I should read one of those days, following Andrew.). Note that each version corresponds to a physical mechanism. Thus that there is no way to distinguish between them. Had I time, I would also like to consider the limiting case when the room gets infinite as, presumably, some of those proposals would end up being identical.