RightSignal
1 of 4

Your RightSignal

Concept of the day1 / 3

Reservoir sampling

The concept

How 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.

  1. k = 1, n = 3. Item 3 is kept with probability 1/3.
  2. Item 1: starts kept, survives step 2 with 1/2 and step 3 with 2/3.
  3. 1 × 1/2 × 2/3 = 1/3, the same as item 3.