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

124 Views Asked by At

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$.