Distribution of Maximum of a uniform multinomial distribution - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T16:29:31Z http://mathoverflow.net/feeds/question/104948 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/104948/distribution-of-maximum-of-a-uniform-multinomial-distribution Distribution of Maximum of a uniform multinomial distribution Jack 2012-08-17T22:14:40Z 2012-08-18T00:21:00Z <p>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$.</p> http://mathoverflow.net/questions/104948/distribution-of-maximum-of-a-uniform-multinomial-distribution/104954#104954 Answer by tergi for Distribution of Maximum of a uniform multinomial distribution tergi 2012-08-17T23:08:59Z 2012-08-17T23:08:59Z <p>This is addressed by Bruce Levin, 1983, "On Calculations Involving the Maximum Cell Frequency."</p> <p>Also in <a href="http://www.jstor.org/stable/2347220" rel="nofollow">http://www.jstor.org/stable/2347220</a> .</p> http://mathoverflow.net/questions/104948/distribution-of-maximum-of-a-uniform-multinomial-distribution/104955#104955 Answer by Douglas Zare for Distribution of Maximum of a uniform multinomial distribution Douglas Zare 2012-08-17T23:19:36Z 2012-08-18T00:21:00Z <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 <a href="http://en.wikipedia.org/wiki/Hoeffding%27s_inequality" rel="nofollow">Hoeffding inequality</a>.</p> <p>$$\begin{eqnarray}Pr(\max \ge n/k + d) &amp; \le &amp; k Pr(\text{Binomial}(n,1/k) \ge n/k + d) \\ &amp; \le &amp; k \exp(-2d^2/n).\end{eqnarray}$$</p> <p>There are sharper bounds available such as the <a href="http://en.wikipedia.org/wiki/Chernoff_bound" rel="nofollow">Chernoff bound</a>, but this is simple and it sounds like it will suffice.</p>