Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.