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)