Quantiles from Finite Samples and Their Confidence Bands

A percentile is a statement about a distribution, but the number printed on a report is computed from a finite list of observations. The gap between the two is the subject here: the sampling distribution of a quantile estimate is wide, it is asymmetric in a way that hides the uncertainty, and the sample sizes needed for a tail claim to mean anything are far larger than the sample sizes benchmarks usually collect.

A quantile is an order statistic

Given $n$ sorted observations $x_{(1)} \le \dots \le x_{(n)}$, the empirical $p$-quantile is some interpolation between the observations bracketing position $np$. Different definitions place the boundary slightly differently, and the resulting differences are largest for small $n$ and for extreme $p$, where adjacent order statistics are far apart.

The relevant property is the sampling distribution of the position. For continuous data, the number of observations at or below the true $p$-quantile is binomial with parameters $n$ and $p$. The $k$-th order statistic is therefore an estimate of the quantile at probability $k/(n+1)$ in expectation, and its uncertainty is the spread of a binomial count rather than a fixed offset. The standard deviation of that count is $\sqrt{np(1-p)}$, so the index of the estimated quantile moves by roughly that many positions from sample to sample.

The movement translates into a wide interval on the value axis whenever the density near the quantile is low, which is precisely the tail case of interest. At $p = 0.99$ and $n = 100$, the count at or below the true 99th percentile has mean 99 and standard deviation about 1. The estimate is therefore the last or second-to-last observation, and which one it lands on depends on chance. The reported p99 from 100 samples is a two-value lottery.

The distribution-free interval, and how it fattens

The binomial argument gives a distribution-free confidence interval for a quantile: find indices $l$ and $u$ such that the probability of the binomial count landing in $[l, u]$ is at least the desired coverage, then report $x_{(l)}$ and $x_{(u)}$. No assumption about the shape of the distribution is needed, only that observations are independent and identically distributed.

The interval’s width is governed by the binomial index spread, which scales as $\sqrt{n p (1-p)}$. In value terms, that index spread becomes a value spread by dividing by the local density. For a tail quantile the density is small, so a modest index spread becomes a large value spread.

The sample size needed for a tight tail interval follows from the same binomial quantity, measured in probability rather than in rank positions. The estimated tail probability has standard error $\sqrt{p(1-p)/n}$, so at $p = 0.99$ and $n = 100$ the standard error is about one probability point, and a three-sigma interval spans nearly $\pm 3$ points. That interval says the observation at the estimated tail could correspond to the 96th percentile or to the maximum of the sample, which is a claim too weak for most purposes. Reaching $\pm 0.3$ points at three sigma requires roughly ten thousand observations, since the standard error falls as $1/\sqrt{n}$. Whether even that is tight enough depends on how fast the tail rises, which is another way of saying that the useful precision is distribution-dependent even though the interval construction is not.

Why the printed number looks more certain than it is

A benchmark run reports a point estimate. If it reports an interval at all, the interval is usually computed under a normal approximation on the log values or by a bootstrap, and both can understate the uncertainty at extreme percentiles for small $n$.

The bootstrap has a specific failure mode here. Resampling with replacement from $n$ observations produces resamples that cannot contain more distinct extreme values than the original sample, so the bootstrap distribution of a p99 is bounded above by the largest observed value and piles mass on the top few order statistics. The resulting interval is too narrow on the right and cannot express the possibility that the true tail is heavier than anything observed, which is exactly the possibility that matters.

A second and more common problem is coordination between the quantile and the concurrency model. When a load generator issues a request, waits for the response, then issues the next, the request rate collapses whenever the system is slow. The slow period is sampled once, and the measured latencies are conditioned on the system keeping up. The resulting percentile describes a system that is never offered more load than it can handle, which is a different system from the one being characterised. Fixing this requires the generator to issue requests on a schedule independent of responses, so that samples are taken during stalls as well as during smooth operation.

Estimating the tail from a histogram

Systems that cannot retain every observation summarise into fixed buckets, and the quantile is then interpolated within the bucket that contains the target rank. The error introduced is bounded by the bucket width, so the bucket boundaries determine the accuracy of every tail claim the system can make.

The structural problem is that bucket boundaries are chosen when the metric is defined, based on an assumption about the range of values. A bucket layout with an upper bound at one second returns the highest bucket for every observation above it, so a slow period whose true p99 is several seconds is reported as a p99 of exactly the last boundary. Prometheus’s histogram documentation is explicit that the highest bucket is a special case for this reason: the value is a lower bound and the fraction in that bucket is an unbounded count.

Exponential bucket layouts bound the relative error instead of the absolute error, which is usually the right trade for latency. A layout with ratio $r$ between adjacent boundaries reports any value with a relative error of at most $r - 1$ in the interpolation, uniformly across the range, and the number of buckets needed for a wide range grows logarithmically in the range ratio rather than linearly.

import math

def bucket_index(value, base):
    """Exponential bucketing: constant relative error, O(log range) buckets."""
    if value <= 0:
        return 0
    return int(math.floor(math.log(value, base))) + 1

# base = 1.1 gives at most ~10% interpolation error per bucket
# a range from 1us to 1000s needs about 100 * log(1e9)/log(1.1) ~ 2516 buckets

The count is the point. Fine relative resolution across a wide range costs many series per metric, and the memory and storage cost of those series is what usually forces a coarser layout. Sample Sizes, Effect Sizes, and Confidence Intervals for A/B Comparisons takes up the comparison problem where the quantity being compared is a quantile rather than a mean, and the same binomial reasoning gives the interval on the difference.

What can honestly be claimed from a given sample

Three statements have very different requirements. A claim about the median needs few samples, because the density near the middle is highest and the binomial index spread translates to a narrow value interval. A claim about the mean is misleading for heavy tails, where a handful of large values dominates and the sample mean has no stable value until the sample size is far beyond what tail quantiles would need. A claim about a tail quantile needs enough samples that the rank is far from the ends of the sample, which for $p = 0.999$ means at least tens of thousands of observations before the estimate stops being the maximum of the sample.

When the available data cannot support the claim, the honest output is the order statistic with enough of its neighbours to show the spread, not a smoothed value. Reporting the largest few observations alongside the percentile communicates the shape of the tail and how much of the estimate rests on the last few positions in the sample, which is the information a reader needs in order to judge the figure. A percentile quoted with its sample size and with the top of the observed range can be interpreted; the same percentile alone cannot. The sample size needed for a tail claim to be meaningful is a power question in the sense of Power, the Minimum Detectable Effect, and the Cost of Repeated Looks, and it is usually the binding constraint when a benchmark is asked to support a claim about the worst case.