# Expected number of trials to cover X% of a dataset using a particular iterative sampling scheme

I derived the average number of trials to see x% of a dataset, if during each trial I randomly sample p% of that dataset with replacement (hopefully this is correct):

$$\frac{log(1-x)}{log(1-p)}$$

Now I would like to extend this to the following scenario: in a single trial, first I randomly sample p% of the dataset, then from those particular p% of samples that were chosen randomly sample q% of that data, and then replace everything to the original state. This time, only the q% of the data in the second stage are considered to be "seen." I want to find the average number of trials needed to see x% of the entire dataset.

I'm mainly interested in this "sample of a sample" case, but out of curiosity I would also be interested to see the general solution for N "sample of a sample of a sample of..." problem.

• Your formula clearly is incorrect, as you can tell by considering tiny examples such as a dataset of two elements, $x=100\%,$ and $p=50\%.$ So, you need to back up and reconsider that before proceeding. See our threads on the coupon-collector-problem .
– whuber
Oct 5, 2023 at 12:39
• I attempted to find a variation of the coupon collector problem that fits my question the best, and I came across this: math.stackexchange.com/questions/2021884/… But even this still depends on the dataset size n. In this case for arbitrary "seeing percentage" x, the result is n*log(1/(1-x)). Is there some proof that this cannot be solved without knowing the dataset size ahead of time? I wanted to solve this by only knowing the percentage of data out of the whole set that I want to sample, but it seems it's not possible.
– AAC
Oct 7, 2023 at 10:33
• You can find answers here on CV to various generalizations of this question at stats.stackexchange.com/questions/320152, stats.stackexchange.com/questions/294171, stats.stackexchange.com/questions/110448. The thread at stats.stackexchange.com/questions/487741/… directly answers the question you have asked.
– whuber
Oct 7, 2023 at 11:11
• OK, it seems that it is the same answer as the above question that I linked. But still I do not intuitively understand why the answer is dependent on the dataset size N. If I am sampling some fixed percentage of the dataset, why does it matter how big that dataset is? Does the math break down if I consider a continuous blob of data from which I scoop up p% of the blob on each turn? To me it shouldn't matter how big that blob is, I should get the same result since my scoop is of fixed size. So maybe you can help me understand why I need to know the size of the dataset.
– AAC
Oct 7, 2023 at 19:34
• I see. In that case it's actually closer to "packets" where the size of the packets are a fixed fraction of the total.
– AAC
Oct 7, 2023 at 20:15