Reference S.P. Mudur and S.N. Pattanik, "Monte Carlo Methods for Computer Graphics", State of the Art Reports, Eurographics'93, Barcelona, Sept. 6-10, 1993.:
The Monte Carlo method is a numerical method for solving mathematical problems using stochastic sampling. Look at a simple Monte Carlo technique known as the "hit or miss" method.
Assume we have a function f(x) and we want to find the integral of f(x) from x = 0.0 to x = 1.0. We can draw a unit square, choose N random points within the square. For each point we determine if it lies below the f(x) curve, if it does then we increment a counter Hit. Then the area under the curve is given by Hit/N. N = Hit + Miss.
Note two features of this method. First, an algorithm is written to perfom one random test and then repeated N times. Second, the statistical measure of error is proportional to (D/N)^1/2 where D depends on the particular Monte Carlo technique used.
Another method for finding an integral is called Monte Carlo quadrature. This consists of the following steps:
1. Let G = òg(x) dx be the integral to be evaluated. 2.
Rewrite g(x) as f(x)g'(x) where f(x) is a probability distribtion
function and g'(x) = g(x)/f(x). Note that for a uniform random
distribution in the interval [a,b] the pdf = 1/(b-a). 3. Sample f
(x) for a xi, i.e. obtain some xi from f(x). 4. For each such
sample xi evaluate g'(x). 5. Perform steps 3 and 4 N times. Then
the average
One value of the variance that is frequently used is the
sample variance S2 where: S2 = 1/(N-1)SNi=1 (g'(x) -
So we can improve the accuracy by increasing the number of samples N or by decreasing the variance. We can decrease the variance by eliminating potential samples with unusually high or low values.
Go back to First Math screen
HyperGraph Table
of Contents.
HyperGraph Home
page.