Answers · The mathematics underneath

When should I give up on finding an exact formula and simulate instead?

In shortGive up on an exact formula when the quantity can be written as an average of something drawable, since simulation then gives an estimate with a measurable error.

Give up on the exact formula as soon as the quantity can be written as an average of something you can draw at random, and an exact closed form is either absent or intractable. The test is not whether the algebra is hard, but whether you can name a random draw $X$ , a computable $f$ from one draw, and check that the average of $f(X)$ is the quantity wanted. Most quantities worth knowing fail the first test for a formula, not the second: an integral with no elementary antiderivative, or a queue with abandonment, is perfectly definite and still has no usable closed form. The formula is the special case. Simulation is the default when the average rewriting exists.

Q = \mathbb{E}\big[f(X)\big] \qquad\text{estimated by}\qquad \hat{Q} = \frac{1}{n}\sum_{i=1}^{n} f(x_i)

The test in practice

Write the target as $Q=\mathbb{E}[f(X)]$ . For the average wait in a queue with abandonment, $X$ is one random day of arrivals and service times, $f(X)$ is the mean wait on that day, and the average over days is the long-run average wait. In the simplest queue with arrival rate 0.8 per minute and service rate 1 per minute, the mean wait in queue is $0.8/(1(1-0.8))=4$ minutes; add abandonment, or a server that slows when busy, and that formula stops. For an area under a curve on $[0,1]$ , $X$ is a point drawn evenly in the interval and $f(X)$ is the height of the curve there; the average height is the area because the width is one. For a probability, $f(X)$ is one when the event happens and zero otherwise, so counting hits out of trials is the same operation with a particular $f$ .

FIG 1From question to loop

step	question	the random draw	computed from one draw	the average	what happened
1	area under $x^2$ on $[0,1]$	$x$ uniform in $[0,1]$	$x^2$	the area, $1/3$	width is one
2	chance of at least three sixes in five dice	one roll of five dice	one if at least three are sixes, else zero	the probability, $23/648$	indicator average
3	average wait in a queue with abandonment	one random day of arrivals and service times	the mean wait on that day	the long-run average wait	no closed form

3 steps

Each row is the same move: name a drawable object, compute one number from it, and average. The queue row is the case with no closed form; the area and dice rows are there to check the arithmetic against known answers.

Take the area under $x^2$ from 0 to 1. The exact value is $\int_0^1 x^2\,dx=1/3$ . Draw $n=100000$ points uniformly, square each, average. The estimator is unbiased, and its standard error is the standard deviation of $X^2$ divided by $\sqrt n$ . Since $\mathbb{E}[X^4]=1/5$ and $(\mathbb{E}[X^2])^2=(1/3)^2=1/9$ , the variance of $X^2$ is $1/5-1/9=4/45$ .

\int_0^1 x^2\,dx=\frac13,\qquad \operatorname{SE}(\hat Q)=\sqrt{\frac{4/45}{100000}}=0.000943

For five dice and at least three sixes, the exact probability is also available. There are $6^5=7776$ equally likely rolls. The count is $10\cdot25+5\cdot5+1=276$ : ten ways to choose which three are sixes and two non-sixes, five ways for four sixes, one for five. So $p=276/7776=23/648=0.0354938$ . A hundred thousand trials gives about 0.0355, with one standard error $\sqrt{p(1-p)/100000}=0.000585$ . Two standard errors is 0.00117, so quote 0.0355 plus or minus 0.0012, not 0.0354938. The exact value is there for this toy; the simulation did not need it. The last digits of a single run are noise.

p=\frac{10\cdot25+5\cdot5+1}{7776}=\frac{276}{7776}=0.0354938,\qquad \operatorname{SE}=\sqrt{\frac{p(1-p)}{100000}}=0.000585

The natural guess is that a hard enough derivation will always end in a formula. It will not. Most integrals have no elementary antiderivative, and most systems with two or more random parts interacting have no closed form for anything about them. The queue with abandonment is a definite question with a definite answer, and the algebra has run out. Treating a formula as the only rigorous answer is a category error: a simulated estimate with a stated error is a measurement of the same quantity, and a formula that cannot be evaluated is not more exact in practice.

What the error costs

The price is exactness. The estimate changes from run to run, and the size of that change is estimable from the same samples. A simulated number should be quoted with uncertainty attached, as estimate plus or minus something, and never as a bare figure. If a downstream user sees 0.33331 they may treat the fourth decimal as information; it is usually noise. The error shrinks like $1/\sqrt n$ , so halving it needs four times the samples: the area estimate at $n=100000$ has standard error 0.000943, and at $n=400000$ it has standard error 0.000471.

\operatorname{SE}\propto \frac{1}{\sqrt n},\qquad n\to 4n \text{ halves the error}:\quad 0.000943\to0.000471 \text{ at } n=400000

Where it stops

The method stops being direct when $Q$ cannot be written as $\mathbb{E}[f(X)]$ with a drawable $X$ , or when the draw is from the wrong distribution. Then the average converges to the wrong number, and more samples only make the wrong number more precise. If $f(X)$ has infinite variance, the standard error from the samples is unreliable and the normal error rule can fail. A conditional average over the worst five per cent of years is a further warning: it throws away ninety-five per cent of draws, so its error is much larger than the raw sample count suggests. That case needs a deliberate sampling design, not a bigger loop.

Worth keeping

A quantity with no closed form can still be computed if it is the average of something drawable at random.
A probability is the average of a zero-one indicator, so counting hits out of trials estimates it.
A simulated estimate is incomplete without its error, and halving that error needs four times the samples.

Where this goes next

This question is one step of Answering With Random Samples, a course that works through its subject from the beginning. The page that teaches this part of it is When the Formula Runs Out, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course