Sampling from a Stream
Selecting a random element from an array of length n
is easy: simply
generate a random integer i
, with 0 <= i < n
, and use the array
element at that index position. But what if the length of the array is
not known beforehand, or is, in fact, infinite (i.e. a stream)? And what
if we don’t just want a single element, but a set of m
samples,
without replacement?