Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Just a quick followup question: The lower bound seems a bit insufficient for what I need. So alternatively, can we give a concentration bound on $b_i$? In particular, can we reasonably upper-bound the probability that $b_i$ is larger than some function of $n$, for any $i$? From what I understand from the Wikipedia entry, the variance of $b_i$ is given by: $Var[b_i/n] \approx \frac{b_i (n-b_i)}{n^2}(1-e^{-t/2n}) < b_i/n$, right? If that's true, we can just apply, say, Chebyshev's inequality for that purpose, right?
Right. $o(1)$ was supposed to be $o_n(1)$; i.e., it approaches $1$ as $n$ grows. For starters, I want to know how fast it converges to $1-1/n$. In particular, what is the probability of stopping with $b_t=0$ for $t =O(\log n)$?
As it turns out, one could use the Poisson approximation to estimate the distribution of the minimum load. (cf. Corollary 5.11 in p. 103 in link. Asked a similar question about $n$ Poisson variables in a separate post:link
