Last week I posted a puzzle that Mohammed Mahdian was spreading around at FOCS. Given n indistinguishable balloons, with capacities 1/k for each integer k between 1 and n, describe a randomized strategy to fill them with as much air as possible, in expectation. Within minutes, someone posted a strategy with expected payoff π²/6. Here is another equivalent strategy:

Set i = 1.

For each balloon in random order:

Try to fill the balloon to 1/i liters.

If the balloon does not pop,

repeat

increment i

until balloon i has not already been popped.

Unlike the straw man I posted last week, this algorithm gets useful information from its failures. When a balloon pops, we learn its capacity, and we know not to look for that balloon in future iterations. It's not hard to see that balloon k (the one with capacity 1/k) survives if and only if it appears last among the k largest balloons, which happens with probability 1/k. So in the limit as n gets big, the expected return is ∑_{k≥ 1} 1/k² = π²/6 ≈ 1.6449 liters.

Despite Danil's posted argument in the comments, this is *not* the best possible strategy. It *might* be the best strategy that either completely fills or pops every balloon, but the rules don't require that! Consider the following alternative:

Set i = 1

For each balloon in random order:

Try to fill the balloon to 1/i liters.

If the balloon does not pop,

Increment i

If balloon i has already been popped, break out of the for loop.

Put 1/n liters in each of the remaining empty balloons.

As in my straw-man strategy, balloon k is fully inflated if and only if balloons 1,2,...,k are encountered in that order, which happens with probability 1/k!. Now suppose balloon k is the largest one that does not survive. We have inflated k-1 random balloons, so the expected number of remaining empty balloons is (n-k+1)/k, which means the expected payoff from the last line of the algorithm is (n-k+1)/kn = 1/k - o(1). Let's retroactively put all this air into (the ghost of) balloon k. NOW we get credit for balloon k if and only if balloons 1,2,...,k-1 are encountered in that order, which happens with probability 1/(k-1)!, so our total expected payoff, in the limit, is ∑_{k≥ 1} 1/k! = **e - 1 ≈ 1.7183 liters**. This is the expected payoff that Mohammed reported at FOCS.

However, even this is not the best possible strategy. UIUC student Dan Cranston had an idea that gives a very small improvement, but since we haven't worked out a full analysis yet, I'll wait a few days before giving away the secret.

## Recent Comments