Why a small random sample needs a precise contract
A log file may be too large to retain, and its final length may be unknown when the first record arrives. Keeping the first thousand records is inexpensive, but gives later records no opportunity to appear. Independently keeping each record with probability one in a thousand gives every record a chance, but does not enforce a thousand-record memory limit. We want a different contract: after every finite prefix, retain a uniformly chosen subset of a fixed maximum size.
The objects being sampled are record occurrences, identified by their positions or unique immutable identifiers. Two records with the same value are still different occurrences. Sampling without replacement forbids selecting the same occurrence twice; it does not forbid equal displayed values. The sampling law is conditional on a fixed input stream. If the data are themselves random, the law below holds conditional on those data when the sampling randomness is independent of them. An adversary that changes future inputs or decides when to stop after inspecting the reservoir needs a separate analysis.
The method uses only a bounded collection of retained records, exact integer counts and a stated random-source model. The implementation section distinguishes that mathematical model from an executable pseudorandom demonstration.
The reservoir invariant and the one-pass update
Definition 11.1.1
(Uniform reservoir of capacity )
Fix an integer capacity . After reading occurrences, write and . A correct reservoir is a random unordered subset of satisfying
The last clause means that every size- target subset has the same probability. At the only subset is empty. If , every occurrence is retained, so the law is concentrated on . The capacity-zero reservoir is always empty. The stored array order is bookkeeping; the invariant makes no claim that its order is a uniform permutation.
Fill the first array slots. For each subsequent occurrence , draw a fresh uniform integer in . If , replace the item in slot by ; otherwise do nothing. Thus the new occurrence enters with probability , and each particular occupied slot is replaced with probability . Never draw from a fixed range that ignores the current count.
Theorem 11.1.2
(Every finite prefix has a uniform subset)
Suppose each update integer is conditionally uniform given the entire earlier sampling history, and independent of the fixed input. The algorithm produces the stated invariant at every deterministic finite , for every capacity , without knowing the final stream length.
Proof
(Induction on the prefix length)
The cases and are deterministic and already satisfy the invariant. For , use induction from . Suppose and the invariant holds at . Fix a -subset of .
If , the previous reservoir must have been exactly , and the update must make no replacement. Hence
If , put . The previous reservoir must be for some . There are such choices. For each choice, exactly one occupied slot contains , and that slot is selected with conditional probability . The preceding events are disjoint, so
These two cases exhaust all -subsets. Conditional uniformity justifies multiplying the previous-state probability by the relevant update probability, regardless of the array position of . This completes the induction.
Proof X-ray
Where each hypothesis enters the induction
The induction hypothesis is used on whole -subsets of : the case sums over the predecessor reservoirs , and each summand needs the exact value , not merely the survival probability of one record. Conditional uniformity of given the entire history is used twice, to multiply by for no replacement and by for the one slot holding ; the array position of is irrelevant because every slot has the same conditional probability. The step closes because both cases reduce to the identity . If the update integers share randomness, the products are no longer justified even when each is marginally uniform; the shared-draw practice question below computes the resulting bias.
Common mistake
(Equal inclusion probabilities are not the invariant)
It is tempting to verify only that each record is retained with probability . For four records and capacity two, choosing or with probability one half gives every record inclusion probability one half, yet it never produces four of the six possible pairs. The invariant is a statement about every target subset, which is why the proof tracks subsets.
An unbounded incoming stream has a correct reservoir at every fixed finite prefix; there is no final uniform sample from a countably infinite stream. Indeed, a hypothetical fixed-size sample with equal positive inclusion probability for every positive integer would have infinite expected size, while zero inclusion probability for every integer would imply an empty sample almost surely, since a countable union of probability-zero events has probability zero. For , neither describes a size- sample.
The finite-prefix theorem also allows an independent random stopping count: condition on its value and apply the fixed-count result.
Common mistake
(Stopping because the reservoir looks interesting)
A stopping rule that inspects the reservoir is not independent of the sampling randomness. For example, with , stop at count two if record two is retained, otherwise stop at three. Conditional on stopping at two, record two is retained with probability one, rather than one half. The theorem applies at each fixed count, or at a count chosen independently of the sampling decisions.
What a partition summary must retain
Definition 11.1.3
(Partition summary)
A summary of a partition with occurrences, at capacity , is a pair consisting of the exact count and a uniform reservoir of size for that partition.
Suppose two disjoint partitions contain occurrences, and each worker returns a summary built with randomness independent of the other worker. Counts are metadata about the original partitions, not the sizes of their retained arrays. An empty partition has count zero and an empty reservoir.
Let and . A uniform -subset of the union contains a random number of records from . Counting subsets gives the hypergeometric allocation law
To merge, draw with this law using randomness independent of both summaries. Uniformly choose entries without replacement from 's retained array and entries from 's array, with independent fresh decisions. Return their union and count . Every feasible allocation fits in the local reservoirs because and .
Why may a worker discard records before the allocation is known? A uniform subsample of a uniform reservoir remains a uniform sample of the original partition.
Lemma 11.1.4
(Uniform subsampling composes)
Let be a uniform -subset of an -element set, where . Conditional on , choose an -subset uniformly from . Then is a uniform -subset of the original set.
Proof
(Counting reservoirs that contain the target)
For a fixed target -subset , exactly possible reservoirs contain it. Conditional on any of them, selecting has probability . Therefore
by the identity . The factorial identity also holds for and under .
Theorem 11.1.5
(Weighted merging preserves the full subset law)
For fixed disjoint partitions, independent uniform local reservoirs of capacity , and independent allocation/subsampling randomness, the merge above is a uniform -subset of . Its count is .
Proof
(Conditioning on the allocation)
Fix a target -subset and write . The merge can return only when . Conditional on this allocation, the subsampling lemma gives probabilities and for the two target pieces. These events are independent: the original reservoirs are independent and the selection decisions are fresh. Multiplying yields
This includes , and : the unique full or empty subset is handled by the same conventions. Counts add because the partitions are disjoint.
Proof X-ray
One allocation, two lemmas, one cancellation
The single move is to condition on : a target with can only arise from the allocation , so there is no sum over cases. The subsampling lemma is then applied separately to each side, with and , and with and ; this is what justifies discarding records before the allocation is known. Independence of the two workers and of the fresh merge decisions is used exactly once, to multiply the two side probabilities. The proof closes because the hypergeometric numerator cancels both lemma denominators, which is why no other allocation law works. The result averages over the workers' sampling: conditional on one realized summary, discarded records cannot reappear, and two workers reusing a seed break the multiplication even on disjoint partitions.
A merge tree can apply this theorem inductively. Summaries on disjoint subtrees remain independent when their source randomness is independent, so any fixed tree returns the required uniform law. Different trees need not return the same realized sample. Partitions must be disjoint and processed once, as in the earlier distributed-reduction unit; repeated or missing partitions change the population. Checking a summary's length cannot certify those external identity conditions.
Worked example 11.1.6
(An exact five-record merge)
Take , and . The allocation probabilities for are respectively
For the pair , the probability is . The factor includes both the first worker's two-of-three reservoir and its later one-of-two selection. For , the probability is . For , it is . These are the three allocation types; all ten pairs have probability one tenth.
Worked example 11.1.7
(A merge below capacity forces the allocation)
Take , and . Each local reservoir is its whole partition, since and . Here and , so the feasible range is . The only allocation is , with probability . Both subsamples take everything, and the merge returns all three records with count , which is the unique -subset of the union. With instead, the range forces in the same way, and the empty summary contributes nothing.
Counterexample mode
Equal-sized summaries do not imply equal population weights
Let , with one record in and nine distinct records in . Both workers return one record. Choosing uniformly from those two summaries retains with probability , and each particular record with probability . The target probability for every original record is . The correct allocation selects either the summary with probability or the summary with probability . For larger capacities, a hypergeometric allocation is needed; fixing proportional quotas can eliminate allocations that a uniform subset must allow.
A complete implementation using finite random words
Assume an ideal source returns independent uniform -bit words on every call, independent of all input and earlier calls. Here . For any positive integer bound , concatenate enough words, say of them, to obtain a uniform integer in , with . Put , reject , and return otherwise. Every residue has accepted representatives. Repeated independent attempts therefore return each residue with probability . Acceptance probability is , so termination is almost sure with fewer than two attempts on average. There is no fixed bound on the number of attempts.
Fresh source words make successive calls conditionally uniform even when their bounds depend on previous decisions. In particular, a growing stream count never requires replacing exact integer decisions by floating-point probabilities.
For the allocation, imagine an urn containing labels of type and labels of type . Draw labels without replacement using integer decisions, without storing the labels. A sequence with labels of type has probability , where and . There are such type sequences. Multiplication simplifies to the hypergeometric formula above. The program stores only the remaining counts.
The following complete Python program uses a seeded generator as a runnable realization of the word interface. Its deterministic output does not certify the ideal independence assumption. Input occurrences in the demonstration have distinct integer labels; summary validation checks count/length consistency, while the caller must enforce disjointness and fresh randomness.
import random
class FiniteWords:
def __init__(self, seed):
self.rng = random.Random(seed)
def below(self, bound):
if not isinstance(bound, int) or bound < 1:
raise ValueError("positive integer bound required")
if bound == 1:
return 0
words = ((bound - 1).bit_length() + 15) // 16
size = 1 << (16 * words)
limit = size - size % bound
while True:
candidate = 0
for _ in range(words):
candidate = (candidate << 16) | self.rng.getrandbits(16)
if candidate < limit:
return candidate % bound
def reservoir(items, capacity, source):
if not isinstance(capacity, int) or capacity < 0:
raise ValueError("nonnegative integer capacity required")
count, kept = 0, []
for item in items:
count += 1
if len(kept) < capacity:
kept.append(item)
elif capacity:
slot = source.below(count)
if slot < capacity:
kept[slot] = item
return count, kept
def subsample(items, take, source):
if not 0 <= take <= len(items):
raise ValueError("invalid subsample size")
pool = list(items)
for i in range(take):
j = i + source.below(len(pool) - i)
pool[i], pool[j] = pool[j], pool[i]
return pool[:take]
def merge(left, right, capacity, source):
if not isinstance(capacity, int) or capacity < 0:
raise ValueError("nonnegative integer capacity required")
for count, kept in (left, right):
if (not isinstance(count, int) or count < 0
or len(kept) != min(capacity, count)):
raise ValueError("summary count/length mismatch")
na, ra = left
nb, rb = right
total = na + nb
take = min(capacity, total)
remaining_a, remaining_total, allocated_a = na, total, 0
for _ in range(take):
if source.below(remaining_total) < remaining_a:
allocated_a += 1
remaining_a -= 1
remaining_total -= 1
kept = (subsample(ra, allocated_a, source)
+ subsample(rb, take - allocated_a, source))
return total, kept
left = reservoir(iter(range(3)), 2, FiniteWords(101))
right = reservoir(iter(range(3, 5)), 2, FiniteWords(202))
count, sample = merge(left, right, 2, FiniteWords(303))
assert count == 5 and len(sample) == 2 and len(set(sample)) == 2
assert set(sample) <= set(range(5))
assert reservoir(iter(range(2)), 5, FiniteWords(404)) == (2, [0, 1])
assert reservoir(iter(range(5)), 0, FiniteWords(505)) == (5, [])
assert merge((0, []), (0, []), 2, FiniteWords(606)) == (0, [])
print("merged", count, sorted(sample))
The partial swaps in subsample choose each ordered sequence of distinct entries with probability ; forgetting order gives a uniform -subset. The routine copies only a reservoir, never a full partition. The allocation loop runs at most times, and the two subsampling loops together run at most times.
The one-pass routine retains at most records and a count. This is record slots, plus bits for the count and temporary random integer. For arbitrary-length streams, it is not a fixed-bit memory bound: a growing exact count needs growing storage. Every finite prefix uses finite memory, and no input list is built. This accounting also assumes retained records have bounded size or are stored as bounded-size references. Unbounded record payloads require a separate byte budget.
In an idealized model with constant-cost exact integer draws, the scan takes updates and a two-summary merge takes work and auxiliary record slots. With the stated word source, a draw below uses source words in expectation; integer arithmetic and copying large records add costs. Distinct seeds in the demonstration identify reproducible streams; their distinctness is not a proof of mathematical independence.
What the uniform subset buys for estimation
Proposition 11.1.8
(Mean and variance of the reservoir mean)
For fixed real values , with and , put and . If is a uniform -subset of , the reservoir mean is unbiased, with finite-population variance
Proof
(Inclusion indicators and pairwise inclusion)
Write . Counting subsets gives and, for distinct indices, . Linearity proves unbiasedness. Set , so and . Expanding gives
which is the claimed variance.
Pairwise inclusion is where the full sampling design matters. With the variance is zero; with capacity zero there is no sample mean. If , all values are retained, and dividing their sum by the actual sample size gives the exact mean when . For and positive capacity, that mean also has variance zero; the displayed formula using assumes . These are design-based statements about a fixed finite population, not a confidence claim for an unknown future data-generating process.
Worked example 11.1.9
(Checking the finite-population correction)
For values and , the three equally likely pair means are . Their mean is and their variance is . The population quantity is , so . Treating the two retained values as independent draws would miss the reduction from sampling without replacement.
Practice with complete solutions
Quick check
(With capacity two, the reservoir after three records is a uniform pair. What are the probabilities of the pairs and after record four?)
Track the predecessor pairs and the slot replacement probability.
Solution · Answer
The first pair requires the previous pair , probability , and no replacement, probability , giving . For , the previous pair must be or . Each has probability , and replacing the other record's unique slot has probability . The sum is . The reasoning depends on slot replacement probability, not on any sorted array order.
Quick check
(Both workers and the reducer use capacity three, and the two partitions have sizes four and two. Find the allocation probabilities and the probability of the specified subset .)
Start from and .
Solution · Answer
Here . The feasible counts are , with probabilities , and . For the specified subset, allocate two to and one to . Uniform subsampling gives probability . The first worker's capacity-three reservoir is sufficient even though the allocation is decided later.
Quick check
(Capacity is one. Choose one uniform integer from and reuse it to set and . Both update integers are individually uniform on their required ranges. Find the three final selection probabilities. Which theorem hypothesis fails?)
List the six values of and follow both updates.
Solution · Answer
For , the last update selects slot zero and retains record three. For , the second update retained record two and the third makes no replacement. For , neither update replaces record one. The final probabilities are therefore for records one, two and three. The decisions are not conditionally uniform given the earlier history: they share . Correct one-dimensional marginals do not justify the induction products.
Quick check
(Why does knowing that a reservoir has at most one hundred records not prove a fixed-byte memory bound for an arbitrary-length stream? Can the same summary be inserted twice in a merge tree?)
Consider the count and the merge theorem's hypotheses.
Solution · Answer
An exact count of needs order bits, and retained records may have varying byte sizes. The bound is on record slots unless both integer range and record size are separately bounded. Inserting the same summary twice violates disjointness and independence: occurrences have been duplicated, and the two copies share sampling decisions. The merge theorem then does not describe a uniform sample of the intended once-only population.