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$.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
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. 


This is addressed by Bruce Levin, 1983, "On Calculations Involving the Maximum Cell Frequency." Also in http://www.jstor.org/stable/2347220 . 

