1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – conjectures
    Nov 24, 2013 at 14:48
  • $\begingroup$ 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 $\endgroup$
    – amit
    Nov 24, 2013 at 14:56

2 Answers 2

Reset to default
1
$\begingroup$

Random sampling from a large stream (possibly infinite) is actually a well known problem in CS and it is solved by using the Reservoir Sampling algorithm. I think you can easily adapt it to your case.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ To help with googling for related problems; an algorithm that processes a stream as it comes by is called an online algorithm en.wikipedia.org/wiki/Online_algorithm $\endgroup$
    – kasterma
    Dec 25, 2013 at 12:20
0
$\begingroup$

ok... I found a good solution:

Let's m be the target sample size, and let A_i (i=1,2,3,...) be the stream of items (finite, but with unknown size). Here is a sampling rule: you pick the i'th item into your sample with probability m/i (1 if m/i>1). if you chose an element at step i, you put it in your sample, randomly removing an element from it if the sample is already full (that is, if you already chose m items prior to the current item).

proof goes by induction, that for every n>m the probability of item i (1<=i<=n) to be included in the sample is m/n. can't ask for more.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.