I'm not a ruby guy at all (never used it), but if I understand this correctly: j = rand(idx) out[j] = i if j < n ..it is keeping the sampling probability

I'm not a ruby guy at all (never used it), but if I understand this correctly: j = rand(idx) out[j] = i if j < n ..it is keeping the sampling probability at n/idx where n is the sample/reservoir size and idx is the number of items seen so far. Then if this item is selected for sampling, each of the n items in the reservoir is equally likely to be replaced. I think the implementation is correct, assuming that idx is the number of items seen so far.