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 alok-g on Saturday March 07, 2015 @11:25AM (#9162158)
Can you show that this will still maintain a uniform probability distribution?
[ Parent | on HN ]
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by shoegumfoot on Sunday March 08, 2015 @02:52PM (#9166654)
> Can you show that [generating a number of records to skip instead of a yes/no for each record] will still maintain a uniform probability distribution?

That should work if you pull the skip count from the appropriate distribution (negative binomial, I think).

[ Parent | on HN ]
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by eru on Monday March 09, 2015 @08:28PM (#9175110)
Yes, you have to work out the right distribution, and how to sample from it (at all, and perhaps how to sample from it efficiently).
[ Parent | on HN ]
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by eru on Sunday March 08, 2015 @12:25AM (#9164677)
Yes.
[ Parent | on HN ]