Balls and bins question with nlogn balls and n bins.

Question

The question: Suppose we randomly drop nlogn balls into n bins. Give an upper bound on the expectation of the maximum number of balls in any bin.

How would this be done?

I believe the answer is well on the order of the mean, but I don't remember how to obtain it.

Answer 1

Too long for a comment:

You might want to look at theorem 1 of http://www14.in.tum.de/personen/raab/publ/balls.pdf

Alternatively, the distribution of balls in each bin is not quite independent of the others. Nor is the binomial distribution the same as the normal distribution. And $n \log_e n$ is not an integer.

But ignoring those inconvenient facts for the moment, applying a previous answer on the maximum of normal random variables seems to suggest that something like $\frac{\text{balls}}{\text{bins}} $ $+ \sqrt{\frac{\text{balls}}{\text{bins}} \times 2 \log_e(\text{bins})}$ might be an upper bound or at least a rough approximation.

Here with $\text{bins} =n$ and $\text{balls} = n \log_e n$, this approximation would simplify to $(\sqrt{2}+1)\log_e n$, about $2.414$ times the mean.

As an illustration, consider $n=235$ so $n \log_e n \approx 1283.003$, so we might take $235$ bins and $1283$ balls. We would have $(\sqrt{2}+1)\log_e n \approx 13.18$. Compare this with the following simulation in R:

set.seed(2016)     # for replication
bins  <- 235
balls <- 1283 
cases <- 10000     # number of simulations
simmax <- numeric()
for (i in 1:cases){
  simmax[i] <- max(table(sample(bins, balls, replace=TRUE)))
  }
mean(simmax)
# 13.0313

which is quite close.