Math paradoxes

Glossary / Bootstrap

Glossary · bootstrap

Rerun the survey without asking anyone new

You have 50 orders and you have computed the average order value. How far can you trust it? The honest answer is to collect a thousand more such weeks and watch how the number jumps. The bootstrap does this without a single new order: a thousand times it draws 50 orders from your own 50, putting each one back. Every such copy loses about a third of your data and repeats some of the rest. And yet the spread of these "damaged" copies is almost the same as that of real new weeks.

In plain wordspictures, analogies, small numbers

“In plain words” is hidden on all puzzles.

How many orders get lost

A resample works like this: 50 times we pick one of your 50 orders at random, write it down and put it back. So the same order can come up twice or three times, and another one not at all.

What share of your 50 orders usually doesn't make it into a resample even once?

A thousand weeks out of one

In the simulation we know the whole shop: the true average order is $40, and single orders mostly run from $10 to $100, occasionally more. You see only 50 orders from one week. Press "Resample ×1000": the dark pile shows the averages of a thousand resamples. The grey pile is what you never get to see in real life: a thousand genuinely new weeks of 50 orders. Compare their widths.

1,000 resamples1,000 real new weeksyour weekthe truth

Spread of resamples–
Formula s / √n–
Real spread–

Notice that the dark pile sits around your week, not around the truth. The bootstrap doesn't tell you where the true average is. It tells you how far your number could have jumped, and that is exactly what the "±" in a report and a confidence interval need. For a median or a return rate there is no handy formula at all, so the bootstrap is often the only simple way to get the error.

Why damaged copies don't lie

An explanation without formulas, slightly simplified. A new week in the real shop means 50 new customers drawn at random from everyone. You can't visit everyone, but your 50 orders are the best portrait of the shop you have: small and large orders appear there in roughly the right proportion. A resample "visits" this portrait the way you would visit the shop. That some orders are missing and others repeat is not a flaw but the whole point: a new week would also miss some customers and bring several similar ones. That randomness is the very error we are after.

So the bootstrap is only as good as your portrait. If not a single big client happened to land among your 50 orders, the resamples won't learn about them either. And if the sample is biased, say you only surveyed people who answer the phone, the bootstrap will carefully measure the error of a biased number.

Rigoroustables, charts, formulas

“Rigorous” is hidden on all puzzles.

What the bootstrap is

The bootstrap is a way to estimate the error of any number computed from a sample, without a formula: you repeatedly draw a new sample of the same size from the sample itself, with replacement, and watch how the result changes. The steps:

  1. You have n values and a number computed from them: a mean, a median, a rate, the difference between two groups.
  2. Draw n values at random with replacement and compute the same number.
  3. Repeat 1,000–10,000 times.
  4. The standard deviation of these numbers is the bootstrap estimate of the standard error. The range between the 2.5th and 97.5th percentiles is a simple 95% confidence interval.

Share left out: (1 − 1/n)ⁿ → 1/e ≈ 0,368  ·  for the mean: SE* = σ̂ / √n = √((n − 1)/n) · s / √n

Each order is missed on a single draw with probability 1 − 1/n, and over n draws with probability (1 − 1/n)ⁿ. For the mean, the bootstrap reproduces the known formula almost exactly: the spread of the resamples equals σ̂ / √n, where σ̂ is the spread of your n values. It differs from the usual s / √n by a factor of √((n − 1)/n), which is 0.99 for 50 orders. In other words, the bootstrap "invented" the standard error formula on its own, knowing nothing about it.

Sample nLeft outDistinct valuesRecord kept

"Left out" is the share of values missing from a resample; "Distinct values" is how many different values remain in it; "Record kept" is the chance that the sample's largest value made it into the resample.

When to use what

  • A mean or a rate, plenty of dataThe formula σ / √n is enough: the bootstrap gives the same, only slower. It is useful as a check that you got the formula right.
  • Median, percentile, ratioThe median order, the 90th percentile of load time, revenue per user, the difference of medians in an A/B test. Either there is no formula or it is complicated and fragile. Here the bootstrap is the first choice.
  • Resample people, not sessionsIf one person contributes several rows of data, you draw the person with all their rows. Otherwise the resamples come out too calm and the error is understated. For time series, likewise, you draw whole weeks or blocks of days.
  • A small, skewed sampleWith 50 orders from this shop, the ±2 bootstrap-error interval covers the truth in about 92% of cases, not 95%. The smaller the sample and the longer the tail of big orders, the more optimistic the bootstrap. It is no substitute for more data.
  • How many resamplesFor the error itself 1,000 is enough: the error of the error estimate is then about 2%. For the edge of an interval, the 2.5th percentile, 10,000 is better.
Deepergeneralisations, theory, history

“Deeper” is hidden on all puzzles.

Where the bootstrap goes blind: records

Switch the simulation to "Largest order". The dark pile turns into a single bar: in 63.6% of resamples the largest order is the same as in your week, because your record makes it into a resample with probability 1 − (49/50)⁵⁰. A resample can never go above it: it only knows the numbers you have already seen. Yet the real record of a new week beats yours in exactly half of cases: which of two weeks holds the bigger record is down to chance. In a typical week the spread of the resamples for the record is about three times smaller than the real one.

The same goes for anything that depends on the edges: the maximum, the minimum, the rarest event. The bootstrap works for numbers that rest on many values at once, like the mean or the median, and fails for those that rest on a single one.

Where the name comes from

  • Efron, 1979The method was described by the Stanford statistician Bradley Efron in "Bootstrap methods: another look at the jackknife" (The Annals of Statistics, 1979). The name comes from the idiom "to pull yourself up by your bootstraps": getting something that seemingly can't be had from anywhere.
  • The jackknifeThe bootstrap's forerunner is the jackknife of Quenouille (1949) and Tukey (1958): drop one value at a time from the sample and watch how the result changes. The bootstrap generalised the idea, but it needed computers, which were just becoming available in the 1970s.
  • The prizeIn November 2018 Efron was awarded the International Prize in Statistics for the bootstrap; it was presented at the 2019 World Statistics Congress.
  • The same 37% in machine learningLeo Breiman's bagging (1996) and random forests (2001) train each tree on a resample. The roughly 37% of the data left out of it becomes a ready-made test set for that tree.

Where it shows up

More on “Data and experiments”

All terms →