Distribution of Maximum of a uniform multinomial distribution - MathOverflow

Distribution of Maximum of a uniform multinomial distribution

2012-08-17T22:14:40Z

Hello, I'm working with a data structure which uses a uniform distribution to bucket the inputs into $k$ buckets. The efficiency of the structure is bounded by the $\frac{k_{max}}n$, where $n$ is the number of items. How many elements are in each bucket will follow a uniform multinomial distribution. What will the distribution be for the number in the largest bin. We can assume that $n$ is much larger than $k$, and an approximate answer is good. I just want to be able to say something like: the largest bucket will have at most $(1.5k)/n$ elements with probability $p$.

Answer by tergi for Distribution of Maximum of a uniform multinomial distribution

2012-08-17T23:08:59Z

This is addressed by Bruce Levin, 1983, "On Calculations Involving the Maximum Cell Frequency."

Also in http://www.jstor.org/stable/2347220 .

Answer by Douglas Zare for Distribution of Maximum of a uniform multinomial distribution

2012-08-17T23:19:36Z

The probability that there is at least one bin with at least $c$ items is less than or equal to the expected number of bins with at least $c$ items, which is $k$ times the probability that a particular bin has at least $c$ items. You can bound the probability that a particular bin contains at least $c$ items using the Hoeffding inequality.

$$\begin{eqnarray}Pr(\max \ge n/k + d) & \le & k Pr(\text{Binomial}(n,1/k) \ge n/k + d) \\ & \le & k \exp(-2d^2/n).\end{eqnarray} $$

There are sharper bounds available such as the Chernoff bound, but this is simple and it sounds like it will suffice.