Reservoir sampling
The conceptHow do you pick 100 fair random lines from a log of unknown length?
Reservoir sampling picks k random items from a stream in one pass, without knowing how long the stream is and without storing it all. Every item ends up equally likely to be chosen.
Keep the first k items in a 'reservoir'. When item number i arrives (for i greater than k), keep it with probability k/i. If you keep it, it replaces one reservoir slot chosen at random.
For a log of a million lines and k = 100, line 200 gets in with probability 100/200, and line 1,000,000 with probability 100/1,000,000. Early lines get in easily but are likely to be pushed out later, and the two effects cancel exactly.
What it’s forShows that an item seen at position i is still in the sample when the stream ends.
P(kept) = (k/i) · Π_{j=i+1..n} (j−1)/j = k/n
- k
- reservoir size, how many items you want, e.g. 100
- i
- position of the item in the stream
- n
- total items in the stream, unknown until it ends
- (j−1)/j
- chance the item survives step j: 1 − (k/j)·(1/k)
What it givesEvery item ends with the same chance, k/n, whatever its position.
- k = 1, n = 3. Item 3 is kept with probability 1/3.
- Item 1: starts kept, survives step 2 with 1/2 and step 3 with 2/3.
- 1 × 1/2 × 2/3 = 1/3, the same as item 3.