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$.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Aug 17, 2012 at 23:19
-
$\begingroup$ Do you know anything about the other side? I.e., $\Pr(\max \le n/k + x) \le f(k,n,x)$? $\endgroup$ Commented Nov 21 at 18:26
$\begingroup$
$\endgroup$
This is addressed by Bruce Levin, 1983, "On Calculations Involving the Maximum Cell Frequency."
Also in http://www.jstor.org/stable/2347220 .
