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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.