6
$\begingroup$

Here is a math problem I thought of:

  • Set up:

    • Suppose we have integers 1,2,3...99, 100
    • Each integer has an equal probability of being selected

  • Game:

    • In round=1, we pick 5 numbers randomly without replacement and then put them back
    • In round=2 we again pick 5 numbers randomly without replacement and then put them back
    • We do this until round = 100

I wrote an R program to simulate this situation:

 round   numbers_picked         cumulative_unique_numbers_seen     percent_of_new_numbers
     1  31, 79, 51, 14, 67                              5                    100
     2  42, 50, 43, 14, 25                              9                     80
     3  90, 91, 69, 99, 57                             14                    100
     4   92, 9, 93, 72, 26                             19                    100
     5    7, 42, 9, 83, 36                             22                     60
     6  78, 81, 43, 76, 15                             26                     80
     7    32, 7, 9, 41, 74                             29                     60
     8   23, 27, 60, 53, 7                             33                     80
     9  53, 27, 96, 38, 89                             36                     60
    10  34, 93, 69, 72, 76                             37                     20
    11  63, 13, 82, 97, 91                             41                     80
    12  25, 38, 21, 79, 41                             42                     20
    13  47, 90, 60, 95, 16                             45                     60
    14   94, 6, 72, 86, 97                             48                     60
    15  39, 31, 81, 50, 34                             49                     20

I am wondering if there is some probability distribution that can be used to answer the following question:

  • Question 1: Suppose we are currently at round = n and we have seen "m" unique numbers. If we know that there are 100 total numbers - what is the probability we will have seen 99% of all numbers by round = k? (k>n)
  • Question 2: Suppose we are currently at round = n and we have seen "m" unique numbers. If we DO NOT know that there are 100 total numbers - what is the probability we will have seen 99% of all numbers by round = k? (k>n)

For Question 1, I found out that this is very similar to the Coupon Collector Problem (https://en.wikipedia.org/wiki/Coupon_collector%27s_problem) - but I am not sure how to adapt the answer given in terms of probabilities (given some initial conditions). Only the general expectation and variance are provided. I.e. it tells you how many draws are needed to see all coupons and the variance for the number of draws .... but it doesn't tell you that assuming you have seen n/m coupons in j rounds, what is the probability of seeing (n+k)/m coupons in j+x rounds?

For Question 2, I am not sure if these types of problems can be answered when we don't know the total amount of numbers. I thought perhaps something could be done where we observe if the number of unique coupons seen in each round stabilize towards 0 - heuristically indicating we have seen more and more coupons with higher probabilities?

Can someone please help me answer these? Can we use PGF's? https://en.m.wikipedia.org/wiki/Probability-generating_function

$\endgroup$
5
  • $\begingroup$ You can answer question 1 with a recurrence. For example, if you have seen $49$ unique numbers in the first $15$ rounds, then I think the probability of having seen exactly $99$ unique numbers ($99\%$ of them) in the first $100$ rounds is about $34.701\%$, of having seen exactly $100$ unique numbers (i.e. all of them) is about $52.081\%$ and of having seen fewer than $99$ is about $13.218\%$. That compares to $33.625\%$, $54.708\%$ and $11.666\%$ without the information on the position after $15$ rounds. $\endgroup$
    – Henry
    Commented Jul 24 at 16:05
  • $\begingroup$ Question 2 is more complicated. You could try a Bayesian approach based on a suitable prior for the total number of numbers, updating this to a posterior distribution based on the early information about the number of unique numbers seen (and perhaps the largest number seen), then using that and the recurrence many times to get your probabilities. $\endgroup$
    – Henry
    Commented Jul 24 at 16:13
  • $\begingroup$ @ Henry: Thank you so much for these suggestions! I was even looking at some mathematical/ecology models for the second problem such as Mark and Recapture, as well as the Chao Estimator.... $\endgroup$
    – konofoso
    Commented Jul 26 at 4:27
  • $\begingroup$ An alternative approach for question 2 might be a maximum likelihood approach. $\endgroup$
    – Henry
    Commented Jul 26 at 10:04
  • $\begingroup$ @ Henry: I tried to write a recursion formula but got stuck - can you please help me out here? math.stackexchange.com/questions/4955881/help-using-recursion thank you $\endgroup$
    – konofoso
    Commented Aug 8 at 2:02

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .