3 ms·
Then I'm a little bit worried about this algorithm, because if the probability of picking is n/idx then the odds of picking a long tail item get asymptotically
by javajosh 12y ago
Then I'm a little bit worried about this algorithm, because if the probability of picking is n/idx then the odds of picking a long tail item get asymptotically close to 0. I'm not sure if it really qualifies as a sample of the entire thing.
- c0ldfusion 12y agoproof is in the article http://en.wikipedia.org/wiki/Reservoir_sampling http://en.wikipedia.org/wiki/Reservoir_sampling
- loqi 12y agoIntuitively, the reason why it balances out is that while earlier items are more likely to be picked, they're also more likely to get kicked out after being picked.