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?"
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$.