Balls and bins question with nlogn balls and n bins. 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.
 A: 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.
