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)
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