# Distribution of max number of common balls

I have $n$ different balls numbered $\{1,\dots, i, \dots, n\}$. I choose $n$ balls, uniformly at random, with replacement. Let $X_i$ denote the number of times ball $i$ has been chosen. I would like to derive the distribution of $M = \text{max}(X_i)$. What is its average and $90^{\text{th}}$ percentile value?

• Nice question. Now what ? May 4, 2016 at 7:47
• I'm not sure I understand. May 4, 2016 at 8:40
• As usual, compute the CDF of the sample maximum. Then make use of it to get the expected value. For the 90th percentile I'm afraid you may need to fall back to numerical method only.
– BGM
May 4, 2016 at 9:32
• @BGM I think you may be misinterpreting the question - it is not about order stats May 4, 2016 at 18:58
• To OP: I have edited the question to try resolve some notational issues - please check you are happy with the edits. May 6, 2016 at 20:31

I think this is an interesting and original question. The idea is simple:

Suppose we take 10 samples with replacement from $U(1,10)$ and record say:

  {8,4,7,8,5,7,9,7,2,1}


The OP is interested in the maximum number of common items $M$: in this case, $M = 3$, because there are 3 values of ball $i=7$. What is the pmf of $M$?

The problem the OP is trying to solve is related to the Mutinomial distribution with pmf:

$$f\left(x_1,\ldots ,x_n\right)=P\left(X_1=x_1,\ldots ,X_n=x_n\right)=\frac{n! }{ x_1! \cdots x_n!} \; p_1^{x_1} \cdots p_n^{x_n}$$

where $X_i$ is the number of recorded values of ball $i$, subject to: $$\sum _{i=1}^n x_i=n \quad \text{and} \quad p_i= \frac1n$$

Exact Symbolic derivation

In the case with $n = 3$ (a trinomial), the exact pmf of $M$ can be derived as:

• $P(M=1) \quad = \quad P(X_1 = 1 \text{ And } X_2 = 1 \text{ And } X_3 = 1) = \quad \frac29$
• $P(M=2) \quad = \quad P(X_1 = 2 \text{ Or } X_2 = 2 \text{ Or } X_3 = 2) \quad = \quad \frac69$
• $P(M=3) \quad = \quad P(X_1 = 3 \text{ Or } X_2 = 3 \text{ Or } X_3 = 3) \quad = \quad \frac19$

which matches a Monte Carlo simulation of the pmf of $M$:

The above should provide a structure to take things further symbolically, though it may be arduous to do so.

Monte Carlo derivation

Here is some code (here using Mathematica) to generate say 100,000 pseudorandom drawings of $M$, given $n$ balls:

maxData[n_] := Table[Max[Transpose[Tally[RandomInteger[{1, n}, n]]][[2]]],  10^5];


For example:

data = maxData[20];


will generate 100,000 drawings of $M$, given $n=20$ balls. It takes about $\frac14$ second to generate. For faster performance on computers that have more than 1 core, replace Table with ParallelTable.

In the case of $n = 10$, the pmf of $M$ (here via Monte Carlo) appears:

The following diagram compares the pmf of $M$ when $n = 50$ and $n = 100$: