Monte Carlo Estimation: Computing Quantities by Random Sampling and Its Slow but Sure Convergence
Abstract
Some quantities, such as the value of a complicated integral or the behaviour of a complex system, are hard to compute exactly but can be estimated by a surprising method: generating many random samples and averaging the result, the Monte Carlo method; the estimate it gives is not exact but improves as more samples are used, converging to the true value slowly but surely, and in a way that does not worsen with the complexity of the problem. This study examines Monte Carlo estimation, computing quantities by random sampling, and its slow but sure convergence. The estimate of a known quantity, obtained by random sampling, was examined as the number of samples was increased, so that how the estimate converged to the true value, and how fast, could be seen. The estimate fluctuated around the true value and settled toward it as the number ofsamples grew, the fluctuations shrinking but slowly: with few samples theestimate was rough and varied considerably from run to run, and as samples were added it homed in on the true value, but the error fell only in proportion to one over the square root of the number of samples, so that reducing the error tenfold required a hundredfold more samples. The convergence was therefore sure but slow, each further digit of accuracy costing a hundredfold more work. The method's strength was that this rate did not worsen as the problem grew more complex or higher-dimensional, unlike methods that divide the problem into a grid, whose cost explodes with dimension. Monte Carlo is therefore valued not for speed on simple problems, where it is slow, but for problems too complex orhigh-dimensional for other methods, where its dimension-independent convergence makes it the practical choice. The study shows that Monte Carlo estimation converges to the true value as one over the square rootof the number of samples, and it discusses the implications for computation in engineering and statistics. KEYWORDS: Monte Carlo method, Random sampling, Estimation,Convergence, Square-Root law, Variance reduction, High-dimensionalintegration, Simulation, Numerical methods.
Full Text:
PDF 33-40Refbacks
- There are currently no refbacks.