5
$\begingroup$

I have a simple random sample (SRS) $S$ of size $n$ drawn from a population $D_1$ containing $N_1$ members. A new set $D_2$ with $N_2$ members is added to the population. I would like to create a new set $S'$ that is a SRS from $D_1 \cup D_2$.

One strategy that won't work is to draw a SRS of size $nN_2/N_1$ (or any other size) from $D_2$ and add is to $S$. (The result would be a stratified random sample from $D1 \cup D2$, but not a SRS from it.)

A strategy that will work is to first make one trial on a random variable with a hypergeometric distribution (population size $N_1+N_2$, number of draws $n'$, and number of success states in the population $N_1$). The resulting value $n'_{1}$ is the number of items in $S'$ that should be taken from $D_1$. If $n'_{1} < n$, we discard a SRS of size $n - n'_{1}$ from $S$ to form the initial $S'$. If $n'_{1} > n$, we select an additional SRS of size $n'_{1} - n$ from $D_1 \setminus S$, and put these items, plus all items from $S$ in $S'$. We also draw an SRS of size $n'_{2} = n' - n'_{1}$ from $D_2$ and add it to $S'$.

I'm interested in choosing $n'$ to minimize $E[|S' \setminus S|]$, the expected size of $S' \setminus S$. In other words, the expected value of the number of items from $D_2$ plus the number of new items, if any, from $D_1$.

I have three questions:

Q1. If we have the additional constraint that $n' \ge j$ for some $j$, is there a simple argument that the optimal $n'$ is $j$? Seems like it has to be, but I'd rather not work out the expected value formula and slog through the derivatives.

Q2. Does anyone know of a better algorithm for the above problem?

Q3. The problem I'd really like to solve is more complex. Each item in $D_1$ and $D_2$ is either an A or a B. $S$ has at least $k$ A's, and I want to minimize $E[|S' \setminus S|]$ subject to the constraint that $S'$ has at least $k$ A's. The above algorithm no longer works, because we can't pick $n'$ in advance. (We don't know how rich $D_2$ is in A's, and we might get unlucky anyway.) Is there a simple algorithm for this case? I've perused

Thompson, S. K. and Seber, G. A. G. Adaptive Sampling. Wiley, New York, 1996

but can't find exactly this problem treated. But my gut tells me that both the above problems have been faced and solved many times before.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Clever, and I certainly can't think of a better way of doing this. But for Q1 to make sense we need another constraint; otherwise the smaller $n'$ gets the better it meets your criterion, with $n'=0$ meaning you don't have do any new sampling at all. $\endgroup$
    – Peter Ellis
    Commented Apr 28, 2012 at 3:12
  • $\begingroup$ There are some slight tweeks: for example if $n'_{1} \le n/2$, it may be faster to take an SRS size $n'_{1}$ from $S$ than to discard an SRS size $n-n'_{1}$. $\endgroup$
    – Henry
    Commented Apr 28, 2012 at 7:55
  • $\begingroup$ Peter - Good point about $n'$. I had simplified my actual problem too much. I've edited my question above to give the full problem. $\endgroup$
    – DavidDLewis
    Commented Apr 28, 2012 at 13:38
  • $\begingroup$ Henry - Good point, though I'm actually more interested in a simple algorithm than an efficient one in this case. Fast existing software will do the sampling, but the overall process needs to be comprehensible to non-statisticians. $\endgroup$
    – DavidDLewis
    Commented Apr 28, 2012 at 13:44
  • $\begingroup$ Indeed, from the standpoint of simplicity, minimizing the number of times a person calls the simple random sampling capability of an existing piece of software is probably the main factor. $\endgroup$
    – DavidDLewis
    Commented Apr 28, 2012 at 13:56

1 Answer 1

Reset to default
2
$\begingroup$

You are right, there's been some thought put into how to sample from growing populations by sampling statisticians. I think you would want to look at the work of Larry Ernst of the US Bureau of Labor Statistics: http://www.google.com/search?q=lawrence+ernst+bls+sampling+overlap. As I am still not sure what your statistical problems is -- estimating the fraction or the number of As in the total population? -- I cannot recommend anything specific, but I expect that you will find something suitable from the body of work he develops and cites. Most statistical solutions would involve stratified samples though; these folks are interested in developing statistical solutions in which they can quantify the probabilities of selections of the individual units and the pairs of units. The issue of how the algorithm scales or runs in real time is rarely of interest, as sample is to be taken once, so it's OK if it takes a long time. For you, apparently, timing is an issue.

Improve this answer
$\endgroup$
2
  • $\begingroup$ StasK - Thanks for the pointer. The literature is much larger than I expected! The key terms are ones like "sample overlap", "sample coordination", and "synchronized sampling". As you observe, my problem is much simpler than the ones the literature addresses, so I'm having to dig back to the basics but I'm sure I'll find it. Drawing a sample in order of "permanent random numbers" (essentially hash codes) provides one easy solution, but I'm not sure the software platforms my users have support that capability. $\endgroup$
    – DavidDLewis
    Commented Apr 29, 2012 at 19:22
  • $\begingroup$ Permanent random numbers are available to my users, so I'm going to declare this answered - thanks! $\endgroup$
    – DavidDLewis
    Commented May 1, 2012 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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