Basis Lab

Answers · The mathematics underneath

Why does cutting the error in half require four times as many samples?

In shortThe error shrinks in proportion to one over the square root of the sample count, so halving it needs four times the samples.

Halving the error needs four times as many samples. The typical error of a simulated average is the spread of one draw divided by the square root of the number of draws, so the sample count sits under a square root and precision is bought at a quadratic price.

se⁡=sn\operatorname{se} = \frac{s}{\sqrt{n}}

Take a quantity whose single computed draw has spread s=1s=1 and take n=10,000n=10{,}000 draws. The standard error is 1/10,000=1/100=0.011/\sqrt{10{,}000}=1/100=0.01. To halve it to 0.0050.005, solve 1/n=0.0051/\sqrt{n}=0.005: the square root of nn must be 200200, so n=2002=40,000n=200^2=40{,}000. That is four times the original count, not twice. Doubling the draws would give 1/20,000≈0.007071/\sqrt{20{,}000}\approx 0.00707, a reduction of about 29 per cent, not 50 per cent.

n′=4nbecauses4n=12snn' = 4n \quad\text{because}\quad \frac{s}{\sqrt{4n}} = \frac{1}{2}\frac{s}{\sqrt{n}}

The linear guess

The natural guess is that error falls in proportion to the number of draws: double the samples, halve the error. That would be true if errors added up, but they do not. Each draw contributes a deviation from the true value, and independent deviations partly cancel. The variance of a sum of nn independent draws is ns2n s^2, so the variance of their average is s2/ns^2/n. The spread is the square root of that variance, s/ns/\sqrt{n}, which is why the count enters as a square root. Four times as many draws give twice as much cancellation in the standard deviation, not four times.

FIG 1
drawsstandard errordraws relative to row above
1000.1baseline
4000.054
1,6000.0254
6,4000.01254

One more reliable decimal digit means reducing the error by a factor of ten, so the sample count rises by 102=10010^2=100. From n=10,000n=10{,}000, where the error is 0.010.01, three digits needs error 0.0010.001 and therefore n=1,000,000n=1{,}000{,}000: one hundred times as many draws. At a million draws per second that is one second, while four digits needs 100100 seconds and five digits needs 10,00010{,}000 seconds, about two hours and forty-seven minutes. The arithmetic is unforgiving because each digit multiplies the previous cost by a hundred, not by ten.

For an estimated probability the same square root appears with a known spread. A single draw is one on success and zero otherwise, its variance is p(1−p)p(1-p), and the standard error of the estimate after nn draws is p(1−p)/n\sqrt{p(1-p)/n}. At p=1/2p=1/2, aiming for a standard error of 0.010.01 needs n=0.25/0.012=2,500n=0.25/0.01^2=2{,}500; aiming for 0.0050.005 needs n=0.25/0.0052=10,000n=0.25/0.005^2=10{,}000, again four times. Planning at p=1/2p=1/2 is the safe choice because p(1−p)p(1-p) is largest there, so every other probability needs no more draws for the same error.

Where the square root stops helping

The rule assumes independent draws and a spread ss that stays put as nn grows. Correlated samples, or a simulation whose values become more variable as it runs, break the 1/n1/\sqrt{n} calculation, and the error bar computed from the samples will be too small. It also assumes the average is the thing being estimated; a maximum or a quantile has a different rate. When the quantity is a probability, a very small pp changes the practical arithmetic: the precision is governed by the number of successes, not the number of draws, so a one-in-a-million event can need hundreds of millions of draws before the estimate means anything. The cheap alternative is to reduce ss instead of raising nn: halving the spread of one draw does exactly what quadrupling the sample count does, and that is often the only way to make a precise run feasible.

Worth keeping

  • Standard error is the spread of one draw divided by the square root of the number of draws.
  • Halving a standard error requires four times the samples; gaining one decimal digit requires one hundred times.
  • For an estimated probability the standard error is the square root of p(1-p)/n, largest at p equal to one half.

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 How Far Off Is It, 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 pageThe whole course

Other questions people ask about this

  1. When should I give up on finding an exact formula and simulate instead?Give 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.
  2. Why does the average of many random samples get closer to the true value as I take more samples?Because the average of independent draws is centred on the true value at every sample size, and its typical distance from that value shrinks like one over the square root of the number of draws.
  3. How do I estimate the error of a statistic when I don't have a formula for it?Resample your own data many times, recompute the statistic each time, and use the spread of those results as the error bar.
  4. What is the difference between variance and standard deviation?They measure the same spread: variance is the average squared distance from the mean, standard deviation is its square root, so you report the standard deviation and calculate with the variance.
  5. How do you make a vague claim precise enough to tell whether it's true?Fix what is being talked about, what is asserted, which cases are covered and the cut-off, then name an observation that would prove it false.
  6. How do you find the parabola that best fits a function near a point?Match the function's height, slope and bending at the chosen point; those three conditions single out exactly one parabola.

Read alongside