Vitter's reservoir sampling algorithm D: randomly selecting unique items

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by ridiculous_fish on Monday April 04, 2016 @04:22AM (#11420219)

This is very practical, but the result is not uniform; in fact it only returns a tiny fraction of the possible combinations.

There are "N choose k" combinations, which in the worst case (k = N/2) grows as ~ 2^N. The number of combinations quickly outstrips the number of possible states of the LCG, and most combinations will never be found. For example, we have a list of length 16 and wish to choose 8. We have a choice of 16 distinct seeds, so there are only 16 different combinations (out of 12870 possible) that we can get for any given LCG.

[ Parent | on HN ]

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by mrdrozdov on Tuesday April 12, 2016 @09:49AM (#11479522)

By randomly adding skips, can definitely get to all possible combinations even with only 16 seeds (since skips can be seeded from a much larger space), although there could be a speed implication.

[ Parent | on HN ]

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by vrfcodf on Monday April 04, 2016 @06:40AM (#11420761)

Good point. You would get different sequences by choosing different constants for the generator though, but you couldn't cover all of them by a longshot.

[ Parent | on HN ]

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by mcherm on Monday April 04, 2016 @08:38AM (#11421372)

And this inability to cover all possible sequences has real-world implications.

https://www.cigital.com/papers/download/developer_gambling.p...

http://superuser.com/questions/712551/how-are-pseudorandom-a...

[ Parent | on HN ]