A randomized algorithm is said to give an (,)-approximation for the value of V if the output X of the algorithm satises P(|X V| ) .

(Chebyshev Inequality) If X is a random variable with mean and variance 2, then P(|X | a) ( ^2 /a^2 )for all a > 0. (1)

In this project, we want to estimate the value of through random sampling. First, consider the unit square S = {(x,y)|0 x 1,0 y 1}and the circle C = {(x,y)|(x1/2)2+(y 1/2)^2 1/4} which resides inside the unit square. Suppose that we sample n points from the unit square S, uniformly and independently. Let Xi be 1 if the ith sample falls into the circle C and 0 otherwise. Dene Sn = X1 ++ Xn.

(a) What is the PMF of Xi?

(b) Calculate the expectation of Xi.

(c) Calculate the mean and variance of Sn/ n . What happens as n grows to innity? Discuss what it means.

(d) Continuing from part (c), let = E[Sn/n] = / 4. The strong law of large numbers says that Sn n converges almost surely to as n . Using this fact, devise an estimator of the value of .

(e) By using the Chebyshev Inequality in (1), calculate the number of samples n that guarantees (,)-approximation of , where = 0.01 and = 0.01. You may want to use the fact p(1p) 0.25 for p [0,1].

(f) Implement the estimator in (d) by writing a computer program (using any language including C/C++/Java/MATLAB/Python/etc.)

(g) Does your estimator approach the true value of as the number of samples n grows? Plot the behavior of your estimator versus n and discuss the result.