Ernie's 3D Pancakes

We're doomed

We have the human genome project, we have Google, we have social networks, we have contributions to many disciplines, and our own discipline, but we argue amongst ourselves about whether emacs is better than vi, Eclipse better than IDEA, C++ better than Java or Scheme, or what objects-first really means.

I'm sorry, but if we don't change what we talk about amongst ourselves, we are doomed to a niche market while the biologists, the economists, the political scientists, etc., start teaching their own computational/modeling/programming/informatics courses. Nearly everyone turns to math for calculus; nearly everyone turns to math/stats for statistics. These are nearly universally acknowledged as basic and foundational for lots of disciplines. In the age of information nearly no discipline at a large scale requires computer science, certainly not programming as we teach it.

— Owen Astrachan, quoted by Eugene Wallingford

Harmonic Hot Air, Part 2

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.

Logic: It's not just for breakfast any more!

From behind the table, I pull out a box of Total Cereal (teaching is just like doing magic tricks, except that you get paid more as a magician). I show them the list of ingredients; "iron, 100 percent" is on the list. I ask by a show of hands whether this is the same iron as in the nails. 3 of 23 kindergarten kids say "yes"; 5 of 44 Harvard graduate students say "yes" (almost the same percent in both classes!).

[via Marginal Revolution]