Not sure of the best way of phrasing this question, but I'll give it a go.
If I were to randomly choose whole numbers between 1 and $n$ a significant number of times relative to $n$ (say, $m$, where $m$ is something like 70% of $n$) and then looked at the distribution of frequencies of outcomes, I believe you would get a distribution that wasn't flat. I.e. a very small number of outcomes would come up >1 times, the majority would come up 1 time, and some outcomes would come up 0 times. Obviously, this would be affected by the relative size of $m$ to $n$: If I were to choose a only 10 numbers between 0 and 1,000,000 ($m$=10, $n$=1,000,000), I would expect the vast majority of numbers to have a frequency of 0, with the rest 1.
I have questions:
- Is this correct?
- How would you calculate the expected frequency of the most frequent chosen number?
- If you were to order the outcomes by frequency and then bar graph the frequency, does the resulting curve have a name, or any interesting properties?
I hope this makes some sort of sense. If not, let me know and I'll try and think of a better way of explaining it. This all came from an original question which went something like this: "If I have a lottery machine with 15 million different lottery number outcome combinations, given that I've already made 10 million draws, what is the probability that the 10,000,001th draw has already been drawn?"
Edit:
I ran some monte-carlo simulations for $2<n<650$, with $m$=$n$ and the total number of experiments for each $n$ run 10,000 times and the results averaged. I logged the max frequency, the number of times a number came out 1 time, and the number of times a number comes out 0 times. Two interesting things: The number of numbers that come up 1 time closely matches the calculated $n p(k)$, and this is also close to the number of times a number comes out 0 times. I'm not sure it's obvious that these two should be the same, as $p(k)$ doesn't seem to make sense for $k=0$ (Can you do $m$ choose $0$?). Also, interestingly, a plot of $m$ against the average maximum frequency gives a curve that looks like this:
Obviously some sort of log relationship.
Next step is to vary $m$ as a percentage of $n$.