Motivation
A numerical integral or expectation can be difficult to evaluate exactly while individual random samples are easy to generate. Monte Carlo estimation replaces the expectation by an average of simulated values. The average is random: running the same algorithm again generally gives a different result. An analysis should therefore say both what quantity is being estimated and how often a specified error can occur.
There are several distinct guarantees. Unbiasedness concerns the mean of the estimator across hypothetical repetitions. The law of large numbers concerns its limit as the number of samples increases. A finite-sample bound controls a particular error probability at a specified sample size. None of these automatically supplies the others under arbitrary sampling assumptions. In particular, the variance reduction from averaging relies on the dependence structure of the simulations, not merely on the number of values printed by a program.
From uniform draws to a target distribution
The estimator needs samples from the chosen distribution, not just a formula for its expectation. One basic construction starts with an ideal uniform random variable on . Let be a cumulative distribution function: it is nondecreasing and right-continuous, with limits zero and one at the two infinities. Define its generalized inverse for by
The set is nonempty and bounded below, so is finite. Choose points of the set decreasing to its infimum; right-continuity then gives . Consequently, for every real ,
Indeed, the forward direction uses monotonicity of ; in the reverse direction belongs to the set defining the infimum. Therefore
Thus has the target distribution, including atoms and flat portions of . The argument does not require a density or a strictly increasing . If independent uniforms are transformed separately by the same deterministic , the results remain independent and identically distributed. This is the link to the independent-sample formulas below.
Worked example 9.1.1
(Exponential and discrete samples)
For , the exponential distribution has for and for . Solving gives . For instance, gives .
For a discrete variable taking with probabilities , the cumulative probabilities are . Return for , for , and for . The intervals have precisely the required lengths. There is no ordinary one-to-one inverse of this step function; the generalized inverse is what makes the construction work.
The proof describes ideal continuous uniforms and exact arithmetic. A computer supplies a finite set of pseudorandom values, not literally independent continuous variables; endpoint conventions matter too. In the exponential formula, would require , while a finite grid cannot represent the unbounded tail exactly. A fixed pseudorandom seed makes a run reproducible; it does not itself prove independence or establish a Monte Carlo error bound. Use the actual generator's documented range and assess its suitability for the calculation.
Quick check
(A target takes the values and with probabilities and . Give a transformation of the uniform variable that produces it, and the expectation of the target.)
Compare the intervals of with the cumulative probabilities.
Solution · Answer
Return when and otherwise. The expectation is . This is a distributional statement for the ideal construction, not a guarantee about a single finite-grid implementation.
Quick check
(For an exponential target with rate , what does the transformation return at ?)
Use with .
Solution · Answer
, which is the median of this distribution.
Definitions
Definition 9.1.2
(Monte Carlo estimator and variance)
Let be independent identically distributed real random variables with finite mean . For an integer , the Monte Carlo estimator is
If , write . Independence gives
The last quantity is the root mean squared error. It is not a deterministic bound on an individual run. Pairwise zero covariances also suffice for this variance formula, but the proofs of the strong law and Hoeffding bound below use independence.
An expectation under a probability density is an integral: can be estimated by drawing independent and setting . For a random-walk calculation, one could instead be a function of an entire simulated path; independence is then required between paths for the formulas above, not between consecutive positions within one path.
Definition 9.1.3
(Convergence in probability and almost surely)
A sequence converges to in probability if, for every , . It converges almost surely if the set of outcomes for which has probability one. Almost-sure convergence is a statement about the full infinite sequence on one outcome; it does not say that every finite estimate lies within a given tolerance.
Laws of large numbers and error bounds
Theorem 9.1.4
(Finite-variance laws of large numbers)
For i.i.d. with mean and finite variance , both in probability and almost surely. For every , Chebyshev's inequality supplies the finite-sample bound
For i.i.d. variables, the stronger general strong law also holds with a finite first absolute moment, even if the variance is infinite; the proof below uses the more restrictive finite-variance assumption.
Theorem 9.1.5
(Hoeffding bound for bounded independent outputs)
Suppose the are independent and each lies in the same interval almost surely, with and mean ; identical distributions are not needed if the individual means are all . Then for every ,
In particular, suffices to make this bound at most , for .
The sample-size formulas are sufficient guarantees; they are not exact failure probabilities. Chebyshev uses a variance bound, whereas Hoeffding uses a known almost-sure range. A small observed range in one run is not by itself proof that the output distribution is bounded by that range.
Why the convergence and concentration claims hold
Proof
(Mean, variance and the weak law)
Linearity of expectation gives unbiasedness. For independent variables, all off-diagonal covariances in the variance of the sum vanish, giving . Because the estimator is unbiased, this variance is also its mean squared error. Applying Markov's inequality to gives Chebyshev's bound. Its right-hand side tends to zero for fixed , proving convergence in probability.
This derivation uses the true variance. If is unknown, replacing it with a random sample variance requires a separate statistical argument; the displayed bound does not automatically become a confidence guarantee by that substitution.
Proof
(A finite-variance proof of almost-sure convergence)
Set and . The are independent, mean zero and have variance . We first establish the maximal inequality
For each , let be the event that the first index at which is . The are disjoint and are determined by . Independence and zero means make the cross term vanish in expectation, not pointwise: . The remaining squared increment is nonnegative. Consequently
Sum over and use to obtain the inequality.
For an integer , apply it with and . The probability that some has is at most . These bounds are summable in . By the first Borel–Cantelli lemma, only finitely many of the events occur almost surely. Thus, eventually, every satisfies . Intersecting these probability-one conclusions for yields almost surely.
Proof X-ray
Why blocks of indices, not single ones
Finite variance enters through , the only place where the size of the fluctuation is measured. Independence is used once: depends only on and only on later terms, so the expectation of their product factorizes and the mean-zero increment makes it vanish.
The non-obvious move is the choice of what to bound. Chebyshev applied at each single index gives , and the harmonic series diverges, so Borel–Cantelli would say nothing. The maximal inequality pays one factor to control every at once, and cutting the indices into blocks makes the bounds geometric. Inside a block , so gives at the price of a factor two.
The argument closes in two stages: Borel–Cantelli turns a summable sequence of failure probabilities into "eventually no failure" on a single outcome, and a countable intersection over removes the dependence on the tolerance. Without independence the cross term need not vanish; in the perfectly dependent example later on this page the average never settles.
Proof
(Why the bounded-output tail is exponential)
We use the following bounded-variable estimate: if almost surely, then for every real ,
For completeness, let . Boundedness justifies differentiating the expectation. The exponential tilt of the distribution is still supported in ; differentiating the logarithm shows is its variance. A variable supported in has variance at most : compare its squared distance from its own mean with its squared distance from the interval midpoint. Since and centering gives , integrating the second-derivative bound twice gives .
For the upper tail, Markov's inequality and independence give, for ,
Choose to obtain . Apply the same argument to and use a union bound for the two tails. This proves the stated factor two. Independence is used when the exponential moments of the sum are factored.
Proof X-ray
Exponential moments turn independence into a product
The real idea is to apply Markov's inequality to instead of the sum itself, so that independence factorizes the moment into a product of one-variable factors. Boundedness enters only through the one-variable estimate , and independence only in the factorization. The parameter is then free: the exponent is minimized at , giving . The factor two is a union bound for the two tails. Without independence the product step fails, as in the perfectly dependent example below.
Importance sampling
Definition 9.1.6
(Changing the sampling density)
Let be probability densities with respect to the same reference measure , write for , and interpret “almost everywhere” relative to . Suppose is real-valued and measurable with . Assume almost everywhere on the set where . For independent , define
The ratio may be defined arbitrarily on the -null set where . The support condition ensures
If additionally , its variance is
The support requirement above is tailored to this one integrand. To use the same proposal for arbitrary integrands under , require almost everywhere on . A proposal that misses a region where is nonzero cannot recover its contribution by multiplying observed samples by a weight. Even when support is adequate, small can create very large weights and infinite variance.
There is a useful benchmark for how small the variance could be. Put and assume . For any admissible proposal with finite weight second moment, Cauchy–Schwarz gives
because . Equality is attained by , which is a density and has the needed support for this integrand. Its minimum attainable weight variance is . When almost everywhere under , and the optimal weight is constant ; a sign-changing integrand need not permit zero variance. This is a theoretical benchmark: using exactly requires its normalizing constant , which may be unknown.
For example, under uniform on let . Then , , and . The weight is on the left half and on the right, each with proposal probability . Its variance is , smaller than the uniform-sampling variance but not zero.
Concept lensAnalytic
The weight variance as a chi-squared distance
Take , so and . If wherever , then . This is the chi-squared divergence of from : it vanishes exactly when almost everywhere, and it is infinite exactly when diverges. In the infinite-variance example below, .
Worked examples
Worked example 9.1.7
(Estimating the area of a disk)
Draw independent uniformly from and put . The square has area four and the disk has area , so . The estimator is four times the fraction of points in the disk. Here and
For absolute error and failure probability at most , Hoeffding gives the sufficient condition
so suffices. This bound is a planning guarantee under independent uniform draws, not the actual probability that this particular program returns a given decimal.
Worked example 9.1.8
(An importance proposal with zero variance)
To estimate , take the target density and proposal density on . The support condition holds almost everywhere, even though at one point. A proposal draw gives
The estimate is therefore exactly for every positive sample size and has zero variance. By contrast, uniform sampling produces with variance . This is an instructive ideal proposal, not a generic recipe: normalizing a density proportional to an unknown nonnegative integrand can require knowing the very integral being estimated.
Worked example 9.1.9
(Correct support but infinite variance)
Now estimate using the same and . The weight is for . Its expectation is one, but
Thus the estimator remains unbiased, but its variance is infinite for every finite : all weights are nonnegative, so . The finite-variance Chebyshev and bounded-output Hoeffding formulas do not apply. The general finite-first-moment strong law can still yield almost-sure convergence; that fact supplies no finite-variance error certificate.
Counterexample mode
Many dependent outputs may be only one piece of information
Let be a fair Bernoulli random variable and set for every . Each has mean and variance , but the outputs are perfectly dependent. Their average is for every , so its variance remains and it does not converge in probability to . Treating the values as independent would incorrectly predict variance .
Common mistakes
Common mistake
(Confusing unbiasedness with a reliable single estimate)
An unbiased estimate can be far from its target on one run and can even have infinite variance. A finite-sample guarantee requires assumptions strong enough to control its tail, as well as a stated tolerance and failure probability. Almost-sure convergence is an asymptotic statement, not a certificate for a particular finite .
Common mistake
(Ignoring where the proposal density vanishes)
If on a set where has a nonzero contribution, the estimator never samples that contribution. For example, estimating with but yields on every sampled point, so the expected output is , not one. The problem is missing support, not a large-sample fluctuation.
Summary
Independent simulation averages are unbiased and have variance when the variance is finite. Chebyshev, Hoeffding and the strong law make different kinds of statements under different hypotheses. Importance sampling changes the distribution of observations and requires both a support check and, for variance-based guarantees, a finite second moment of the weight.
Exercises
Exercise 9.1.10
(Independent outputs have mean and variance . For , find the variance and root mean squared error of their average, and give Chebyshev's bound for an error of at least .)
Foundation
Solution(3)
- 1
Variance of the average
- 2
Root mean squared error
Because: The estimator is unbiased, so its mean squared error is its variance.
- 3
Apply Chebyshev
This is a bound, not the exact probability for every distribution with the stated mean and variance.
Exercise 9.1.11
(For independent outputs in , find an integer for which Hoeffding's two-sided bound with is at most .)
Foundation
Solution(3)
- 1
Write the condition
Because: Here .
- 2
Solve for
- 3
Round up
suffices.
Exercise 9.1.12
(Estimate using and on . Find the importance weight, its mean and its variance.)
Core
Solution(3)
- 1
Compute the weight
Key step
For , almost surely
- 2
Compute the mean
- 3
Compute the second moment and variance
For independent proposal draws the average has variance .
Exercise 9.1.13
(Let for all , where is a fair Bernoulli variable. Compute and explain why the independent-sample Hoeffding bound does not apply.)
Core
Solution(3)
- 1
Identify the average
Every equals , so for every .
- 2
Compute the probability
Since , always, so the probability is for every .
- 3
Locate the failed hypothesis
The outputs are perfectly dependent, so that factorization is invalid. The bound would be below for large , which contradicts the exact value .
Because: Hoeffding's proof factorizes the exponential moment of the sum into a product over samples.