# Weighted balls and bins

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.

• I think you meant ~ $(1-1/e)T$ ? – HTV Apr 28 '17 at 2:23
• 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.) – Peter Shor Apr 28 '17 at 2:25
• Are the weights guaranteed to be positive integers? – D.W. Apr 28 '17 at 6:25
• @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. – HTV Apr 28 '17 at 6:28
• 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. – Yury Apr 28 '17 at 16:21

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.