Consider the problem of taking a weighted sample of size $K$ from a stream of unknown but finite size $N$ in a single pass.

Reservoir sampling solves this by assigning each item from the stream with a key $R^{1/w}$, where $R$ is a random number in 0..1 and $w$ is the item's weight, and maintaining the set of $K$ items with the largest key.

When a new item arrives, we compute its key and insert it into the set. Let us say that the item is skipped (never enters the set) if its computed key is smaller than the smallest key in the set, otherwise let us say that the item is competitive (it replaces some previous item in the set). Some implementations of reservoir sampling may use this as an optimization to avoid fully populating the sample datum in case it is not competitive.

I'm curious, what is the expected number of competitive items (i.e. number of replacements), relative to $N$ (stream size) and $K$ (sample size)? I was not able to find the answer to this question in any of the descriptions of reservoir sampling I found on the internet.

| cite | improve this question | | | | |

Good question; I see that you are planning an implementation, and are concerned about the storage requirements. I suspect there is no flat $O(N^\alpha K^\beta)$ answer possible, as it would depend on the distribution of weights. If all weights are the same, approximately all items are competitive. If there are $K$ large weights (say 100) and $N-K$ small weights (say 1), then whenever a high-weight item enters the pool, its key is nearly always competitive, overshadowing a small-weight item. Thus the first $~\sim N/K$ items would be small, and keep fighting each other; but as soon as large items begin entering the sample, the competition for the lowest key whittles down. So my conjecture is, the number of competitive items can be anywhere from $N/K$ to $N$.

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.