News for hackers. Stuff that matters.

A comment on Algorithms Every Programmer Should Know: Reservoir Sampling. Parent comment

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by javajosh on Friday March 06, 2015 @02:18PM (#9158931)
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.
[ Parent | on HN ]
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by loqi on Friday March 06, 2015 @05:50PM (#9160096)
Intuitively, 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.
[ Parent | on HN ]
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by c0ldfusion on Friday March 06, 2015 @02:31PM (#9159019)
proof is in the article http://en.wikipedia.org/wiki/Reservoir_sampling
[ Parent | on HN ]