1.9 Extreme values and heavy tails
Handling “almost never happens”
What you will learn
- Explain what a heavy-tailed distribution is, and see the danger of estimating rare events by assuming a normal distribution
- Explain, using “once-in-n” values, why the worst value (the extreme value) grows as the number of trials increases
- Explain the idea of extrapolating accident rates from near misses (extreme value theory) and its limits
Build intuition
With the normal distribution in 1.3, only 0.27% of values fall outside ±3σ of the mean. That makes it tempting to think “a 3σ margin is enough”.
Yet some real-world data behave calmly most of the time and then, every so often, go wildly off. A sensor’s range error may be a few centimetres almost always, yet occasionally be far off because of reflections or occlusion. A person’s reaction time is usually about a second, but can exceed three seconds when they are looking away. Distributions whose ends — their tails — are much thicker than the normal distribution’s are called heavy-tailed distributions.
A margin sized on the normal assumption — “exceeding 6σ happens once in a billion” — might be breached once in a thousand if the real tail is heavy. The mean and standard deviation alone do not determine the probability of rare events.
Another important habit is to look not at the average but at the worst value (the maximum or minimum, together called extreme values). The “closest call” in one day of testing will be milder than the closest call over a whole year. The more trials you run, the worse the worst value becomes. Just as a river levee is designed for a “once-in-a-century flood”, safety evaluation asks “how bad a value appears how often?”
Think about rare events with statistics of the ends
The probability of a rare event is set not by the middle of the distribution but by the shape of its tail. Do not apply the normal distribution’s 3σ or 6σ blindly: check the tail with real data and evaluate with statistics of the worst values.
Check with math
① Comparing tail probabilities
For the two distributions in the figure, the probability of a value at least kσ above the mean (one-sided) is:
| k | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| Normal | 2.3% | 0.13% | about 1 in 30,000 | about 1 in 3.5 million | about 1 in a billion |
| Heavy-tailed | 2.0% | 0.69% | 0.31% | 0.16% | 0.095% |
The normal tail shrinks dramatically with distance, like \(e^{-k^2/2}\). Many heavy-tailed distributions, by contrast, have tails that shrink only slowly, as a “power”:
Here a measures how heavy the tail is: the smaller a, the heavier the tail (a = 3 in the figure). Doubling x reduces the probability only by a factor of \(2^a\). When a is 2 or less, the variance is infinite, and the σ of 1.4 and the central limit theorem of 1.5 no longer work as they are — a single extreme value that happens to turn up can throw the mean and σ around wildly.
② “Once-in-n” values (return levels)
The value \(x_n\) that is exceeded only with probability 1/n is the “once-in-n value”, or return level. The n — like the “century” in a once-in-a-century flood — is the return period.
| n (number of trials) | 100 | 10,000 | 1 million |
|---|---|---|---|
| Normal | 2.3σ | 3.7σ | 4.8σ |
| Heavy-tailed | 2.6σ | about 13σ | about 60σ |
With around 100 tests, the two distributions are hard to tell apart. But the once-in-a-million value of the heavy-tailed distribution reaches more than ten times as far. Fitting a normal distribution to the worst values of a short test and using it to estimate the worst value over long operation can be wrong by orders of magnitude.
③ Extrapolating from near misses (peaks over threshold)
As we saw in 1.8, demonstrating an accident rate by counting accidents themselves requires an enormous driving distance. An alternative is to collect near misses — events far more frequent than accidents, such as situations with a short time to collision (TTC) — and extrapolate “the probability of going all the way to a collision” from the shape of their tail.
If you collect only the events that exceed a threshold (say, TTC below 1.0 s), and the threshold is strict enough, the distribution of how far they exceed it approaches a fixed shape — the generalized Pareto distribution — whatever the original distribution. This is extreme value theory, a “tail version” of the central limit theorem in 1.5. The simplest form is:
Y is how far an event goes past the threshold (here 1.0 − minimum TTC, in seconds) and b is a typical size of that excess. Suppose there are 200 near misses with TTC below 1.0 s per million km, and the data give b = 0.15 s. A collision means a minimum TTC of 0, i.e. Y ≥ 1.0, so
The accident rate is then about 200 × 0.00127 ≈ 0.25 per million km — about one per 4 million km. Showing the same with the rule of three in 1.8 would take about 12 million km without a single accident.
This extrapolation, however, depends heavily on the assumed tail shape. The general form adds \(\xi\) (xi), which describes how heavy the tail is:
\(\xi = 0\) gives the simple form above; the larger \(\xi\), the heavier the tail. Changing the assumptions only slightly changes the result a lot:
| Assumption | Probability of reaching a collision | Estimated accident rate |
|---|---|---|
| b = 0.15 s, ξ = 0 | 0.13% | about 1 per 4 million km |
| b = 0.20 s, ξ = 0 | 0.67% | about 1 per 740,000 km |
| b = 0.15 s, ξ = 0.1 | 0.61% | about 1 per 830,000 km |
| b = 0.15 s, ξ = 0.2 | 1.4% | about 1 per 350,000 km |
A small difference in the tail shape changes the estimate more than tenfold. Extrapolation is a powerful tool, but always attach a range (a confidence interval) to the estimate, and check that the conclusion holds when the threshold or the assumptions change.
Advanced: putting a range on the extrapolation (the bootstrap)
The “about one per 4 million km” in ③ is a single value based on b = 0.15 s, estimated from 200 near misses. Since b varies with the scatter of the data at hand, the accident-rate estimate needs a range too (1.6). But the path from b to the accident rate goes through an exponential, so a formula for “estimate ± 2 × standard error” as in 1.6 is not easy to write down. A general-purpose method for such cases is the bootstrap.
- From the 200 recorded excesses, draw 200 again “with replacement” (resampling): some events may appear twice and others not at all
- Estimate b from this pseudo-data and carry the calculation through to the accident rate, as in ③
- Repeat steps 1 and 2 a thousand times, and take the 2.5% and 97.5% points of the thousand accident rates as the interval
In this example the estimate of b wanders between about 0.13 and 0.17 s, and the accident rate spans roughly one per 1.7 million km to one per 11 million km — a factor of nearly three either way (illustrative figures). Because of the exponential, a ±14% scatter in b turns into a several-fold scatter in the accident rate. The result of a tail extrapolation should always be reported together with this range.
The advantage of the bootstrap is that the same procedure gives a range for complicated calculations and for quantiles such as the 99.9% point. But the range only reflects the random scatter of the data at hand. It does not include the error from a wrong tail-shape assumption (ξ), or from data that do not represent the ODD (the same caution as in the “Connection” box of 1.6). It is also known that for quantities extrapolated beyond the data, the range tends to come out narrower than it really is. → 5.5, 5.8
How to set ξ. Like b, ξ is estimated from the excesses over the threshold (maximum likelihood is the standard choice). With few excesses, however, ξ is hardly determined at all: even with 200 excesses its standard error is about 0.07 (a large-sample guide), so the gap between ξ = 0 and 0.1 in the table of ③ is only about one standard error. So place a value on the unfavourable side, such as the upper end of the confidence interval of ξ, and show that the requirement is still met. A larger ξ gives a worse accident rate, so this is the conservative choice. Give the value a justification: the interval, other data, or a physical reason. Note that this cannot check whether the generalized Pareto distribution is a good approximation at all; combine it with checks at other thresholds and with other evidence (→ 5.8).
Connection to automated driving
- Do not take “3σ” or “6σ” margins at face value: sensor range errors, localization errors and processing delays occasionally go far off because of reflections, occlusion or load spikes. Check the tails with real data, and design with high percentiles (such as the 99.99th) or statistics of the worst values rather than the mean and σ. → 4.3 Sensors and fusion, 5.3 Functional insufficiencies and triggering conditions
- Look at the worst side, not the average: a good average TTC or a small average error does not guarantee safety. Danger lives at the ends of the distribution, so evaluate with distributions of extreme values such as the minimum TTC. Assume that the worst value seen in a short test will get worse over longer driving.
- Count the events just before accidents: extreme value theory lets you estimate accident rates before accidents happen, helping with the “driving distance wall” of 1.8. But it assumes that near misses and accidents arise from the same mechanism, so it cannot capture accidents that happen without a preceding near miss, such as sudden failures. The result also depends on what you count as a near miss (TTC, required deceleration, and so on).
- Unknown hazards hide in the tails: a heavy tail means that rare, extreme situations account for most of the risk. Piling up kilometres rarely brings you face to face with them, so you have to search deliberately for dangerous conditions (importance sampling, scenario search). → 5.8 Searching for unknown hazards
Summary
- In a heavy-tailed distribution, extreme values are far more likely than in a normal distribution with the same mean and σ. Do not apply the normal distribution’s 3σ or 6σ carelessly
- The more trials, the larger the worst value (the extreme value). Think in terms of “once-in-n” values (return levels)
- Extreme value theory lets you extrapolate from events beyond a threshold (near misses) to rarer events (accidents) — but the result depends heavily on the assumed tail shape
Quick quiz
Q1. Assuming a normal distribution, the probability of a value 6σ or more from the mean is about 1 in a billion. If the real data are heavy-tailed, what tends to happen to this estimate?
It tends to be far too optimistic (too small). In the figure’s example, the probability of exceeding 6σ was about 1 in 1,000 — roughly a million times the normal estimate.
Q2. The same vehicle is tested over 10,000 km and over 1 million km. In which test is the “minimum TTC” (the closest call) likely to be smaller?
The 1-million-km test. The more trials (distance), the rarer and more extreme the situations you meet, so the worst value gets worse. Do not mistake the worst value of a short test for the true worst case.
Q3. There are 200 near misses with TTC below 1.0 s per million km, and the probability that one of them goes all the way to a collision is estimated at 0.001. What is the accident rate?
200 × 0.001 = 0.2 per million km — about one per 5 million km. But the “0.001” depends heavily on the assumed tail shape, so treat it with a range.
Q4. What kinds of accidents are hard to capture by extrapolating from near misses?
Accidents that happen without a preceding near miss — for example, sudden failures, or situations of a kind never encountered before (unknown scenarios). No precursor events are recorded, so there is nothing to extrapolate from.
Further reading
- Next lesson: 2.1 What is machine learning?
- Related: 1.3 Probability distributions, 1.5 Law of large numbers and the central limit theorem, 1.8 Statistics of rare events, 5.8 Searching for unknown hazards
- Glossary: Heavy-tailed distribution / extreme value, Return level / return period, Extreme value theory / peaks over threshold, Time to collision (TTC), Importance sampling, Bootstrap
- Video lecture: YouTube (about 5 minutes) (the key points explained with slides and narration; the Japanese article has a Japanese video)
- References
- S. Coles, An Introduction to Statistical Modeling of Extreme Values, Springer, 2001.
- P. Songchitruksa, A. P. Tarko, “The extreme value theory approach to safety estimation,” Accident Analysis & Prevention, 38(4), 2006.
- D. Åsljung, J. Nilsson, J. Fredriksson, “Using Extreme Value Theory for Vehicle Level Safety Validation and Implications for Autonomous Vehicles,” IEEE Transactions on Intelligent Vehicles, 2(4), 2017.