Computing with Randomness
Some problems resist exact solutions but can be estimated by random sampling. Monte Carlo methods use deliberate randomness: generate many random scenarios and use their statistics to approximate answers for integrals, areas, and probabilities.
| Application | Approach | Formula |
|---|---|---|
| Estimating | Scatter points in a unit square containing a quarter-circle | |
| High-dimensional integrals | Bypass exponential grid growth using random samples | Cost is independent of dimension count |
Monte Carlo shines for high-dimensional integrals where grid-based methods fail entirely due to exponentially growing point requirements.
Convergence and Simulation
A Monte Carlo estimate's error shrinks as with sample count . This means convergence is slow: gaining one more decimal digit of accuracy requires one hundred times more samples.
| Feature | Monte Carlo Property |
|---|---|
| Convergence rate | Error proportional to |
| Best used for | Quick estimates and high-dimensional problems |
| Poor used for | High-accuracy computations needing many digits |
Common pitfall: Expecting estimates to improve quickly. Doubling samples only cuts error by , not in half.
Monte Carlo methods also simulate stochastic systems directly—such as particle diffusion or financial markets—by averaging many random trials.