Balls into bins with random number of balls

Question

In the classical balls into bins we throw $m$ balls into $n$ bins. We throw the balls independently of each other and the probability of choosing the bins is uniform. For $n=m$ it is known that the expected number of balls in the bin, which has the maximal number of balls, is of order

$$ \frac{\log(n)}{\log(\log(n))}$$

for $n \rightarrow \infty$. I wonder what is known about this expectation value (asymptotically) when we start with a random number of balls, e.g. replace the deterministic number $m$ by a random variable, which is for example geometrically distributed with mean $n$ (or any other distribution). Of course I assume that this random variable is independent of the selections of bins.

Literature references or any ideas are highly welcome, even if they treat only a very specific case.

Thank you in advance for any suggestions.

Answer 1

Consider for a moment the case $m=cn$ for some constant $c$. This also yields a maximal load of $(1+o(1))\log(n)/\log(\log(n))$. Geometric distribution with mean $n$ will give you $cn$ balls with high probability, so the asymptotic behaviour of the maximal load will not change.

Answer 2

First a small comment. The maximal load is $\log(n)/\log(\log(n))$ with high probability for $n \to \infty$ and its expectation is asymptotically equivalent to $2 \log(n)/\log(\log(n))$. These things are messed up in the question.

A classical reference for the balls into bins problem is Gonnet's research paper. He also mentions these result in case of $m=cn$ with a fixed constant $c \in (0,\infty)$.

It's not difficult to see, that for $m$ geometrically distributed with mean $n$ the expectation won't decrease asymptotically. However, verifying the same upper bound asymptotically seems messy to me. Can you maybe give a hint on how to estimate the formula, Mr. Gurel-Gurevich?