How would you divide 50 black and 50 white marbles into two piles, not necessarily of same size, so that the probability of picking a white marble as follows is maximized: we first pick one of the piles uniformly at random, then we pick a marble in that pile uniformly at random?

Folklore.

Put one white marble into one pile and the rest of the marbles into the second pile. The overall probability of drawing a white marble are close to 75%.

Formally proving that putting one white in one pile is the optimal solution requires some work. Let us analyze the general case with w white marbles and b black marbles, where both w and b are positive integers. If the two piles are equi-sized, then no matter how we distribute the balls, the probability of drawing a white is . This configuration is always superior to putting all balls in one pile and making the other pile empty. We are now left with configurations with unequal pile sizes, with each pile having at least one marble each. Divide the marbles arbitrarily into two piles with U and V marbles each, with U < V. We now change the configuration in three steps. With each step, the overall probability of drawing a white marble increases.

Step 1: Repeatedly swap one black marble from the first pile with one white marble from the second pile. One such swap increases the overall probability of drawing a white marble by . If w ≥ U, the smaller pile has only white marbles, and we skip Step 2 and go directly to Step 3. However, if w < U, the larger pile has only black marbles and we execute Step 2.

Step 2 (executed only if w < U) Repeatedly transfer a black marble in the smaller pile to the larger pile. Clearly, this operation increases the overall probability of drawing a white marble. At the end of this step, the smaller pile has only white marbles.

Step 3: At the end of Steps 1 and 2, the smaller pile has only white marbles. Repeatedly move one white marble from the smaller pile to the larger pile, leaving only one white marble behind.

For the resulting configuration, the overall probability of drawing a white marble is , which simplifies to , which exceeds when w + b > 2, because for any w' > 0. So the optimal configuration has one white marble in one pile and all others in the second pile. The only exception is the case w = b = 1 in which both marbles may be in the same pile.

Thanks to Puneet Pamnani and Arijit Sarcar for developing the above proof at lunch today!