Motivation
Simulation replaces an inaccessible calculation with an experiment that a computer can repeat. An integral over a complicated region may be hard to evaluate analytically, while drawing a point and evaluating a function there may be straightforward. The computer does not remove uncertainty: it changes the calculation into one whose error can be studied probabilistically. A long list of simulated values becomes useful only after we specify the quantity being estimated and the assumptions connecting the list to that quantity.
There are three distinct errors to keep apart. A mathematical model may simplify the phenomenon of interest. A numerical simulator may approximate that model, for example by discretizing a differential equation. A finite Monte Carlo average then fluctuates around the expectation of the simulator's output. Increasing the number of replications addresses the third error. It does not automatically remove model error or discretization bias. Even an average that looks very stable may be stably estimating the wrong target.
Consider estimating an integral on the unit interval. Drawing a uniform point and evaluating the integrand turns area into an expectation. Many replications can be split across machines, and their summaries can be merged using the previous unit. But merging statistics correctly is only one part of the argument: the replications also need the stated joint distribution. Accidentally giving every worker an identical random stream can destroy the expected gain from parallelism.
Definitions
Let have the uniform distribution on . If is integrable, the target integral can be written as .
Definition 2.1.1
(Replication and the ordinary Monte Carlo estimator)
Let denote the output of one complete simulation replication and suppose exists. Given independent identically distributed copies of , the ordinary Monte Carlo estimator is
Definition 2.1.2
(Unbiasedness and mean squared error)
An estimator of is unbiased if . Its mean squared error is .
When the estimator has finite second moment, the mean squared error decomposes into variance plus squared bias. Thus unbiasedness does not say that one particular answer is close, and small variability does not rule out a systematic offset from the intended target.
Definition 2.1.3
(Standard error and its estimate)
If has finite variance , the standard deviation of is called its standard error. For , the estimated standard error uses the sample variance :
The standard deviation of individual outputs measures simulation variability; the standard error measures variability of their average. Dividing by is justified by independence or a suitable substitute, not by the mere length of an output file.
Concept lensGeometric
The sample variance as a squared projection
Write the outputs as a vector in , with . The residuals form , where is the orthogonal projection onto the hyperplane perpendicular to . Hence . When , its expectation is : the denominator counts the dimensions left after fitting the mean.
Definition 2.1.4
(Confidence procedure and coverage)
A confidence procedure is a rule producing a random interval from data. Its coverage probability is the probability, over repeated applications of the rule under its assumptions, that the interval contains the target.
Coverage is not a probability assigned retrospectively to a fixed parameter by frequentist reasoning alone. We will derive a finite-sample probability bound and distinguish it from a normal approximation.
Definition 2.1.5
(Reproducibility)
A simulation is reproducible when its specified computational inputs and execution choices allow the calculation to be repeated with the same result.
A random seed is one input, but a complete record may also require the generator algorithm, library version, stream assignment, model parameters, sample count and reduction order. A deterministic pseudorandom sequence is not literally an infinite collection of independent mathematical random variables. The probabilistic analysis is a model for a properly designed simulation procedure, whose practical validity also requires checking the generator and sampling implementation.
Theorem/proposition
Theorem 2.1.6
(Mean and variance of independent replications)
Suppose are independent identically distributed real random variables with mean and finite variance , and is fixed in advance. Then
For , the sample variance satisfies .
Proposition 2.1.7
(A finite-sample error guarantee)
Under the same assumptions, for every ,
If a valid deterministic bound is known and , choosing guarantees error less than with probability at least . The bound may be conservative. Substituting a random sample variance for does not preserve this particular guarantee automatically.
Proof sketch or proof idea
Proof
(Expanding the centered sum and the sample-variance identity)
Linearity of expectation proves unbiasedness without needing independence. To compute variance, center each output and expand the square of the sum. Independence makes the cross expectations zero. There remain copies of , divided by , giving the variance and mean squared error formulas.
For the sample variance, use the deterministic identity
The expectations on the right are and . Dividing their difference by proves the claim. This also explains why the denominator differs from the descriptive variance of the observed records.
Proof X-ray
Where independence enters and where it does not
Unbiasedness of uses only linearity, so it survives any dependence between replications. Independence is used at exactly one point: the expanded square of contains cross terms , and only uncorrelatedness makes them vanish. The sample-variance step uses that variance formula once more, through . The identity itself is deterministic algebra, so subtracting the single term from is what produces the denominator .
The probability bound needs only the variance formula just proved.
Proof
(Markov's inequality applied to the squared error)
Apply Markov's inequality to the nonnegative variable : its expectation is , while the event of interest forces it to be at least . This is Chebyshev's inequality in the present setting. The sample-size formula simply rearranges the resulting bound. A deterministic error target of zero would require a different argument; no finite choice of makes the displayed bound vanish for positive variance.
The central limit theorem gives an additional asymptotic statement for independent identically distributed outputs with positive finite variance: the normalized average approaches the standard normal distribution. It motivates intervals using approximately estimated standard errors for nominal coverage. Such intervals are approximations, not consequences of the finite-sample bound above. Very skewed outputs, rare events and small samples can make the approximation poor.
Worked examples
Worked example 2.1.8
(Integrating a square and planning a sample budget)
Let . Direct integration gives and , so . For , the standard error is . The uncertainty shrinks as , so halving this standard error requires four times as many independent replications.
For an absolute error target and failure probability at most , the finite-sample guarantee asks for , so replications suffice. The calculation uses the known variance of this teaching example. In a real integral, estimating variance from a pilot run can guide a budget, but the pilot estimate alone is not a deterministic upper bound. If only is known, the valid bound gives a more conservative budget of .
Worked example 2.1.9
(Rare events and an apparently perfect output)
For an event indicator , let the true probability be . Then . With , the standard error of the event proportion is . Chebyshev gives probability at most of an absolute error at least . A nominal normal interval has an approximate half-width if this standard error is appropriate; these are different types of statements.
Now suppose an event is much rarer, with . In independent trials, the probability of seeing no events is , about . The observed sample variance is then zero. Reporting zero uncertainty would be badly misleading: the data have not demonstrated that the event is impossible. A simulation plan must be able to resolve the scale of the target, especially when relative rather than absolute accuracy matters.
Worked example 2.1.10
(Antithetic pairs and a fair cost comparison)
Instead of using two independent uniform points, draw one and use the paired output . Its mean remains , since both and are uniform. Algebra gives . Integrating its square and subtracting yields .
For a budget of function evaluations, an ordinary estimator averages independent outputs and has variance . An antithetic estimator averages independent paired outputs and has variance , eight times smaller. Within a pair the evaluations are dependent by design; different pairs must be generated independently under the analysis. The comparison counts function evaluations, not just the number of averages. If pairing introduces substantial extra overhead, wall-clock efficiency needs a separate measurement.
Pairing is not a universal improvement. For , one has , so each pair repeats the same output. At a fixed evaluation budget this wastes one of the two evaluations relative to independent sampling. The variance benefit depends on negative covariance for the chosen integrand.
Common mistakes
Counterexample mode
A long file is not a large independent sample
The false claim is that averaging outputs always divides variance by . Draw a single random variable of positive finite variance, and set every output . Each marginal distribution is correct, yet the average equals and has variance for every . In general the variance of an average also includes all cross covariances. Repair the claim by checking independence, or by using an analysis that explicitly controls dependence. Reusing an identical stream on each worker can create this failure in an otherwise correct program.
Common mistake
(Treating a fixed seed or nearby seeds as a proof of independence)
A fixed seed demonstrates repeatability, not unbiasedness, independence or accuracy. For parallel work, assign draws by a documented scheme of disjoint generator substreams or supported independent-stream facilities. Merely choosing nearby integer seeds is not a proof that streams have the desired properties. Record which replication indices belong to each worker, and ensure that retries do not create extra accepted replications or silently discard difficult outputs.
Common mistake
(Stopping when the interval looks good)
Stopping as soon as an estimated interval becomes attractive is also a change to the procedure. The fixed- theorem does not automatically apply to a data-dependent stopping time. Decide a budget in advance for this analysis, or use a sequential method with its own valid guarantee. A pilot run should be labeled as such, and its role in choosing the final estimator should be explicit.
Summary
Monte Carlo accuracy depends on the distribution of a complete replication and the dependence between replications. Unbiasedness, variance and reproducibility answer different questions. A finite variance yields a root-sample-size error scale and a conservative finite-sample probability bound. Variance reduction should be compared at a common computational budget, while model and discretization errors require separate analysis.
Exercises
Exercise 2.1.11
(Let . Find its expectation and variance. For , use Chebyshev's inequality to bound the probability that the sample mean differs from its target by at least .)
Foundation
Solution · Answer
Since and , the expectation is and variance is . The sample mean variance is . Chebyshev bounds the required probability by . This is an upper bound, not an equality or a normal-approximation probability.
Exercise 2.1.12
(An estimator has standard error at independent replications. Under an unchanged output distribution, how many replications are needed to reduce it to ? State what this scaling does not address.)
Foundation
Solution · Answer
The target standard error is one quarter of the old one. Because standard error is proportional to under the stated assumptions, the sample count must grow by sixteen, to . This does not correct model error, discretization bias, dependence introduced by an implementation mistake, or a change in the output variance.
Exercise 2.1.13
(For , form the antithetic paired output. Find its variance and compare with two independent evaluations. Explain why this exact success does not establish a universal rule for every integrand.)
Core
Solution · Answer
The pair average is for every draw, so its variance is zero. Averaging two independent uniform evaluations instead has variance . The cancellation works because the integrand is linear and the paired arguments sum to one. For a symmetric integrand such as , the two paired outputs coincide and do not create this cancellation.
Exercise 2.1.14
(Four workers each use the same sequence of independent mathematical outputs. The reducer averages all recorded values. Find the estimator's variance in terms of the individual variance , and specify a reproducibility record that would help detect the error.)
Core
Solution · Answer
Every distinct output appears four times, so the recorded average equals the average of just the original distinct outputs. Its variance is , not . Record the generator algorithm, seed or stream identifier, replication-index range, sample count and stream-allocation rule for every worker. Identical stream identifiers and index ranges would expose the duplication. Changing only the final reduction tree cannot fix the dependence.