A Monte Carlo method approximates a deterministic quantity using averages of simulated random variables and controls the approximation with probabilistic limit theorems.
Replacing a simulated quantity by preserves its expectation and reduces variance by the law of total variance. This is Rao-Blackwellization. For a random sum, conditioning on the count and all but one summand replaces an event indicator by a cumulative distribution function evaluation. The resulting estimator needs that conditional expectation to be computable.
Independent uniform distribution draws on produce independent standard normal distribution draws and . The proof transforms an independent uniform angle and radial density through the polar-coordinate Jacobian.
Nested Monte Carlo approximates an outer expected value whose integrand contains another expected value. A nonlinear transformation, such as a logarithm, of an inner sample average usually introduces finite-sample bias. Increasing both sample sizes requires suitable integrability controls to establish consistency; an unbiased estimator of the inner quantity does not make its logarithm unbiased.
A Monte Carlo estimator is a random approximation obtained from simulated samples, commonly a sample average or a weighted sample average.
At equal proposal count, compare for unnormalized importance sampling with for the accepted-sample mean. There is no universal ordering for nonzero target mean. For zero mean, the bounded-weight inequality gives importance sampling no larger asymptotic variance. Empty rejected samples and per-proposal computational cost are separate considerations.
An additive constant leaves the target variance and accepted-sample mean variance unchanged, but changes the variance of unnormalized importance sampling because its random weights do not sum to one. With g uniform on (0,1), f(x)=2x and M=2, phi(x)=x gives importance variance 16/45 versus rejection proposal-budget variance 1/9. Replacing phi by x-1 gives importance variance 1/45 with the same rejection variance, reversing preference.
A control variate is a random variable with known expected value whose centered value is subtracted from a Monte Carlo estimator to reduce its variance. For a mean-zero vector , put and . When is invertible, the optimal estimator averages and has variance for independent draws. Improvement is strict exactly when .
If a smooth posterior density has vanishing boundary terms, its log-posterior gradient satisfies andThis is a posterior integration-by-parts identity; it concerns differentiation in the random parameter, distinct from the usual mean-zero score identity for sampling distributions. It makes a vector control variate. Finite moments and known coefficients preserve unbiasedness of the Monte Carlo estimator.
Monte Carlo error is the random difference between a simulation estimate and the exact quantity it approximates. For an average of independent finite-variance draws, its standard deviation is proportional to the inverse square root of the number of draws.
Suppose is a target probability density and is a proposal density with . Draw and an independent , and accept whenThe accepted value has density , the acceptance probability is , and the expected number of proposals is .
Reject pairs of independent uniform coordinates from the square until their squared radius lies in . Multiply each coordinate by to obtain two independent variables with the standard normal distribution. Squaring either gives a chi-squared variable with one degree of freedom.
For n independent proposals and an envelope constant , each rejection decision succeeds with probability . The accepted count is Bin(n,1/M). Conditional on any acceptance pattern, the accepted values have independent target density f; summing over patterns preserves that product law conditional on the count. The empty-output probability is .
Conditional iid accepted values have the ordinary target-sample CLT at scale . Since , the same estimator has asymptotic variance at scale . The centered count has limiting variance . Any fixed convention on an empty output is asymptotically negligible.
With normalized densities and envelope , , conditioning a proposal on rejection gives density . It can be used as an importance sampling proposal only if it covers the relevant target support. If on a set of positive target mass, rejected draws never visit that set.
Adaptive rejection sampling builds a piecewise linear upper envelope for a differentiable log-concave probability density, samples from its piecewise exponential form, and accepts with the target-to-envelope ratio. Adding evaluated points improves the envelope without changing the target distribution. Initial tangent slopes must yield integrable tails. The accepted draws are exact samples, unlike a finite run of Markov chain Monte Carlo.
To estimate , sample independently from a reference density whose support covers that of , and useThe summands have expectation , and the strong law of large numbers gives almost-sure convergence under integrability.
For rejection indicators with conditional acceptance , the conditional expectation of given all proposals is the unnormalized importance estimator. The Rao-Blackwell theorem reduces variance relative to that fixed-denominator estimator. It gives no such automatic comparison with the accepted-sample mean, whose denominator is the random count.
If , the importance weight is bounded by , and . A finite target second moment therefore guarantees finite variance and the iid central limit theorem for the unnormalized importance-sampling average. Its proposal-budget variance is .
For and , the proposal minimizes the variance of the ordinary unbiased importance sampling estimator. The Cauchy-Schwarz inequality gives , so the minimum variance for independent samples is . The proposal need only cover the nonzero integrand.
An importance sampling proposal must be positive wherever the target-weighted integrand can contribute. The usual sufficient condition is that the target probability is absolutely continuous with respect to . Otherwise multiplying observed draws by cannot recover a missing part of the integral. A strict rejection envelope supplies this condition for the rejected-proposal distribution.
For target density and proposal density , the importance weight is the density ratio wherever the target is supported.
For an unnormalized target density, self-normalized importance sampling uses weights and estimates expectations by . Resampling a point with probability proportional to produces the associated weighted empirical distribution.
For estimating by the unbiased importance estimator , the proposal minimizing variance isThis follows from the Cauchy-Schwarz inequality. Its normalizing constant and dependence on the particular integrand often make it impractical.
Articles by others on the same topic
The Monte Carlo method is a statistical technique used to approximate solutions to quantitative problems that might be deterministic in nature but are complex enough to make exact calculations infeasible. It relies on random sampling and statistical modeling to estimate numerical outcomes. The method is named after the Monte Carlo Casino in Monaco, reflecting its inherent randomness similar to games of chance.