<p>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.</p>

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

<p>You're never going to get $c &gt; 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.</p>

CC BY-SA 3.0
2017-04-29T20:46:10.100Z
2017-04-29T20:51:14.920Z
2017-04-29T20:51:14.920Z
Peter Shor 
<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2017-04-28T02:23:21.920Z
I think you meant ~ $(1-1/e)T$ ?
polar_bear_cheese
CC BY-SA 3.0
2017-04-28T02:25:11.347Z
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 
CC BY-SA 3.0
2017-04-28T06:25:08.110Z
Are the weights guaranteed to be positive integers?
D.W.
CC BY-SA 3.0
2017-04-28T06:28:39.220Z
@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.
polar_bear_cheese
CC BY-SA 3.0
2017-04-28T08:19:15.723Z
I don't think this question is precise enough. Are you asking whether there is a $p>0$ such that for all $w_i$'s there's $c$ such that the total weight is *at least* $cT$?
domotorp
CC BY-SA 3.0
2017-04-28T16:21:47.653Z
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
CC BY-SA 3.0
2017-05-02T18:28:04.020Z
@Yury: This is a side technical question, but how do you get the last inequality?
polar_bear_cheese
CC BY-SA 3.0
2017-05-02T18:53:17.990Z
Sequence $w_1, \dots w_n$ majorizes sequence $T/n,\dots, T/n$. Since coefficients $e^{-i/n}$ are decreasing, $\sum e^{-i/n} w_i \geq \sum e^{-i/n} (T/n) = (1 - 1/e) (e^{1/n} - 1)^{-1} (T /n) \approx (1- 1/e)T$.
Yury
<randomized-algorithms><randomness>
Weighted balls and bins
polar_bear_cheese
# Weighted balls and bins

(Asked by: username_0 on 2017-04-27)

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.

**Tags:** randomized-algorithms, randomness
> **Comments:**
> **username_0**: I think you meant ~ $(1-1/e)T$ ?  
> **username_1**: 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.)  
> **username_2**: Are the weights guaranteed to be positive integers?  
> **username_0**: @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.  
> **username_3**: I don't think this question is precise enough. Are you asking whether there is a $p>0$ such that for all $w_i$'s there's $c$ such that the total weight is *at least* $cT$?  
> **username_4**: 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.  
> **username_0**: @Yury: This is a side technical question, but how do you get the last inequality?  
> **username_4**: Sequence $w_1, \dots w_n$ majorizes sequence $T/n,\dots, T/n$. Since coefficients $e^{-i/n}$ are decreasing, $\sum e^{-i/n} w_i \geq \sum e^{-i/n} (T/n) = (1 - 1/e) (e^{1/n} - 1)^{-1} (T /n) \approx (1- 1/e)T$.  

---

## 1 answers

### Answer by username_1 on 2017-04-29. Score: 3 | Accepted answer

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.


---

