0
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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 . $\endgroup$
    – whuber ♦
    Commented Oct 5, 2023 at 12:39
  • $\begingroup$ 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. $\endgroup$
    – AAC
    Commented Oct 7, 2023 at 10:33
  • $\begingroup$ 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. $\endgroup$
    – whuber ♦
    Commented Oct 7, 2023 at 11:11
  • $\begingroup$ 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. $\endgroup$
    – AAC
    Commented Oct 7, 2023 at 19:34
  • 1
    $\begingroup$ I see. In that case it's actually closer to "packets" where the size of the packets are a fixed fraction of the total. $\endgroup$
    – AAC
    Commented Oct 7, 2023 at 20:15

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.