When records have unequal importance
A uniform reservoir gives every occurrence the same chance. Sometimes an occurrence has a known positive weight: for example, one record may represent three times as much traffic as another. We would like larger weights to make selection more likely, while keeping a fixed-size sample and allowing disjoint workers to combine their results. There is more than one reasonable definition of a weighted sample without replacement. We will define a particular one precisely and derive its consequences, rather than assume that every inclusion probability is simply proportional to its weight.
Definition 18.1.1
(Exponential-race sample of capacity )
Fix a finite stream of distinct occurrences and deterministic weights . Repeated values are distinct occurrences. Let be an integer and . Independently draw an exponential clock of rate , meaning
The sample consists of the occurrences with the smallest clocks, listed in increasing order of clock as .
With ideal continuous draws there are no ties almost surely. This is a mathematical model conditional on the input and weights, with randomness independent of them; if future records or the stopping time depend on visible random choices, the fixed-stream statement need not hold. Zero-weight occurrences are excluded from this construction; negative weights are invalid.
The ordered sample law
Theorem 18.1.2
(The exponential race selects proportionally among those remaining)
For a fixed finite stream with positive weights, the ordered indices of the smallest independent clocks satisfy, for distinct ,
The empty product is one when . Thus the next occurrence is chosen in proportion to its weight among those not yet chosen.
Proof
(First arrival, then memorylessness)
Write . The first clock is exactly when and all others exceed . Integrating their independent densities and survival probabilities gives
For the remaining clocks, the exponential memoryless identity says . Independence means that, conditional on and the first arrival time , the residual clocks of the other occurrences are independent exponentials with their original rates. The same integration therefore chooses the next index in proportion to its remaining weight. Repeating this argument proves the product formula. Conditioning on an exact continuous time here is shorthand for the corresponding conditional density; the result is independent of .
Proof X-ray
Why the race restarts after every arrival
The proof uses one computation and one structural fact. The computation is the first-arrival integral: the minimum of independent exponentials is exponential with rate , and the winner is with probability . The structural fact is that, at the first arrival time, the clocks still running are again independent exponentials with their original rates. Both independence and memorylessness are needed here: memorylessness removes the elapsed time , and independence ensures that learning which clock rang first and when tells nothing more about the others. The induction therefore restarts on the smaller set of occurrences with the same rule, which is why each factor's denominator is the weight that remains. With clocks that are not exponential, for example uniform on , the proportional rule fails at once: for weights and , the second clock rings first with probability , not .
The theorem describes ordered samples. Any question about which occurrences appear, regardless of order, requires adding over orders.
Common mistake
(Ordered probabilities are not set probabilities)
The probability of an unordered set is the sum over all orders yielding that set. The theorem does not say that a size- set has probability proportional to the product of its weights, nor that inclusion probabilities are . For the distinction vanishes; for it usually does not, as the next examples show.
Worked example 18.1.3
(Three weighted occurrences)
Take weights and capacity two. The chance that occurrence 1 appears is the sum of the disjoint possibilities that it is first, or that it is second after 2 or 3:
By contrast, , so multiplying the single-draw probability by the capacity gives the wrong inclusion probability. The unordered set has probability . Equal weights do recover a uniform -subset: every ordered list has probability , and every subset has orders.
Worked example 18.1.4
(All inclusion probabilities for capacity two)
Keep weights and . The first example gave . For occurrence 2, add the case where it is first and the two cases where it is second:
Similarly . As a check, , the sample size. The naive values are , and : heavy occurrences are not certain to be chosen. In the edge case of weights with , the naive value for the heavy occurrence is , which cannot be a probability; the race gives .
One pass and exact merging
For each arriving occurrence, generate its clock once. A max-heap of at most pairs stores the smallest clocks seen so far: insert until full, then replace the heap maximum only when the new clock is smaller. For store nothing. A heap update costs when , and stored samples use entries; weights, identifiers and clock representations contribute to the actual byte cost. This is an ideal real-arithmetic statement, not a finite-precision random-number guarantee.
The invariant follows by induction: after each record the heap contains the smallest clocks of the prefix. If a new clock is not below the current maximum, the retained set is unchanged; otherwise exactly the former maximum must leave. In particular no discarded clock can later re-enter under insertion-only processing: at least earlier clocks already beat it.
Worked example 18.1.5
(Tracing the heap with capacity two)
Let and let the clocks arrive in the order . The first two fill the heap: with maximum . The clock is below , so leaves: . The clock is not below the maximum , so nothing changes; this is the boundary case in which a new record is generated, compared once and discarded. Finally replaces , leaving , which are indeed the two smallest of the five clocks. The discarded , and each had two smaller clocks before them by the time they left or were rejected.
Theorem 18.1.6
(Local top- priorities merge exactly)
Partition a fixed collection of occurrences into disjoint sets. Give every occurrence one independent clock of its stated rate and let each worker return its smallest clock–record pairs. Taking the smallest pairs from the union of worker outputs gives exactly the same sample as taking the global smallest clocks directly, for every realization without ties.
Proof
(Local losers cannot be global winners)
A record discarded by its worker has at least records in that same partition with smaller clocks. It therefore cannot belong to the global smallest . Every global winner is in the union of local outputs, and sorting that union recovers precisely the global winners. This argument is pathwise; the random law then follows from the ordered-sample theorem. Empty partitions and cause no difficulty.
The pathwise proof needs the same clocks to be compared locally and globally; the next example shows what happens when that is not respected.
Counterexample mode
A merge must preserve the original priorities
Suppose and worker A has two records, each of weight one, while worker B has one record of weight one. With original clocks the global winner is uniform over the three occurrences, so worker A wins with probability . If a coordinator discards the local clock values and chooses uniformly between the two workers' retained records, A wins with probability . Redrawing clocks for local winners also changes the law. Retain original priorities, disjoint occurrence identities and a consistent tie rule for actual finite-precision representations.
A priority can be generated as from an ideal independent uniform on . Real pseudorandom generators have finite states, endpoints and numerical rounding; underflow, duplicate priorities, reproducibility, seed independence and overflow require an implementation-specific policy. A deterministic identifier tie-break makes a concrete implementation reproducible but does not restore the ideal continuous law exactly. The merge proof remains pathwise for any common total ordering of pairs, even when the distribution of that ordering differs from the exponential model. Do not regenerate a priority on retry: deduplicate the same occurrence and reuse its original priority, or it can receive extra chances.
Concept lensAlgorithmic
Smallest clocks as largest power keys
Since is strictly decreasing, the smallest clocks are the largest values of . With these values are the keys , with for . The same sample is therefore the largest keys , kept by the same heap with the comparison reversed. The two forms agree exactly in real arithmetic. In floating point, a large weight pushes toward , and comparing keeps resolution that the power form loses.
Estimation requires inclusion probabilities
Sampling proportionally is not itself an estimate of a population total. Let be a fixed value and let . If these probabilities are known, the Horvitz–Thompson total estimator
is unbiased: write it as and take expectations term by term. Independence of inclusion indicators is not needed for this expectation, but variance generally requires their joint probabilities. When , and a selected value contributes . For , calculating the inclusion probabilities can require summing many ordered-sample probabilities; using is generally wrong and can even exceed one. If and the stream is nonempty, no such positive inclusion probabilities exist. The sample alone does not determine an unbiased total estimator unless the needed weights and inclusion information are available.
Practice with solutions
Quick check
(Weights and : find each selection probability.)
Solution · Answer
The first-clock law gives and .
Quick check
(For weights and , find the probability of the unordered set .)
Solution · Answer
The two orders give . Together with at and at , the three sets have total probability .
Quick check
(A worker with capacity two has clocks ; a second has . What should be sent and merged?)
Solution · Answer
The first sends , the second sends ; the merged winners have clocks . The discarded has two local predecessors and cannot be a global winner.
Quick check
(For one draw with weights and values , calculate the two possible unbiased total estimates and their expectation.)
Solution · Answer
Inclusion probabilities are and ; the estimates are and . Their expectation is , the true total .
Quick check
(Does a larger weight guarantee inclusion when ?)
Solution · Answer
No. With finite positive weights, every ordered list of distinct occurrences has positive probability, including lists omitting any specified occurrence. Weight changes probability, not certainty.
This construction covers fixed positive weights and insertion-only finite streams. Unequal-probability deletion, changing weights, adaptive inputs, finite-bit distributional error, efficient inclusion-probability calculation and failure-tolerant distributed implementations need separate analysis.