1 Introduction
Suppose we wish to calculate where is a random vector in with probability distribution and is a measurable function. Further, suppose that the expected value is finite and cannot be written in closed form or be easily calculated, but that can be easily computed for a given value of . Let . To estimate the expected value, we can use the sample average approximation: $${1\over n}S_{n}={1\over n}\sum_{i=1}^{n}g(X_{i}(\omega)) \eqno{\hbox{(1)}}$$ where the are random realizations of . When the are i.i.d. (i.e. Monte Carlo sampling), by the law of large numbers the sample average approximation should approach the true mean (with probability one) as the number of samples becomes large. Large deviations theory ensures that the probability that the sample average approximation deviates from by a fixed amount approaches zero exponentially fast as goes to infinity. Formally, this is expressed as $$\lim_{n\rightarrow\infty}{1\over n}\log \BB{P}\left(\left\vert {1\over n}S_{n}-\mu\right\vert >\delta\right)=-\beta_{\delta}$$, where is a positive constant.