Lesson 3

The same analysis explains the accuracy of Monte Carlo estimates. Suppose we want to estimate \(\Pr[A]=p\) for some event \(A\). For the \(i\)-th independent run, define the indicator variable \[\chi_{i} = \begin{cases}1, & \text{if \(A\) occurs in run \(i\),}\\ 0, & \text{otherwise.}\end{cases}\] Then the Monte Carlo estimate is \[\widehat p=\frac{\chi_1+\dotsb+\chi_n}{n}.\] It has expectation \(p\) and variance at most \(1/(4n)\). Indeed, each \(\chi_{i}\) is a Bernoulli random variable, so \[\operatorname{Var}[\chi_{i}]=p(1-p) = \frac{1}{4}-\left(p-\frac{1}{2}\right)^{2} \le \frac{1}{4},\] and the variables \(\chi_{1},\dotsc,\chi_{n}\) are independent. Therefore, by Chebyshev's inequality, \[\Pr[|\widehat p-p|\ge \varepsilon] \le \frac{1}{4n\varepsilon^2}.\] This means that to make the error about ten times smaller, one usually needs about one hundred times more trials. Indeed, suppose we want to keep the same upper bound on the probability of a large error. If the old error threshold is \(\varepsilon\), the bound is \[\frac{1}{4n\varepsilon^2}.\] If we replace \(\varepsilon\) by \(\varepsilon/10\), then the same number of trials would give \[\frac{1}{4n(\varepsilon/10)^2}= \frac{100}{4n\varepsilon^2}.\] To compensate for this factor, we should replace \(n\) by \(100n\).