Randomly picking from $n$ choices roughly $n$ times. What's the resulting frequency distribution called?

Question

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:

1. Is this correct?
2. How would you calculate the expected frequency of the most frequent chosen number?
3. 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$.

Answer 1

You can calculate the probability $p(k)$ that a particular number was chosen exactly $k$ times: $$p(k)={m\choose k}\frac{(n-1)^{(m-k)}}{n^m}.$$

From this, you can calculate the expected count of numbers which occur exactly $k$ times, $n~p(k)$.

When $n$ is large and $n p(k)$ is small, then the events that particular numbers occur exactly $k$ times are close to independent. So, the distribution of the count of events which occur exactly $k$ times is close to Poisson. The variance is slightly smaller, similar to a hypergeometric distribution.

This lets you approximate the probability that there is at least one value with multiplicity of at least $k$. The sum of these probabilities is the expected value of the highest count. Some exact calculations are possible for small $k$ but the expressions are increasingly messy as $k$ increases when $n \gg k$.

Understanding this distribution is not necessary to solve the problem you say motivated the study of this distribution. The probability that the first $m$ draws are different from the $m+1$st draw is simply

$$\bigg(\frac{n-1}{n}\bigg)^m .$$

Answer 2

The process you describe generates a multinomial distribution on the set $\{1,\ldots,n\}$. Let $p = <p_1, \ldots, p_n>$ describe the probability distribution for each draw, so that for $i=1,\ldots,n$, $p_i$ is the probability of drawing an $i$, with $p_i \geq 0$ for all $i$ and $\sum p_i = 1$. Let $X_i$ be the number of times $i$ is drawn. Then the random vector $X = <X_1, \ldots, X_n >$ has a multinomial distribution with parameters $m$ and $p$. The probability that $X$ takes a particular value $<x_1, \ldots, x_n>$ is given by

$\Pr[X = x_1, \ldots, x_n>]=\frac{m!}{x_1!\cdots x_n!} p_1^{x_1} \cdots p_n^{x_n}$.

Using this expression, you could compute the order statistics of the multinomial distribution. The value of the most frequently chosen number is called the first order statistic of $X$.

I am not familiar with the properties of the distribution of the first order statistic of a multinomial random variable. However, I believe this Wikipedia article may give you the guidance you need to compute the distribution of the first order statistic, allowing you to investigate them yourself.