Monte Carlo

Robert P. Munafo, 1999 May 7.

A Monte Carlo technique is a technique involving randomness, particularly random sampling, and generally relying on statistical principles or effects to produce a useful result.

For example, the value of pi can be estimated by a Monte Carlo technique. Let n, the sample size, be some large number. Repeat the following n times:

- pick a random point within a square - calculate the distance from the lower-left corner to the point - if the distance is less than the length of the edge of the square, add 1 to your total.

Then the total, divided by n, will be an approximation of pi/4. This method essentially measures the area of a quarter-circle by random sampling.

The error for a Monte Carlo measurement is inversely proportional to the square root of the number of test cases:

E = K / sqrt(n) = K * n^-0.5

The error for ordered sampling (like the grid scan used in pixel counting) goes down quicker, at a rate depending on the Hausdorff dimension of the boundary of the set whose population is being sampled. There is still a square root term. For the whole Mandelbrot Set at low magnification the boundary has a dimension of about 1.5, so the error is about:

E = K / (n^1.5)^0.5 = K * n^-0.75

This property of ordered sampling for certain types of problems is well-known by statisticians. For example, if you're doing a phone survey and ethnicity is a factor in your results, you get more accurate results if you scan through the phone book and call every 20th listing (rather than picking ¹/₂₀ of the listings completely at random). This is because last names occur in clumps and last names are correlated with ethnicity.

In cases like the Mandelbrot Set, this statistical property of the grid scan sampling was verified experimentally. Once a really big sample has been done to get a relatively good estimate, lots of small samples are taken with different sampling methods, to study how the sampling method affects the error.

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2002 Dec 01.

s.27