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



Distribution of Maximum of a uniform multinomial distribution
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](http://en.wikipedia.org/wiki/Hoeffding%27s_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](http://en.wikipedia.org/wiki/Chernoff_bound), but this is simple and it sounds like it will suffice.


