2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I think you meant ~ $(1-1/e)T$ ? $\endgroup$ – HTV Apr 28 '17 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$ – Peter Shor Apr 28 '17 at 2:25
  • $\begingroup$ Are the weights guaranteed to be positive integers? $\endgroup$ – D.W. Apr 28 '17 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$ – HTV Apr 28 '17 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 Apr 28 '17 at 16:21
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

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

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