Let , , ,… be i.i.d random variables from some distribution with finite mean and finite variance .
As , let , we have and
Equivalently, let , we have and
- denotes Normal distribution with mean of and variance of .
Naturally CLT appears in questions that invovle sum or average of a large number of random variablse and especially when the questions only ask for an approximate answer.
Here are a few examples.
Suppose we have a fair coin and we flip it 400 times. What is the probability you will see 210 heads or more?
Let the outcome of each coin flip be a random variable . Thus we are dealing with the random variable . is te sume of a series of i.i.d Bernoulie trials, thus it follows Binomial distribution. So the exact answer is: which requires a program to calculate (Actually try implementing this, beware of roudoff errors and compare it against the approximate answer below.).
- is the notation for “n choose k”, which denotes the number of ways to choose k items from n items where order doesn’t matter.
We use CLT to easily get an approxmate answer quickly. First recognize that for each we have and . Then, is approximately . For , we have .
The 68-95-99.7 rule tells us that for a standard Normal distribution , the probability of the random variable taking value more than 1 standard deviation away from the center is and thus the one sided probability for .
Suppose you use Monte Carlo simulation to estimate the numerical value of .
- How would you implement it?
- If we require an error of 0.001, how many trials do you need?
One possible implementation is to start with a rectangle, say . If we uniformly randomly draw a point from this rectangle, the probability of the point following into the circle region is the ratio of the area between the circle and rectangle, i.e
Formally, let random indicator variable take value 1 if the point falls in the circle and 0 otherwise, then and . If we do such trials, and define , then follows approximately . In this setup, and (see Probability Distribution section for details on ).
One thing we need to clarify with the interviewer is what error really means? She might tell you to consider it as the standard deviation of the estimated . Therefore the specified error translates into a required sigma of for random variable . Thus .
By the way, we can see that the number of trials scales with , which is caused by the scaling of the in the CLT, and is generally the computationaly complexity entailed by Monte Carlo integration.