The question a sample can answer
A stream may be too large to sort or retain, but a user may still ask how many observations are at most a threshold, or request a median. The earlier reservoir unit constructs a uniform sample of occurrences in one pass without knowing the final length. We now use that sample to approximate ranks.
Definition 13.1.1
(Empirical distribution and its reservoir estimate)
Fix a finite, nonempty list of real values before making any sampling choices. Equal values at different positions are different occurrences. Let be a uniformly chosen -subset of the positions, with . The empirical distribution and its reservoir estimate are
Both functions use the same convention, “at most”. Their left limits count values strictly below the threshold. Multiplying by gives a rank count; an error in the fraction is an error of at most in that count. It is not a bound on the distance between the actual values.
A standard capacity- reservoir gives this subset law at a fixed final , provided that, for each position , it draws an integer uniformly from conditional on the prior history and replaces that numbered slot when the integer is at most . The full input list and final count must be fixed independently of this randomness. If the input is random, the same conclusion holds conditional on the list when it is independent of the sampler. Neither an input chosen in response to the reservoir nor a stopping rule based on the observed reservoir is covered by this argument.
One threshold: the finite-population variance
Proposition 13.1.2
(Mean and variance at one threshold)
For a fixed threshold and a uniform -subset with ,
The same formulas hold with replaced by for the fraction of inside any fixed set of positions.
Proof
(Indicator moments for a uniform subset)
Let be the number of successes. Writing gives
The second equality counts subsets containing both positions. The calculation below applies to any fixed set of positions, not only a threshold set. Summing the indicators of the successes gives , so has mean , and
Dividing by gives the displayed variance, and with gives the bound.
This is sampling without replacement; the retained indicator variables are dependent. The factor records the benefit of not selecting the same occurrence twice. At the answer is exact. At it is also exact, without using the displayed formula. Chebyshev's inequality therefore bounds the probability of a fixed-threshold error greater than by . A fixed-threshold result alone does not justify choosing the threshold after looking at the sample.
Common mistake
(Using the binomial variance for a reservoir)
Treating the retained occurrences as independent draws gives the variance , which omits the factor . The two can differ greatly: at the reservoir holds the whole list and exactly, while the binomial formula still reports a positive variance. The binomial value is an upper bound here, so it is safe for a guarantee but wrong as an exact variance.
One event for every threshold
We can prove a conservative simultaneous bound without assuming independent sample entries or quoting a stronger sketch theorem. Let , put
and use a reservoir of capacity , storing all occurrences if .
Theorem 13.1.3
(A simultaneous finite-list rank guarantee)
For every fixed finite nonempty list, independently sampled as above,
The probability concerns the reservoir construction. The same event protects every real threshold, including a threshold chosen after examining the reservoir.
Proof
(A grid of prefixes and a union bound)
If , every occurrence is retained and the error is zero. Otherwise . Since , we have . Sort the occurrences by value, breaking ties by their original position. For each prefix length define and let be the fraction of reservoir positions among the first in this fixed ordering. Each prefix is a fixed population subset, so the variance bound above applies to it, even if it cuts through tied values.
Set and mark the prefix lengths up to , adding if needed. Because and for , we have and . Thus . There are marks, including both endpoints, and consecutive marks differ by at most .
At each fixed mark, Chebyshev with deviation gives failure probability at most . The union bound, which does not require independent mark errors, makes the probability of any marked-prefix failure at most
On the complementary event, choose any prefix between consecutive marks . Monotonicity of gives
and similarly . Every threshold corresponds to the prefix containing all values at most that threshold. Hence the same event controls all thresholds, including values inside gaps and at ties.
Proof X-ray
Finitely many fixed events, then monotonicity
The proof has three moves. First, it replaces thresholds, which are uncountably many and may be chosen after sampling, by prefixes of a fixed ordering of positions. Ordering ties by position makes every prefix a fixed set, so the one-threshold proposition applies even where a prefix cuts through equal values; every threshold is one of these prefixes, so nothing is lost. Second, only prefixes on a grid are controlled directly, each by Chebyshev at deviation , and the union bound adds their failure probabilities without any independence; this is where must be as large as . Third, monotonicity of and carries the bound from grid points to every prefix between them at the cost of the grid spacing, the other . The case is separate because the reservoir then holds everything; the inequality , which guarantees , is available only because . The bound is deliberately elementary and conservative; it is not a statement about the space complexity or failure law of KLL or Greenwald–Khanna summaries.
Worked example 13.1.4
(The grid for a list of one hundred thousand values)
Let and , so and (computed below), and let . Then , and the marks are : there are of them, and is already a mark. A prefix such as lies between and . If the reservoir fractions at both marks are within of and , then and , both within .
The capacity above is occurrences; it can be larger than the list, in which case storing the entire list is exact. The sampler also needs an exact count requiring bits and storage for its random-state representation. Record values need their own byte budget. This bound is sufficient, not a claim that this many samples are necessary or that it is the sharpest available confidence bound.
Worked example 13.1.5
(Sizing the reservoir, and when to keep everything)
For and , and
For a list of values the reservoir keeps positions, and with probability at least every rank fraction is within . For a list of values, , so the rule stores the entire list and every rank is exact. This edge case is not a failure of the method: the conservative capacity is simply larger than the data.
Turning ranks into quantiles
Take a requested level . Sort the sampled values and return , the value at position . By construction and . The simultaneous event also controls left limits: each is the limit of thresholds below , or equivalently the prefix strictly before the tied group. Consequently
These inequalities say that the population rank interval occupied by comes within of : if lies outside the interval, its nearest endpoint is within . They do not say : when many values equal , the right endpoint can jump far past . The same successful event applies to a level selected after seeing the sample, because it controls every threshold. It does not promise a small value error: two adjacent population values can be arbitrarily far apart.
Worked example 13.1.6
(A tied sample and its population ranks)
Let the fixed population be and suppose a capacity-four reservoir happens to contain . This is one possible uniform subset of positions; equal 3s must come from distinct positions. For , the second sampled value is . Here , , while and . At threshold 6 the estimate is and the true fraction is . This is arithmetic for one realized sample, not a demonstration that four records meet the theorem's confidence requirement.
Counterexample mode
The returned quantile need not have rank close to the requested level
Claim: on the success event, . Let every population value equal 7 and take . Every nonempty reservoir returns , the natural median, even when the full population is stored, so the sampling error is zero. Yet and , which exceeds every . The claim fails because a tied group occupies a whole interval of ranks. The correct statement is the interval form above: contains , consistent with and .
The interval form is about ranks only, and a separate warning concerns values.
Common mistake
(Rank accuracy is not value accuracy)
Take 50 zeros and 50 copies of , with a size-99 sample omitting one zero. The lower population median is 0, but the sample median, the 50th of the 99 sorted values, is . The maximum rank-fraction error is only , while the value error can be arbitrarily large.
Practice with solutions
Quick check
(A list of 100 values has 30 at most . A uniform reservoir contains 10 occurrences. Find the expected estimated fraction and its variance.)
Solution · Answer
The expectation is . The variance is . The observations in the sample are dependent, so the binomial variance without finite-population correction is not exact.
Quick check
(Take and . Compute the sufficient capacity and explain what happens if .)
Solution · Answer
and . Since , retain all 100 positions; every rank is exact. The capacity formula is a sufficient worst-case guarantee and need not be economical for this list.
Quick check
(The population is and the sample is . Give the returned value for and its population rank interval. Does have to hold?)
Solution · Answer
The first sampled value is . Its population rank interval is , which contains . The right endpoint is , not : a tie cannot be split by a value threshold.
Quick check
(A researcher selects a threshold after inspecting the same reservoir. Why is the fixed-threshold Chebyshev estimate alone insufficient, and which result above addresses the selection?)
Solution · Answer
A threshold selected from the random sample is not a fixed event to which the one-threshold calculation can be directly applied. The theorem first constructs one high-probability event that holds for every threshold. On that event the selected threshold is covered too, as long as the original list and final count satisfy the independence assumptions.
This unit covers a conservative reservoir-based simultaneous rank guarantee and a tie-aware quantile interpretation. It does not cover compact deterministic rank summaries, sharper concentration, mergeable quantile sketches or adaptive streams.