I need to create a sample of a given size from a population. However, the population is dynamic, that is, comes as a stream of items, and every item has a "time stamp" based on its location in this stream. I don't know beforehand how long is this stream, but I need that in the chosen sample, the time stamps will look as a random sequence.
Practically, I can't "save" the whole population, and then choose a sample. I must somehow retain a sample throughout the process, and end up with the required sample of the gien size.
Here is an idea I had: Suppose you need to sample m items, and the unknown population size total is n. - choose a number k which is greater than m and smaller than n, and for which you can handle populations of size k - for the first k elements in the stream, create a random sample of m elements from it and retain it as the "working sample" - for the next k (that is the second chunk of k items), sample about m/2 elements from it, and replace randomly chosen m/2 elements from your working sample, wit the new sampled items. now you have an m sample from 2k items - so on and so forth... for the i'th chunk of k items from the stream, choose about m/i elements randomly and substitute them randomly into your working sample... - do it until the stream is over. your working sample is the result
does this algorithm create a good sample? are there better ways to do it?