It has been years since I last studied Probability, please feel free to correct any mistakes in my approach.
What is the average number of distinct numbers in N random non-negative numbers less than a thousand?
Given integers from 0 to 999 (inclusive). Choose N integers such that all integers are equally likely to be selected. How many distinct integers do you have in N on average?
[Edit:
I changed the following question (from a textbook about algorithms) into the one I asked above.
What is the average number of distinct keys that FrequencyCounter will find among N random nonnegative integers less than 1,000, for N=10, 10^2 , 10^3 , 10^4, 10^5, and 10^6 ?
My understanding of the question is from 1...999 you select N numbers randomly, that is in no specific way. I think we can assume selecting each number is equally likely. Repetitions are allowed. Now do this for infinite times. Take a note of all results for each experiment somehow and assume all those results are equally likely. Now pick one of the results. How many distinct numbers are that in that result on average?
]
Here is my attempt:
I can choose 1000^N different lists of numbers, that is any number may repeat with any frequency in a list of size N.
If I were to choose sets (distinct numbers in the list) of size N, then the number of different sets should be P(1000, N) (permutations). However in the context of the question order of the elements should not be significant, so the correct number should be C(1000, N) (combinations).
The probability of me choosing all distinct numbers should be Px = C(1000, N)/(1000^N).
Now, how do I get to calculate an average number? Is it 1000 * Px? Somehow this doesn't sound right.
By the way, is my understanding of average number correct? I mean, I do this experiment infinite times and the number of distinct numbers in that set converges to a number which we call average? Though I am guessing that number should depend on the distribution of distinct numbers and calculated accordingly.