3 ms·
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 reach
by joe_the_user 13y ago
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?
- dbaupp 13y agoI'm not sure how your solution gives a uniformly distributed sample?
- archgoon 13y agoSo 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.
- deleted 13y ago[deleted]
- salmonellaeater 13y agoIt'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_biased_coin http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_b... [3] http://en.wikipedia.org/wiki/Arithmetic_coding http://en.wikipedia.org/wiki/Arithmetic_coding
- joe_the_user 13y agoJust 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.
- brendano 13y agoOnce 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...
- deleted 13y ago[deleted]
- dbaupp 13y agoMost 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.)