# balls and bins: the first time when max-loaded is less than twice min-loaded

We have $n$ bins, in each step we throw a ball in a bin chosen uniformly and independently from the $n$ bins we have.

We repeat the process $k$ times. Let $B_k$ be the number of balls in maximum-loaded bin after $k$ steps, and $b_k$, accordingly, the number of balls in minimum-loaded bin after $k$ steps.

Let $K\ge 1$ be the number of step in which we had $2b_K\ge B_K$ for the first time.

I need to find function $f(n)$ and two constants $0<c_1\le c_2$ such that

$c_1f(n)\le T\le c_2f(n)$ with ptobability tending to $1$.

• Very similar to this question – David Moews Feb 17 '13 at 19:00
• And even more similar to this deleted question – joriki Feb 17 '13 at 19:43
• @joriki Now I see both linked questions are deleted. If they are so similar to this one, and have answers, should someone undelete them? – 40 votes Jul 14 '13 at 0:25