[~Home~] | Monte Carlo Integration. Plain Monte Carlo. | Numerical Methods. Note~ « 11 » |
Random sampling. Plain Monte Carlo. We sample N points randomly from the integration region and evaluate the average of the integrand. The integral is equal to the volume of the integration region times the average of the integrand
∫ab f(x) dx ≈ V \mean{f} = V 1/N ∑~i f(xi), |
Here is a typical algorithm for a n-dimensional plain Monte Carlo integration:
function plain_mc(n, a[n], b[n], f, N) returns [I,err] for i=1..N : for k=1..n : x[i] = a[i] + random()*(b[i]-a[i]) sum += f(x[]) sum2 += f(x[])^2 average = sum/N variance = sqrt( sum2/N - average^2 ) vol = product( b[i]-a[i], i=1..n) I = vol*average err = vol*variance/sqrt(N)The variance can be reduced by a cleverer sampling.
Importance sampling. Metropolis algorithm. Distribute points not uniformly but with larger density in the regions which contribute most (that is where the function is largest). Suppose that the points are distributed with the density ρ, that is the number of points Δn in the interval Δx is equal Δn = ρ(x)Δx. Then the estimate of the integral I is
I = ∑ fi Δxi = ∑ fi 1/ρi = ∑ fi/ρi |
Problems