Suppose I have $n$ balls and $n$ bins. Each ball $i$ has weight $w_i$. Let the total weight be $T = \sum_{i=1}^n w_i$. We throw the balls into the bins randomly, i.e., each ball lands into a random bin.

Can we argue that with constant probability, if you take the heaviest ball that lands into each non-empty bin, you get a set of balls whose total weight is $c T$ for some constant $c \in [0,1]$? I prefer $c$ as close to $1$ as possible but I want to make sure that the probability that happens is at least a constant.

  • $\begingroup$ I think you meant ~ $(1-1/e)T$ ? $\endgroup$ Commented Apr 28, 2017 at 2:23
  • 2
    $\begingroup$ Indeed I did: If you have $n$ balls of equal weights, and you take one ball from each non-empty bin, you will with high probability get total weight approximately $(1-1/e)T$. If the balls weigh different amounts, I think this can only increase the weight (it clearly can only increase the expected weight ... I don't know what it does when you want constant probability.) $\endgroup$ Commented Apr 28, 2017 at 2:25
  • $\begingroup$ Are the weights guaranteed to be positive integers? $\endgroup$
    – D.W.
    Commented Apr 28, 2017 at 6:25
  • $\begingroup$ @D.W. yes though I think the the answer above is correct . In expectation, you should get 1-1/e fraction of T in the worse case where all balls have equal weights. $\endgroup$ Commented Apr 28, 2017 at 6:28
  • 3
    $\begingroup$ Assume that $w_1 \geq \dots \geq w_n$. Then, the expected weight is $\sum_{i=1}^n (1-1/n)^{i-1} w_i\approx \sum_{i=1}^n e^{-i/n} w_i \gtrapprox (1-1/e)T$. The inequality is (approximately) tight when all $w_i$'s are equal. $\endgroup$
    – Yury
    Commented Apr 28, 2017 at 16:21

1 Answer 1


Suppose you have $n$ balls. Take a random ball from each non-empty bin. Your expected weight is approximately $(1-1/e)T$. This holds because the probability that a bin is empty is $(1-1/n)^n \approx 1/e$. Thus, the expected number of balls you get is $(1-1/e)n$, and these are a random sample of all the balls.

Now, suppose you have balls whose weights are not all equal. Then the expected weight is at least $(1-1/e)T$, because you always take the largest ball from each bin. However, you never get a total weight larger than $T$. This means that at least half the time, you must get a weight of at least $(1-2/e)T$.

You're never going to get $c > 1-1/e$. That's probably the right answer for $c$, but to get it you probably need to use probability theory that's at least a little more sophisticated than I did.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.