Introduction
Monte Carlo methods vary, but tend to follow a particular pattern:
- Define a domain of possible inputs.
- Generate inputs randomly from a probability distribution over the domain.
- Perform a deterministic computation on the inputs.
- Aggregate the results.
For example, consider a circle inscribed in a unit square. Given that the circle and the square have a ratio of areas that is π/4, the value of π can be approximated using a Monte Carlo method:
- Draw a square on the ground, then inscribe a circle within it.
- Uniformly scatter some objects of uniform size (grains of rice or sand) over the square.
- Count the number of objects inside the circle and the total number of objects.
- The ratio of the two counts is an estimate of the ratio of the two areas, which is π/4. Multiply the result by 4 to estimate π.
In this procedure the domain of inputs is the square that circumscribes our circle. We generate random inputs by scattering grains over the square then perform a computation on each input (test whether it falls within the circle). Finally, we aggregate the results to obtain our final result, the approximation of π.
If grains are purposefully dropped into only the center of the circle, they are not uniformly distributed, so our approximation is poor. Second, there should be a large number of inputs. The approximation is generally poor if only a few grains are randomly dropped into the whole square. On average, the approximation improves as more grains are dropped.
Read more about this topic: Monte Carlo Method
Famous quotes containing the word introduction:
“For better or worse, stepparenting is self-conscious parenting. Youre damned if you do, and damned if you dont.”
—Anonymous Parent. Making It as a Stepparent, by Claire Berman, introduction (1980, repr. 1986)
“My objection to Liberalism is thisthat it is the introduction into the practical business of life of the highest kindnamely, politicsof philosophical ideas instead of political principles.”
—Benjamin Disraeli (18041881)
“We used chamber-pots a good deal.... My mother ... loved to repeat: When did the queen reign over China? This whimsical and harmless scatological pun was my first introduction to the wonderful world of verbal transformations, and also a first perception that a joke need not be funny to give pleasure.”
—Angela Carter (19401992)