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.
[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