News for hackers. Stuff that matters.
Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by joe_the_user on Monday July 01, 2013 @10:14PM (#5975344)
Hmm,

Given the article's windup, I'd be a bit skeptical of the naive solution - at input n, with probability 1/n replace the current choice.

Once you've reached input number 10^8 or whatever, you've got all sorts of chances to have arithmetic overflow and/or the weirdness of that many pseudo-random operations screw you.

I'd rather keep a list of x's; let x1 be randomly chosen from the last 10, x2 randomly chosen from the last 100, x3 random chosen from the last 1000, etc and when termination time come do a little fixup. That'd take O(log(n)) memory instead of O(1) but if this matters, shouldn't you want some sample of what's happening?

Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by salmonellaeater on Monday July 01, 2013 @11:33PM (#5975658)
It's easy to do the right thing using arbitrary-precision arithmetic and a random-bit generator. Basically, generate bits after the decimal point until the possible range for the final random number does not include 1/n. The number of bits you have to generate doesn't depend on n: the expected number is 2 bits[1]. If your random bits are biased, that's easy to correct too[2].

[1] You always need at least one bit. After the first, each additional bit divides the space in which 1/n can lie in half, so it's just 1 + (1/2 + 1/2(1/2 + 1/2(...))) = 1+1/2+1/4+... = 2. It's a lot like arithmetic coding[3]

[2] http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_b...

[3] http://en.wikipedia.org/wiki/Arithmetic_coding

Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by joe_the_user on Tuesday July 02, 2013 @12:39AM (#5975863)
Just FYI, what Wikipedia is talking about is biased but still random distribution that thus wouldn't have the possible problem of correlation between successive "tosses".

Not that I have any knowledge any given pseudo-random number generator would trouble with long series's of zeros. Still, scheme I had in my parent post was aiming to avoid potential problems with that kind of thing.

Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by brendano on Tuesday July 02, 2013 @12:04AM (#5975757)
Once you've reached input number 10^8 or whatever, you've got all sorts of chances to have arithmetic overflow and/or the weirdness of that many pseudo-random operations screw you.

Why? Double floats don't overflow until 10^-300 or so, and RNG's give uniform numbers from 0 to 1 just fine...

Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by dbaupp on Tuesday July 02, 2013 @07:35AM (#5977077)
Most RNGs that generate numbers from 0 to 1 actually just generate a random 64-bit value, and divide by 2^64; which means that they do underflow relatively easily. (This is relatively easily to overcome using a better (& more expensive) random bits -> double algorithm.)
Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by dbaupp on Monday July 01, 2013 @10:58PM (#5975540)
I'm not sure how your solution gives a uniformly distributed sample?
Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by archgoon on Tuesday July 02, 2013 @02:59AM (#5976247)
So you take the first item in the stream. Then you take the second. Flip a coin. Pick the winner, discard the loser. Promote the winner to level 2. Take in the next 2. Promote hte winner to level 2, discard the loser. Pick a winner from the two level twos, discard the loser. Promote the winner to level three. The winner at the top level k will always be picked with probability 1/2^k. If there were 2^k elements, this is exactly the probability it should have; and by the symmetry of selection at each level, it's uniform.

There's some complications if the sample is not a power of two (or whatever number of elements you picked for each level). Essentially though, you know the number of elements at that point though, and you can weight the probability of selection so that the winner has exactly 1/N probability of having been selected.

Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by dbaupp on Tuesday July 02, 2013 @09:23AM (#5977571)
Right, that works; but it seems different from "Pick one from first 10, pick one from next 100, pick one from next 1000".
Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by stouset on Tuesday July 02, 2013 @05:12PM (#5980773)
Fundamentally it's the same.