Mathematics
Randomized Algorithm and Monte Carlo Methods
Quick fact
Monte Carlo methods, like estimating π by randomly scattering points in a square, can achieve accuracy that improves with the square root of the number of samples, meaning you need only a few million samples to get a few decimal places.
Why this is interesting
Imagine trying to find the area of a weird shape by throwing darts at it—randomness might seem like a terrible idea, but it can give you a great answer. How can flipping a coin possibly lead to a reliable result?
Read the full explanation
Understanding Randomized Algorithm and Monte Carlo Methods
A randomized algorithm is one that makes random choices during its execution. Instead of being deterministic (always taking the same path), it uses randomness to decide what to do next. There are two main types: Las Vegas algorithms always give the correct answer but have a random runtime, like randomized quicksort, where you randomly choose a pivot to avoid worst-case performance; and Monte Carlo algorithms, which give an answer that is correct with some probability, but may sometimes be wrong. The randomness is not a flaw but a resource that can simplify problems. For example, consider estimating the value of π by drawing a random point inside a square that contains a quarter circle. If you repeat this many times, the fraction of points that fall inside the quarter circle approximates the area of that quarter circle, which is π/4. This is a Monte Carlo method: you use many random samples to approximate a numerical value. The key idea is that the average of many random samples converges to what you want to know, because of the law of large numbers. Monte Carlo methods are extremely useful when the problem is too complex for an exact formula, like integrals of high-dimensional functions, or when you only need a good approximation rather than an exact answer.
A deeper explanation
The mechanism behind Monte Carlo methods is the law of large numbers: the average of many independent random samples is very likely to be close to the true expected value. In more detail, if you define a random variable X that equals 1 when a random point falls inside the region of interest and 0 otherwise, then the expectation of X is the area of the region divided by the area of the surrounding shape. By taking N samples, you compute the sample mean, which is an unbiased estimator of the true mean. As N grows, the sample mean converges to the true mean, and the error decreases like 1/√N, which is why hundreds of thousands of samples are often used. This is a fundamental result of probability theory, and it ensures that the random errors cancel out in the long run. For a randomized algorithm that must make a decision, Monte Carlo style algorithms may return a wrong answer with some small probability. For instance, the Miller-Rabin primality test is a Monte Carlo algorithm: it declares a number prime with high confidence, but there is a tiny chance of a false positive. However, by repeating the test with different random bases, the error probability can be made astronomically small. This trade-off—perfect certainty versus practical speed—is the essence of randomized computing. The importance extends to physics simulations, financial modeling, and even rendering realistic images in movies, where Monte Carlo methods are used to simulate light paths.