Excercise Probabilistic Algorithm

1)  In our analysis of convergence, we saw that it is required to drop about six thousand needles on the floor to estimate pi within 0.01 nine times out of ten.  This was achieved by dropping needles that are half the width of the planks.  Show that we can improve this "algorithm" by dropping the needles twice as long and producing 2n/k as estimate of pi.  How many of these needles need we drop to have probability at least 90% of obtaining the correct value of pi within 0.01?

Solution

Buffon proved that the probability that a needle of length L will fall across a crack is 2L /( w pi )  when the planks are of width w, provided L <= w.  When the needles are half of the plank width L = w/2, the probability of the needles fall across a crack is 1/pi.  If we use the needles that are twice as long, that is, L = w, the probability will be 2/pi.  Therefore if we drop n needles and the number of the needles that cross cracks are k, k/n = 2/pi, then the estimate of pi is 2n/k.

To determine the number of needles that need to be dropped the have probability at least 90% of obtaining the correct value of pi within 0.01.  Table for normal distribution tells us that
Pr[ | X - E(X) | < 1.645 sqrt(Var(X)) ] =approx. 90%

We have  E(X) = 2/pi and  Var(X) = (2/pi) ( 1 - 2/pi ) / n.   It follows that
Pr[ |X - 2/pi| < e ] => 90% provided

e > 1.645 sqrt( (2/pi) (1 - 2/pi) / n )

n > 0.626 / e^2

now we are estimating 2/pi rather 1/pi hence the error e for estimating 2/pi corresponds to e/2 on an estimate for 1/pi.
e = 0.02  hence   n > 1565.  Ans

2)  Another probabilistic approach for estimating the value of pi is to use Monte Carlo integration to estimate the area of a quarter circle of radius 2.
pi = integrate(x=0 to 2)  sqrt( 4 - x^2) dx
How many random values of x must we use to have the probability at least 90% of obtaining the correct value of pi within 0.01?

3)  Write a computer program to simulate Buffon's experiment to estimate the value of pi. The challenge is that you are not allowed to use the value of pi in your program.  If you do not see why this is a diffulty, try it!