# Sampling from a dynamic population

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?

• What is it you're interested in? The distribution of arrivals across a period (e.g. customers into a shop over a day)? Or some attribute from each item? Are the two independent in your case? Nov 24, 2013 at 14:48
• Each items has lots of features, and I'm interested in analyzing some of these features to make inferences on the items in general. your "customers coming into a shop over time" is a good metaphor. so I want to learn about those customers. However, there might be differences between morning and evening customers, so I want my sample to have both, so my inferences can say whether my analyses (dependent variables) are time dependent or not. However, unlike "customers coming into a shop", I don't know the start and end periods, so I need a way to sample the whole population without knowing it
– amit
Nov 24, 2013 at 14:56