How many random to get n unique integers

Asked Jul 19 '17 at 18:18

Active Jul 20 '17 at 00:33

Viewed 46 times

How many random integers from (1-n) must I produce to get all n integers
Assume a perfect random
Because of duplicates it will be more than n

I understand there will be variance but is there an upper bound?

From this program it is about (5 to 6) * n random to get n unique

It is same as the dice question. If I have an n sided dice how many rolls to get all n.

private static int Guesses()
{
    Random rand = new Random();
    int sample = 100;
    int sum = 0;
    HashSet<int> hs = new HashSet<int>();
    for (int j = 0; j < sample * sample; j++)
    {
        hs.Clear();
        do
        {
            hs.Add(rand.Next(sample));
            sum++;
        }  while (hs.Count < sample);
    }
    Debug.WriteLine(sum / sample / sample);
    return (sum / sample / sample / sample);
}

edited Jul 19 '17 at 20:09

asked Jul 19 '17 at 18:18

paparazzo

1

N unique what? Your question is unclear. – Tim Jul 19 '17 at 18:43
1

https://stats.stackexchange.com/questions/48396/how-often-do-you-have-to-roll-a-6-sided-die-to-obtain-every-number-at-least-once – Sycorax Jul 19 '17 at 18:51
@Tim integer - I will up date the question – paparazzo Jul 19 '17 at 19:30
@Sycorax Yes it is duplicate. I flagged it. – paparazzo Jul 19 '17 at 19:33
"From this program it is about (5 to 6) * n random to get n unique." Hmm, if n = 1, then (5 to 6) * 1 are not needed. 1 will suffice. Basing your rule of thumb on one particular value of n (100) is not a good way of getting a rule valid for general n. – Mark L. Stone Jul 19 '17 at 19:37
@MarkL.Stone OK from this program it is 5-6 * n if n = 100. – paparazzo Jul 19 '17 at 19:42
With what probability? – Mark L. Stone Jul 19 '17 at 19:45
@MarkL.Stone I don't know. I don't know how this is done. – paparazzo Jul 19 '17 at 19:56
I believe this is just another version of the [coupon-collector's problem](https://en.wikipedia.org/wiki/Coupon_collector%27s_problem) on which we have many questions: http://stats.stackexchange.com/questions/tagged/coupon-collector-problem – Glen_b Jul 20 '17 at 00:32

How many random to get n unique integers

0 Answers0