Monte Carlo simulations are one of the most common randomized algorithms. A Monte Carlo simulation is a method of estimating the value of an unknown quantity by making use of the principles of inferential statistics.
In brief (since this is a course in algorithms, not probability and statistics), the guiding principle of inferential statistics is that a random sample tends to exhibit the same properties as the population from which it is drawn.
For example, if you flip a coin 10 times, and it comes up heads every
single time, then you might start to form an opinion that the coin is
not fair, and that it is biased towards coming up heads- you might
begin to believe that the population of all possible flips of this
coin contained more heads than tails.
If you flip
the same coin 100 more times, and it still comes up heads every single
time, it would probably be hard to convince you that the coin was fair
at all (in fact, you might start to believe that it had two heads!).
On the other hand, if you flipped the coin 100 times and roughly half of the time it came up heads, then you would probably believe that it was a fair coin- or at least not unfair to any obvious degree.
In both cases, your belief whether the coin is fair or not is based on the intuition that the behavior of a sample of 100 flips is similar to the behavior of the population of all flips of your coin. Luckily, this belief is not without basis in fact- and we can make use of this fact to achieve good estimates of probabilities with relatively little effort. This method is formalized in algorithm 7.1, which shows a method of estimating p for a coin, based on a set of random trials.
When we use algorithm 7.1 to perform a Monte Carlo simulation, we are trusting that fate will not give us an unusual or freakish sample- we are trusting that the true probability is reflected in our observations. In the long run, we can generally rely upon this assumption- although it is important to know how many samples we will have to take before this assumption holds.
While we trust in luck to ensure that our sample is not wildly
unusual, we must also realize that it is extremely unlikely that fate
will provide a sample that is exactly like the
population. Consider
the example of flipping a fair coin 1000 times. While it is likely
that the number of heads and tails will be close to 500, it is also
unlikely that they will both be exactly 500. What is far more
likely is that the number of heads will fall in some range around
500.
This leaves us with two questions to ponder:
As you might guess, the answers to these two questions are related- the more sure we want to be that our sample is good, the more samples we need to take, and the more samples we take, the more likely it is that we will get a more accurate estimate.
Unfortunately, it is never possible to achieve perfect accuracy through sampling unless you sample the entire population- no matter how many samples you take, we can never be sure that the sample set is typical until we verify every last element of the population (and since we are usually dealing with infinite populations, this is simply impossible). Of course, this is not to say that our estimates are not perfectly correct- we might arrive at the exactly correct value, but the trouble is that we can't know that our estimate is correct! All we can measure is how likely it is to be correct.
Since this is a course in data structures and algorithms, and not a course in statistics, rather than deriving the relationship between the sample size and accuracy estimate from first principles (which requires the first week or two of a course in mathematical statistics to accomplish), it is now time to begin making gross (but useful) generalizations.
The relationship between the sample size and our estimate of the accuracy of an estimate arrived at from a sample is given by the following equations:
In these equations, n is the sample size, and e is the ``margin of error'', which is the fraction by which we believe our estimate may be incorrect. The variable z is a function of how confident we desire to be in our estimate of e- the probability that our estimate is within e of the true value. Computing z is a laborious process (and it was even more laborious before computers were given this task). However, the following table contains values of z for some common confidence levels:
A few very important caveats about these equations:
Returning to our example of flipping a coin 1000 times, if the coin comes up heads exactly 500 times, our estimate of the probability of the coin coming up heads is 0.5. However, now we can also compute our ``margin of error'' for this estimate. With 95% confidence, we can say that our estimate is accurate to within 3.1%:
Similarly, we can compute our ``margin of error'' with a 99% level of confidence, using the same method, but with a z of 2.58:
Notice that our margin of error has increased. In order to gain more confidence in our estimate, we have had to widen the margin. Note that the only way to achieve 100% confidence is to widen the margin of error to be so wide that it spans the entire range from 0.0 to 1.0- the only way that we can be 100% confident that our margin of error contains the correct probability is to include all probabilities!
Returning to the coin example, if our estimated p is 0.5, and our margin of error (based on 1000 trials, at a 95% level of confidence) is 0.031, then we can restate our estimate as (with a 95% level of confidence). This way of expressing the estimate together with the margin of error is called a confidence interval.
In this case, based on our 1000 trials, we can say that we are 95% confident that the true probability of the coin coming up heads is within the range from 0.469 to 0.531. The true probability might be outside this range, but we are 95% confident that it is not.
Note that if our margin of error is large enough (either because we are requiring a very high confidence level, or the number of samples is too small), the confidence interval may include values outside the range from 0 to 1. These values should be discarded, because they are not valid probabilities.
In the last section, we computed the confidence interval for a sample of 1000 trials. In this section, we will ask the problem from the other perspective- in order to get an estimate of the probability p of a coin (i.e. the probability that the coin will come up heads) that is accurate to within 5%, with a 95% level of confidence, how many trials do I need to perform?
Returning the equation:
Therefore, we can be 95% confident that an estimate of p based on 384 coin flips will be accurate to within 5% of the true p. (If we want to be more confident, or to achieve a more accurate estimate with the same level of confidence, then more coin flips will be necessary.)