Reservoir sampling: Definition & Examples

Reservoir sampling maintains a uniform sample of a fixed capacity from a stream whose final length need not be known. After enough records have arrived to fill it, every subset of that size from all records seen so far has the same probability. A quant can retain a manageable collection of trade messages for later inspection without first storing the entire feed or counting its final length.

The target is the observed prefix of the stream. A reservoir containing old trades can be working exactly as intended even when the market has moved to a new regime.

Give later arrivals a smaller admission chance

The standard Algorithm R, described in Vitter’s 1985 paper, §2, uses a reservoir of capacity

k\ge1

Store the first $k$ records in slots numbered $1,\ldots,k$ . If the stream ends sooner, retain everything received.
When record $t>k$ arrives, draw a fresh integer $J_t$ uniformly from $1,\ldots,t$ .
If $J_t\le k$ , replace the record in slot $J_t$ with the arrival. Otherwise leave the reservoir unchanged.

The new record enters with probability

k/t

. Conditional on admission, each slot is equally likely to be replaced. Many arrivals must be rejected. Replacing a random stored record on every arrival is a different rule and gives the latest record probability one of appearing in the sample.

Algorithm R processes $N$ arrivals in $O(N)$ time and stores $O(k)$ records, plus a counter and generator state. “Constant memory” here means independent of stream length when $k$ and record size are fixed; retaining large messages still costs space.

Two places, four records, twelve paths

Consider the synthetic stream A, B, C, D and capacity $k=2$ . Begin with A in slot 1 and B in slot 2. At C, draw $J_3$ from three choices; at D, draw $J_4$ from four. Independent uniform draws give $3\times4=12$ equally likely choice paths.

Exact enumeration for synthetic stream A, B, C, D with reservoir capacity two. The three choices at C and four at D give twelve equally likely cells. Each unordered pair AB, AC, AD, BC, BD and CD appears twice, so each has probability one sixth. Each record appears six times, so its inclusion probability is one half.

An original exhaustive enumeration, not a simulation. Reservoir slots retain their order during updates; final samples are compared as unordered pairs.

For example, $J_3=1$ replaces A with C, leaving slots C, B. If $J_4=2$ , D then replaces B, leaving the unordered sample CD. If $J_4=3$ or $4$ , D is rejected and the final sample is BC.

Every unordered pair occurs in two cells, so its probability is

2/12=1/6

. Each record appears in six cells, giving inclusion probability

6/12=1/2

. This checks simple random sampling without replacement, whose defining condition concerns entire subsets. Equal individual inclusion probabilities alone would not establish it.

Early records do not receive a permanent advantage

At a fixed prefix length $t\ge k$ , Algorithm R satisfies

\mathbb{P}(\mathcal S_t=s)=\frac{1}{\binom tk},\qquad |s|=k,

where

s

is a set of distinct stream positions. The University of Illinois notes prove this invariant by induction over arrivals.

An individual-record check makes the mechanism intuitive. Before arrival $t$ , an old record is present with probability $k/(t-1)$ . If present, its particular slot is replaced with probability $1/t$ . Its new inclusion probability is therefore

\frac{k}{t-1}\left(1-\frac1t\right)=\frac kt,

matching the arrival’s admission probability. In our example, A survives C with probability $2/3$ and then D with conditional probability $3/4$ : their product is $1/2$ .

These probabilities concern positions, or record identities. Two trades with identical prices remain separate records. Repeated delivery of one trade counts twice unless the input is deduplicated first. The stream need not arrive in random order: the selection randomness comes from the algorithm. The guarantee here is for a fixed stream prefix, using random draws independent of its contents.

A small Python implementation

The loop follows the arrivals because the update rule is sequential. In NumPy, the upper bound of Generator.integers is exclusive, so t + 1 includes the integer t.

import numpy as np

rng = np.random.default_rng(20261029)
k = 2
reservoir = []
for t, record in enumerate("ABCD", start=1):
    if t <= k:
        reservoir.append(record)
    else:
        j = int(rng.integers(1, t + 1))
        if j <= k:
            reservoir[j - 1] = record
print(reservoir)
# ['C', 'D']

This is one realised sample, not evidence of uniformity. The twelve-path enumeration checks the distribution. For reproducibility beyond this example, preserve the record order, capacity, random-generator implementation and state as well as the seed.

Match the reservoir to the research question

A reservoir of trade records can support manual data-quality review or approximate summaries when retaining every record is expensive. At a fixed prefix, its unweighted sample mean is an unbiased estimator of the mean per observed record. A per-record mean does not become a volume-weighted execution measure merely because the records are trades.

Capacity controls storage, not a universal error tolerance. A small sample may omit rare rejected orders or extreme losses entirely. If the sole task is an exact running mean or count, an accumulator can compute that summary without retaining sampled rows; a reservoir is useful when the records themselves or later, unanticipated queries matter.

A standard reservoir also makes no promise of recent observations, coverage of every venue, or larger chances for larger trades. A rolling window changes the eligible population to recent records; weighted sampling changes selection probabilities; stratified sampling imposes a group-based design. Each answers a different question and needs matching estimation rules.

Finally, uniform sampling cannot repair gaps in the sampling frame. A feed that omits a venue remains incomplete, and randomly selecting historical trades does not establish independence, remove regime change or validate a forecast. If a sample is inspected repeatedly and the analyst stops when it looks unusual, the fixed-prefix guarantee alone does not justify that stopping rule’s statistical conclusions.

Basic Statistics and Regression introduces sample summaries and standard errors (public preview; full lesson free with a signed-in account). Its independent-sample standard-error baseline must be distinguished from uncertainty under finite-population sampling.

Sources

Jeffrey S. Vitter (1985), Random Sampling with a Reservoir, ACM Transactions on Mathematical Software 11(1), 37–57, §2: reservoir invariant, Algorithm R and linear running time. Vitter credits Algorithm R to Alan Waterman; the paper also develops faster reservoir methods.
Sariel Har-Peled, University of Illinois, Streaming and the Multipass Model, “Reservoir sampling: two constructions” and “Reservoir sampling: uniformity of the whole set”: replacement rule, induction and occurrence-based sampling.
NumPy, Generator.integers: discrete uniform draws and exclusive upper-bound convention; documentation checked 29 October 2026.

Give later arrivals a smaller admission chance

Two places, four records, twelve paths

Early records do not receive a permanent advantage

A small Python implementation

Match the reservoir to the research question

Sources

Related terms

Independence

Sampling frame

Simple random sampling

Stratified sampling

Unbiased estimator