# Distribution of Maximum of a uniform multinomial distribution

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

-

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}$$