Drawing a random sample without replacement from data set

Question

I have data generated by a RCT with a control and treatment group, each with n=300, so N=600. The observations are assumed to be i.i.d..

From that population, I'd like to draw 5 random observations without replacement (5 by group, so 10 in total). If I repeat and simulate this process say 1,000 times, are these 1,000 samples correlated with each other? Does this turn inference invalid, or say, biased?

My intuition tells me that there could me correlation among the 1,000 samples. The severeness of the issue most likely depends on the size of the randomly drawn sample. E.g., if I drew 200 random observations without replacement for each group instead of 5, and repeated this procedure 1,000 times, the observations ending up in the 1,000 simulated samples will be, clearly, very often the same one's. The 1,000 drawn samples will therefore correlate.

Thus, is there a rule of thumb about how large the number of repetitions should be in relation to the randomly drawn subsample out of the original population?

Edit:

To respond to EdM: I simplified the problem a bit, but I think (and hope) it doesn't change much to my underlying concern about correlated "repetition samples". Here's why: The relevant question is: Within each treatment group, how many observations would I need to draw until I find 2 observations with the very same characteristic? (In real, the characteristics of an observation become only "apparent" once the observation is "drawn" so ex-ante the characteristics of the not yet drawn population is unknown. The drawing process - draw until 2 observations match - I want to mimic here is exactly the one happening in nature.) The average number of needed draws is roughly 5 observations. So I have on average 5 observations per treatment group entering each randomly drawn sample in each repetition. Yet, some characteristics are rarer, and there I end up with drawing on average 90 observations by treatment group to find 2 observations that match. Neglecting for now treatment differences.

Edit 2:

To respond to EdM's answer: I am not sure this distribution applies in my setting. To me, it seems that in the Negative hypergeometric distribution it is in advance defined what is a "fail" or "success". So in advance, we define what a "match" or "failure" should be for a particular characteristic, e.g. Male/Female.

The process I want to mimic works differently in nature. It starts to draw an observation. It continues to draw observations until 2 observations exhibit the same characteristic, but this characteristic is not pre-defined in advance. The only thing that matters is that in the pool of drawn observations, 2 observations exhibit the very same characteristic. The exact peculiarity of the characteristic does not matter. Example: Let's assume we want to match on variable 1 (a certain dimension of possible characteristics):

• Draw 1 : AABC
• Draw 2: AACB
• Draw 3: CBAA
• Draw 4: CBAB
• Draw 5: AACB
• Stop. Draw 5 and draw 2 is a "failure".

Number of draws: 5. Thus, 2 observations within the pool of already drawn observations need to "match" or "fail", but the underlying value on what they are matched does not matter. E.g., Draw 5 could have been CBAB, too.

(Regarding the bootstrap, in this case, bootstrapping isn't very appropriate imho since in nature, the process does not work "with replacement".)

Edit 3:

Yes, it is kind of a verification mechanism. Let me try to illustrate with a hopefully easy-to-understand “human” analogue: Assume Google has some new CAPTCHA’s to verify, where google does not know the solution yet. Google assumes users response to be true once 2 users agree. Users solve these CAPTCHA’s sequentially. User 1 arrives first, solves CAPTCHA number 1 and provides solution ABCDEF. User 2 arrives, provides for the same CAPTCHA another solution, say FABCDE. No match. Continue, until another user provides ABCDEF, too, (or, another user agree's e.g. with user's 2 response, it doesnt matter on what response they agree) and then assume the response ABCDEF to be “verified”. With our RCT, we implemented a treatment that modifies the environment in such a way that the observations get more similar, so the speed of verification is increased. With the RCT, we assess the causal effect. But we also want to quantify what it would mean if we implement the treatment in real, and therefore, we want to mimic and simulate 1:1 the real process.

Answer 1

The relevant question is: Within each treatment group, how many observations would I need to draw until I find 2 observations with the very same characteristic?

To avoid potential confusion, I'd prefer to use the word "characteristic" to represent a set of distinct values from which each individual has exactly one value (like the set of colors of a group of single-colored balls, or the set of possible birthdays) and ask about a match of the value of the characteristic between 2 cases (e.g., 2 balls having the same color, 2 people having the same birthday).

For one particular value of the characteristic to match

This can be considered in the context of the negative hypergeometric distribution, when "sampling from a finite population without replacement in which each sample can be classified into two mutually exclusive categories." The distribution is described on that linked Wikipedia page as representing the number $k$ of "successes" until a specified number $r$ of "failures" is found.

For the negative hypergeometric distribution, the mean number of "successes" $\bar k$ until $r$ "failures" depends on the total population size $N$ and the number of "success" cases, $K$, in the population:

$$ \bar k = r \frac{K}{N-K-1}$$

To keep in line with that description, in your situation consider your requirement for finding 2 cases with a particular value of the characteristic as being $r=2$ "failures." Your finite population size is $N=300$ for each group.

If you draw on the average 7 times to get 2 cases with that value of the characteristic ("failures"), then you have on average 5 "successes" without that value. The above formula indicates K=215 for the total number without that value and thus 85 with it. If you need to draw 90 times to get 2 "failures" then $K$ is about 294, or only about 6 cases with that value of the characteristic.

For any value of the characteristic to match

This is related to the birthday problem. That's the classic question about how small a group can be such that there's a 50% chance of 2 individuals sharing a birthday: 23, for 365 possible birthdays evenly distributed. The generalized birthday problem extends that to any set of $d$ values of a characteristic evenly distributed in the population. The minimum sample size needed to have a 50% chance of some match between 2 individuals, $n(d)$, up to $d=99$ values of a characteristic, is:*

$d$	1–2	3–5	6-9	10–16	17–23	24–32	33–42	43–54	55–68	69–82	83–99
$n(d)$	2	3	4	5	6	7	8	9	10	11	12

In your example, your "characteristic" is an ordered set of 4 symbols chosen with replacement from the set $\{A,B,C\}$, for a total of $3^4=81$ distinct values of the characteristic. If all values are equally probable, a sample of size 11 has at least a 50% probability of having 2 cases that match. If all values aren't equally probable, the probability of a match is even greater. If you have in mind a particular distribution of the values of the characteristic among cases, it's not hard to simulate the specific situation.

Implications for sampling

First, if you're planning to re-sample only 5 out of 300 cases then you probably don't need to worry too much about sampling with versus without replacement. Sampling with replacement has only about a 3.3% chance of having any duplicate case in that situation.

Second, it's not clear why you seem to be worried about ending up with a match of a value of your characteristic within your re-sample of 5 cases. The underlying population from which you drew the 300 cases for each arm of your trial will necessarily have multiple matches of all values of the characteristic. Insofar as you are trying to use sampling to represent what's going on in the underlying population, it's not clear why such a value match should be a problem.

Even duplicate cases in a re-sample don't necessarily pose a problem. Re-sampling with replacement has the advantage that the selection of cases from the original sample is independent; each case always has its original probability of being selected at each step. In contrast, sampling without replacement means that the cases already chosen alter the probabilities of selecting subsequent cases, so that sampling isn't independent.

Bootstrapping, to estimate a distribution of parameter values or the generalizability of a modeling process in the underlying population from which the original sample was taken, typically uses re-sampling with replacement of the same size as the original data sample. In that method, over 1/3 of each re-sample usually are cases that are at least duplicates of others. Nevertheless, all selections within each re-sample are independent.

Having replicate cases in a re-sample doesn't by itself lead to bias; the process of re-sampling with replacement from the data sample mimics the independent-case sampling used to get the original data sample from the population. You can think about duplicate cases in the re-sample as representing members of the underlying population that are "nearby" in some sense. If you're worried about bias, you thus might be better off sampling with replacement (although in your example of re-sampling 5 out of 300 the difference is small).

---

*The table is copied from the Wikipedia page. The R functions qbirthday() and pbirthday() provide calculations of minimum sample size to have a desired probability of a match, and the probability of a match for a given sample size.