1
$\begingroup$

I'm trying to understand a proof in a paper I'm reading. It relies on a balls and bins problem.

Here is what I'm trying to figure out: We want the maximum number of balls in a bin. We have 2 balls and 2 bins. We have a lower bound of 3/2. How do I see that the lower bound is 3/2?

Here is the context: To compute the social cost of the equilibrium we see this as the problem of throwing m balls into m bins. The social cost of the equilibrium is equal to the expected maximum number of balls in a bin which is well known to be (log m/ log log m) Given that the optimal solution has cost 1, the lower bound follows. For m = 2, this gives a lower bound of 3/2. (taken from Section 3 of http://cgi.di.uoa.gr/~elias/publications/paper-kp09.pdf)

$\endgroup$
1
$\begingroup$

There is a 50% chance that there are two balls in one bin and 50% there are one ball in each bin.

The maximum of the first case is 2; the maximum of the second is 1.

$$.5*2+.5*1 = \frac{3}{2}$$

The above explains why the maximum for a 2x2 bin is what it is if the likely hood is 50:50. If it is p:

$$p^2*2+2p(1-p)*1+2*(1-p)^2 = 2(p+(1-p))^2-2p(1-p) = 2-2p(1-p)$$

$p(1-p)$ between 0 and 1 has a maximum at $p=.5$ of $.5(1-.5)=.25$

Ergo: the minimum of the problem is 1.5

$\endgroup$
  • $\begingroup$ I thought we were trying to find the max number of balls in a case, which would be 2. $\endgroup$ – larry Nov 7 '13 at 19:27
  • $\begingroup$ To be clear for anyone who needs it, the paper needed to describe the minimum expected value of f where f is the largest number of balls in a bin when the balls are randomly placed in each bin. The 3/2 refered to the case of 2 bins and 2 balls and $\Theta\frac{log n}{log log n}$ somehow refered to n bins and n balls. $\endgroup$ – kaine Nov 7 '13 at 22:24
  • $\begingroup$ Why is there a 50% there are 2 balls in one bin $\endgroup$ – larry Nov 7 '13 at 22:56
  • $\begingroup$ If you place one ball in 2 bins, no mater what there will be one bin empty and one bin with one ball. When you place in the second ball iff there is no skew (there is 50:50 chance of going in either basket) there is a 50% chance of the second ball going into the one with the first. If there is a skew between bins, the chance of there being 2 balls in a bin is more than 50%. The only exception to this is if the "random" placement preferentially avoids already placed balls which this problem does not address. $\endgroup$ – kaine Nov 8 '13 at 13:54
  • 1
    $\begingroup$ a) placing one ball in two bins means you take one ball and (usually) randomly toss it into one of two bins. b) If you have one empty bin and one bin with one ball in it and there is equal probability of the second ball going in either bin, randomly placing a ball in one of those two bins will either yield two balls in one bin or one ball in each bin with equal probabilty. That is a 50:50 chance. 50:50 chance means 50% probability of 2 ball in one bin. I show in my answer that this is the minimum. $\endgroup$ – kaine Nov 8 '13 at 16:11

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.