# How to efficiently expand a simple random sample after population growth?

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.

• 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. – Peter Ellis Apr 28 '12 at 3:12
• 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}$. – Henry Apr 28 '12 at 7:55
• Peter - Good point about $n'$. I had simplified my actual problem too much. I've edited my question above to give the full problem. – DavidDLewis Apr 28 '12 at 13:38
• 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. – DavidDLewis Apr 28 '12 at 13:44
• 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. – DavidDLewis Apr 28 '12 at 13:56