A trade feed of unknown length streams past once and you must hold a uniform random sample of exactly k trades in O(k) memory. Give the algorithm and prove by induction that every trade seen so far has probability exactly k/n of being in the sample.

A trade feed of unknown length streams past once and you must hold a uniform random sample of exactly k trades in O(k) memory. Give the algorithm and prove by induction that every trade seen so far has probability exactly k/n of being in the sample.

Approach: Fill the reservoir with the first k items, then accept item n with a decreasing probability and evict a uniformly chosen incumbent. Do the induction step on one extra arrival.

Keep the first k trades, then for the n-th trade with n > k accept it with probability k/n and, on acceptance, evict a uniformly chosen one of the k incumbents. Reservoir sampling gives every trade probability exactly k/n of being held, by induction on n. The base case n = k is immediate since all k are kept with probability 1. Assume each of the first n trades is held with probability k/n. On arrival n + 1 the new trade is accepted with probability k/(n+1), which is the claim for it. An old trade survives when the new one is rejected, probability 1 - k/(n+1), or when the new one is accepted and some other incumbent is evicted, probability (k/(n+1)) * (k-1)/k. Its survival probability is therefore (k/n) * [1 - k/(n+1) + (k-1)/(n+1)] = (k/n) * (n/(n+1)) = k/(n+1). Memory is O(k), each arrival costs O(1), and the sample is available at any point without knowing the stream length in advance.

Follow-up: How do you take a weighted reservoir sample where each trade should be selected in proportion to its size?

Key concepts: reservoir sampling, induction, uniform sample, eviction probability.