Error Bounds for Bounded Simulation Outputs

Why Bound Simulation Error Without a Normal Approximation?

A simulation estimate is random because it depends on a finite collection of simulated outcomes. When each output has a known finite range, Hoeffding’s inequality provides a way to control the estimation error at a specified confidence level, without estimating the output variance or relying on a large-sample normal approximation. The resulting bound is valid for a fixed sample size, but it can be conservative.

For example, suppose a hypothetical insurer simulates whether each policyholder’s annual payment exceeds a specified amount. Each simulated output is either 0 or 1, so its range is known even when the probability being estimated is not. The same idea applies to bounded dollar payments or other bounded simulation quantities. The method is aligned with the SOA Exam ASTAM (Advanced Short-Term Actuarial Mathematics) syllabus.

Definition: Let $X_1,\ldots,X_n$ be independent simulation outputs, each taking values in a known interval $[a,b]$. Write $R=b-a$ for the interval width and $\bar X=n^{-1}\sum_{j=1}^n X_j$ for their sample mean. If the outputs are identically distributed with mean $\mu=E[X_j]$, then $\bar X$ estimates $\mu$. More generally, for independent outputs with possibly different means, it estimates the average $n^{-1}\sum_{j=1}^n E[X_j]$.

Hoeffding’s Inequality and the Confidence Bound

For independent $X_j$ with $a\le X_j\le b$, Hoeffding’s inequality gives, for every $\varepsilon>0$,

P\left(\left|\bar X-\frac{1}{n}\sum_{j=1}^n E[X_j]\right|\ge \varepsilon\right) \le 2\exp\left(-\frac{2n\varepsilon^2}{(b-a)^2}\right).

In the identically distributed case, the average of expectations in this expression is $\mu$. The inequality is finite-sample: it holds for each positive integer $n$, provided the independence and range assumptions hold. The bound does not require a normal distribution or a known variance.

Theorem: For independent outputs in a common known interval $[a,b]$, a two-sided confidence bound with failure probability at most $\alpha$, where $0<\alpha<1$, is

P\left(\left|\bar X-\mu\right|\le (b-a)\sqrt{\frac{\ln(2/\alpha)}{2n}}\right)\ge 1-\alpha

when the outputs are identically distributed with mean $\mu$. Thus the interval centered at the simulated mean has a guaranteed coverage of at least $1-\alpha$. It is a conservative guarantee: actual coverage may be higher. If the quantity of interest is the average of different output means, replace $\mu$ by that average.

Why the Inequality Holds

The key fact is that a bounded random variable has a controlled exponential moment. Hoeffding’s lemma states that if $a\le X_j\le b$, then, for real $t$,

E\left[\exp\{t(X_j-E[X_j])\}\right] \le \exp\left(\frac{t^2(b-a)^2}{8}\right).

To bound an upper-tail deviation, apply Markov’s inequality to the nonnegative random variable $\exp\{t\sum_j(X_j-E[X_j])\}$, with $t>0$. Independence lets the exponential moments multiply. For any $t>0$, this gives

P\left(\bar X-\frac{1}{n}\sum_{j=1}^nE[X_j]\ge\varepsilon\right) \le \exp\left(-tn\varepsilon+\frac{nt^2(b-a)^2}{8}\right).

The exponent is minimized at $t=4\varepsilon/(b-a)^2$. Substituting this value gives the one-sided bound $\exp\{-2n\varepsilon^2/(b-a)^2\}$. Applying the same argument to the lower tail and adding the two probabilities gives the factor 2 in the two-sided inequality. Finally, set the right-hand side equal to $\alpha$ and solve for $\varepsilon$; this yields the stated confidence bound.

Identify the target and output.
Define one simulation output $X_j$ so that the sample mean estimates the quantity of interest.

Establish a valid range.
Find fixed bounds $a$ and $b$ that contain every possible output, not merely the outputs observed in the run.

Choose confidence or tolerance.
Use the confidence-bound formula to find an error allowance, or rearrange it to plan the sample size.

Report the guarantee in context.
State the sample mean, the bound, the confidence level, and the assumptions supporting the result.

Worked Examples

Worked Example: Bounding a Simulated Exceedance Probability

A hypothetical model simulates whether a policy’s annual payment exceeds $8,000. For each independent simulation, record $X_j=1$ if it does and $X_j=0$ otherwise. In 1,000 simulations, 173 outputs equal 1. Find a 95% Hoeffding confidence interval for the exceedance probability $p=E[X_j]$.

Method. This is a sample mean of independent Bernoulli outputs. Every output lies in the known interval $[0,1]$, so $R=1$. The observed mean is

\bar X=\frac{173}{1000}=0.173.

For 95% confidence, $\alpha=0.05$, so $\ln(2/\alpha)=\ln(40)=3.688879\ldots$. With $n=1000$, the error allowance is

\varepsilon =1\sqrt{\frac{\ln(40)}{2(1000)}} =\sqrt{\frac{3.688879\ldots}{2000}} =\sqrt{0.0018444397\ldots} =0.0429469\ldots.

The interval is $0.173\pm0.0429469\ldots$, giving endpoints $0.1300531\ldots$ and $0.2159469\ldots$. To four decimal places, the Hoeffding interval is $[0.1301,0.2159]$. Its guaranteed coverage is at least 95% under the stated model.

Check. The half-width is positive and the interval contains the observed estimate $0.173$. The common mistake this avoids is treating 173/1,000 as the exact probability; it is an estimate, and the bound quantifies its possible simulation error.

Worked Example: Planning a Conservative Simulation Size

A hypothetical simulation estimates an event probability using outputs in $[0,1]$. How many independent simulations are sufficient to ensure that the absolute error of the sample mean is at most 0.005 with at least 90% confidence?

Method. Use the two-sided Hoeffding bound and solve for $n$. Here $R=1$, $\varepsilon=0.005$, and $\alpha=0.10$, so $\ln(2/\alpha)=\ln(20)$.

2\exp(-2n(0.005)^2)\le 0.10

Taking logarithms and rearranging,

n\ge \frac{\ln(2/0.10)}{2(0.005)^2} =\frac{\ln(20)}{0.00005} =59{,}914.64547\ldots \approx59{,}914.65.

The sample size must be an integer and must meet or exceed the unrounded bound. Therefore $n_{\min}=\lceil59{,}914.64547\ldots\rceil=59{,}915$.

Check. Rounding upward gives a value no smaller than the required bound. The common mistake is to truncate the product or round the final sample size down; either can fail to meet the requested guarantee.

Worked Example: A Wider Monetary Output Range

A hypothetical simulation produces independent annual net payments, each guaranteed by the model to lie between $2 and $5. Determine the number of simulations needed for a two-sided 99% Hoeffding error bound of at most $0.05 in the estimated mean payment.

Method. The interval width is $R=5-2=3$. Use $\alpha=0.01$ and $\varepsilon=0.05$ in the sample-size formula:

n\ge \frac{R^2\ln(2/\alpha)}{2\varepsilon^2} =\frac{3^2\ln(200)}{2(0.05)^2} =\frac{9\ln(200)}{0.005}.

Using $\ln(200)=5.2983173665\ldots$,

n\ge 9{,}536.971259\ldots\approx9{,}536.9713.

Therefore the minimum integer sample size is $n_{\min}=9{,}537$. The width is $3, not $5: the relevant quantity is $b-a$, not the upper endpoint alone.

Check. Substituting $n=9{,}537$ satisfies the unrounded requirement, whereas $n=9{,}536$ does not. The common mistake is to use the rounded logarithm as if exact, or to use the range endpoint rather than the range width.

Choosing the Bound and Interpreting Its Limits

For a desired absolute error $\varepsilon$, rearranging the inequality gives the conservative sample-size rule

n\ge \frac{(b-a)^2}{2\varepsilon^2}\ln\left(\frac{2}{\alpha}\right), \qquad n_{\min}= \left\lceil \frac{(b-a)^2}{2\varepsilon^2}\ln\left(\frac{2}{\alpha}\right) \right\rceil.

This rule makes the design trade-offs explicit. A narrower valid output range or a larger tolerated error reduces the required sample size; a higher confidence level (smaller $\alpha$) increases it. The dependence on the tolerance is quadratic: halving $\varepsilon$ multiplies the required sample size by four, all else equal.

The interval $[a,b]$ must be a deterministic bound justified by the model or the simulation design. The smallest and largest values seen in one finite run are not, in general, valid bounds on future outputs. For example, a sample of Bernoulli outputs may contain no 1s, but that does not establish that a 1 is impossible. If outputs are importance-weighted or otherwise transformed, their bounds must apply to the transformed outputs actually averaged.

Independence is also essential to this result. Correlated simulation outputs cannot simply be treated as independent observations in the formula. Further, Hoeffding’s inequality concerns the simulation error for the specified output and target; it does not automatically account for uncertainty in model parameters or other sources of error.

A common exam trap is to use a familiar standard-error formula when the question asks for a guaranteed finite-sample bound, or to present a Hoeffding interval without verifying boundedness. The method is especially useful when a rigorous conservative guarantee is required and a trustworthy finite range is available. It may be loose compared with methods that use variance information, but it does not need that information.

Key takeaway: For independent outputs known to lie in $[a,b]$, the two-sided Hoeffding error allowance is $(b-a)\sqrt{\ln(2/\alpha)/(2n)}$. Use a valid range, specify the target mean, and round any required sample size upward.

Check Your Understanding

For each problem, assume independent simulation outputs and use the two-sided Hoeffding bound. Round probability or error bounds to four decimal places and sample sizes upward.

A simulated indicator has range $[0,1]$, with $n=2{,}000$ and a 90% confidence level. What is the Hoeffding error allowance around the sample mean? (Answer: $\varepsilon=\sqrt{\ln(20)/4{,}000}\approx0.0274$.)
A payment output is known to lie in $[0,250]$. With $n=500$, what is the 95% error allowance in dollars? (Answer: $250\sqrt{\ln(40)/1{,}000}\approx\$15.18$.)
For outputs in $[1,4]$, how many simulations are sufficient for error at most 0.10 with 95% confidence? (Answer: $\left\lceil9\ln(40)/0.02\right\rceil=1{,}660$.)
For outputs in $[0,1]$, how many simulations are sufficient for error at most 0.02 with 99% confidence? (Answer: $\left\lceil\ln(200)/0.0008\right\rceil=6{,}623$.)
A sample of $1{,}200$ outputs has mean 2.4, and every possible output is known to lie in $[0,6]$. Find the 95% Hoeffding interval for the target mean. (Answer: $2.4\pm6\sqrt{\ln(40)/2{,}400}=2.4\pm0.2352$, or approximately $[2.1648,2.6352]$.)

What You'll Learn