But you will also see that this result will become handy when we will study variance reduction in the next chapter. So keep reading and you will soon understand why this result is important! As you can see, a Monte Carlo estimation is nothing else than a sample mean, only, we substitute the population for a real-value arbitrary function.
For this reason, Monte Carlo estimations and sample means share the same properties:. Some additional remarks can be made. The idea behind the Monte Carlo estimator is simple and has probably be known for a very long time, but it only took off with the advent of computer technology in the late s.
Evaluating functions a great number of times and averaging the results is a task computers can do a countless number of times faster than what we, humans, could ever achieved.
Being able to run these simulations efficiently something we never had a chance to before the computer age , helped solving a great number of important and complex problems in numerous fields of science mathematics, physics, biology, chemistry, etc.
It can also be applied to other areas such as finance to run predictions and of course computer graphics. We will talk about this more in a moment. However you may wonder why we would be interested in this technique at all. Indeed, in the chapter the Mathematics of Shading, we learned how to calculate integrals using a technique called the quadrature rule check the section on the Riemann sum for example. This technique is quite simple as well. So why would you be interested in another method?
It happens that quadrature rules to solve integrals are simple indeed, but as the dimension of the integral increases, they become more and more expensive to use. On the other hand, the principle of the Monte Carlo integration can easily be extended to higher dimension and the convergence rate of the method is independent of the number of dimensions.
As you will see in the next lessons, in rendering we sometimes have to solve integrals of functions with many variables or multiple integrals for which MC integration is better suited.
Of course, for a fixed number of samples, the quality of the approximation decreases with the number of dimension but still, you are guaranteed to get a solution at a fixed cost the number of samples N. One of the key element of a Monte Carlo estimation is the ability to use and thus generate sequences of random numbers which we can use to evaluate the function f x for "random" values of x over the desired interval [a,b]. Thus as with all the other methods, the generation of random numbers.
In this chapter, we will only consider the case where these numbers are generated with a uniform distribution, but it some cases it is advantageous to generate random numbers with very specific PDFs. We will explain why later in this chapter and the lesson on importance sampling. However, the point here, is that mastering the art of generating random numbers, is very important if you wish to use Monte Carlo methods.
A chapter of this lesson is dedicated to this topic. In this chapter, we have only presented the basic Monte Carlo estimator. This naive method works well for simple cases, but we are interested in using it for practical problems which are generally more complex. For this reason, a lot of research went into developing techniques to reduce the error or variance.
We often speak of variance reduction. Importance sampling for instance, which is a term you may have heard of already, is an example of such strategy. We will talk about variance reduction technique in this lesson as well as the lesson on Importance Sampling. Monte Carlo Methods. Monte Carlo Simulation. Monte Carlo Integration.
Generating Random Numbers. Source Code. To be clear, the pdf in the denominator is the same as the pdf of the random variable X. Let's get an intuition as to why dividing f x by pdf x is necessary for non-constant PDFs. When you draw samples from an arbitrary PDF, samples aren't uniformly distributed: more samples are generated where the PDF is high and reversely, fewer samples are generated where the PDF is low see adjacent figure.
In a monte carlo integration though, the samples need to be uniformly distributed. If you generate a high concentration of samples in some region of the function because the PDF is high in this region , the result of the Monte Carlo integration will be clearly biased.
Dividing f x by pdf x though will counterbalance this effect. Indeed, when the pdf is high which is also where more samples are generated dividing f x by pdf x will decrase the "weight" of these samples in the sum. So in essence, we compensate for the higher concentration of samples, by weighting down their contribution. On the other hand, when the pdf is low, fewer samples are generated the density of samples is lower than in region where the pdf is high.
But if we divide f x by a low value 1 divided by 0. We compensate for the lesser density of samples by giving them more weight. That's in essence, what the division of f x by pdf x does. It weights the samples' contribution to compensate for the fact that samples generated from an arbitrary PDF won't be uniformly distributed assuming the PDF is not constant of course : it scales down samples generated in regions of higher density where the PDF is high , and scales up samples generared in regions of lesser density where the PDF is low.
We look into this concept in depth in the next chapter on variance reduction and importance sampling. In fact it can be seen quickly in testing the procedure that compared to the numerical quadrature usually many more support points are needed to achieve a similar result. Unlike numerical quadrature method, the idea of Monte Carlo integration can be applied to the calculation of high-dimensional integrals very easily. There, the Monte Carlo integration has advantages over numerical integration method and therefore is still used today in this areas.
Another difference from the numerical integration is the typeof the convergence. In the numerical quadrature there are error estimatesin form of upper bounds for the error between the actual value of the integral and the computed approximation. These bounds strive for a finer decompositions of the domain to 0. In Monte Carlo integration the integral to be calculated is estimated by a random value. It can be shown that the expected value of this estimator is the exact value of the integral, and the variance of this estimator tends to 0, that is, with an increasing number of support points, the variation around the exact value is getting lower.
The error bounds of numerical integration rules contain a derivative term, therefore for the approximation to tend to the the correct value, is has to hold that the function to be integrated f is sufficiently smooth f has to be differentiable four times as for Simpson's rule.
Such demands are not needed at the Monte Carlo integration. The hit-or-miss Monte Carlo integration directly uses the interpretation of the integral as area. The studied area is bounded by a rectangle, and on this random points are generated following a uniform distribution.
The probability for such a point to be in the investigated area corresponds to the ratio of the desired surface content and the surface area of the whole rectangle. By the strong law of large numbers the relative frequency of the points that lie within the investigated area, just tends to this probability. The desired area thus can be approximated by the proportion of the points within the investigated area multiplied by the area of the rectangle.
Of course also other geometric boundaries can be used instead of a rectangle; it is important that the area can be relatively easily calculated, and that uniformly distributed points can be created in this area in a simple manner. As for the direct Monte Carlo integration here also numerical quadrature methods provide significantly better results on the here illustrated functions; the hit-or-miss-variant of the Monte Carlo integration is nowadays used only to calculate high-dimensional integrals.
0コメント