function trapezoid(f, a, b, n):
dx = (b-a)/n
total = (f(a)+f(b))/2
for j in 1,...,n-1:
total += f(a+j*dx)
return dx*total
function midpoint(f, a, b, n):
dx = (b-a)/n
total = 0
for j in 0,...,n-1:
total += f(a+(j+1/2)*dx)
return dx*totalThe trapezoidal rule gives each endpoint half weight; the composite midpoint rule uses one interior point per subinterval. Both converge for a continuous integrand on the closed interval.
The second equality in the printed trapezoidal hint is missing a factor . The average of the left and right rectangle sums is required. For , the uncorrected equality would return instead of .
A weighting function must first be normalized to a probability density. The constant choice on meansEquivalently, transform and use the already normalized on . Independent samples give the unbiased Monte Carlo integration estimator
function uniform_monte_carlo(f, a, b, N):
require N >= 2
total = 0
total_squared = 0
for j in 1,...,N:
u = independent_uniform_0_1()
value = f(a+(b-a)*u)
total += value
total_squared += value*value
average = total/N
sample_variance = (total_squared-N*average*average)/(N-1)
integral = (b-a)*average
standard_error = abs(b-a)*sqrt(sample_variance/N)
return integral, standard_errorFor a general positive normalized importance density , replace each sample contribution by with . Here the uniform choice is the special case of importance sampling that assigns equal weight to every region of equal length.
The constant density is reasonable when the integrand has comparable magnitude throughout the interval. It is inefficient for a narrow peak because most samples contribute little while rare samples carry large weights.
For independent importance sampling,A good density has support wherever , is easy to sample and evaluate, and resembles . Subject to normalization, minimizes this variance. For nonnegative , the ideal normalized choice makes every sample contribution equal, although its normalization is generally the unknown integral itself. Uniform weighting is therefore acceptable for a flat integrand, not universally suitable.
For a fixed- canonical ensemble, sample the normalized Boltzmann distribution in phase space:After integrating out the momenta for an ordinary separable Hamiltonian mechanics, configurational sampling uses . The correct equilibrium distribution is ensemble-dependent; the Boltzmann form is the canonical answer, rather than a universal prescription for every possible ensemble.
Most high-dimensional phase space has negligible equilibrium probability. Uniform sampling spends nearly all its work in these irrelevant regions and seldom visits the small subset that dominates the partition function or the numerator of an equilibrium average. The resulting estimator can have enormous variance.
Importance sampling places samples where the product of statistical weight and observable matters. Sampling the Boltzmann distribution, for example, converts a weighted phase-space integral into an equilibrium expectation. If a Markov chain Monte Carlo algorithm is used, adequate exploration of separate free-energy basins and allowance for autocorrelation remain necessary.
With independent samples and finite variance, Monte Carlo integration has a root-mean-square stochastic error proportional to . The estimated standard error measures that random sampling uncertainty; it is not a deterministic bound.
For a sufficiently smooth one-dimensional integrand, the composite trapezoidal rule has errorfor some , hence . It is normally much more efficient in one dimension. The stated continuity assumption alone guarantees convergence, but does not guarantee this second-order rate; bounded second derivatives are an additional assumption.
The dimensional advantage is different: a tensor grid with total points in dimensions has only about points per direction and typically error . The Monte Carlo exponent remains , although its variance prefactor can still deteriorate with dimension. This explains why the stochastic method becomes attractive for high-dimensional integrals.
Articles by others on the same topic
There are currently no matching articles.