Wednesday, May 05, 2010

Paradox Lost

Imagine the following game. You're given $1. Then, you keep flipping a fair coin, and every time the coin lands on heads, your money is doubled. The game ends the first time you see tails.  A little thought reveals that your expected payoff is $1 + (1/2)$2 + (1/4)$4 + (1/8)$8 + ...   = infinity!  No matter how much you're willing to pay per game, if you play enough times, you'll eventually come out ahead.   But how much would you pay to play this game once?

Intuitively, you'd be crazy to pay more than $20, and you'd be right not to. One reason is that your utility for money isn't linear: you just don't value 10 billion dollars 10 times more than 1 billion. Another reason is if you got lucky enough, there wouldn't be enough money in the world to pay your winnings -- capping the game at, say, a trillion dollars makes its expected value only around $20. But you wouldn't get lucky enough -- because one-in-a-trillion events just don't occur in real life.  That you shouldn't pay more than $20 to play this infinitely profitable game is known as the St. Petersburg paradox.

This paradox is related to the two envelopes problem in my previous post (required reading for the next part). The way I set it up, the two envelopes problem is also a game of infinite expectation.  Whether you exchange envelopes or not, your expected payoff a priori is infinite.  That's why you can swap envelopes without even looking at what's in yours and expect to gain about 22% -- 1.22 times infinity is still infinity! And the problem with both the St. Petersburg game and the two envelopes problem is that no matter how much money you get, it's less than the expectation.  In both games, you get a finite amount with probability 1, but what's that compared to infinity?  It's also related to why you always gain in expectation by switching.  So, can we make the game's expected value finite and still get the two envelopes paradox? The answer is no! Paradox lost.

I'm happy enough with this explanation, but I'd love to see other ideas about how to resolve these problems.  The two envelopes problem and others like it bothered me for a long time, but I'm trying to accept that often our intuitions simply break when we deal with infinity.

If you want more detail on these paradoxes, David Chambers has some nice papers, which proved useful in making this post.


  1. Anonymous12:22 AM

    It's not so much that you're dealing with infinity; in fact the simplest way to address the problem uses no infinities at all. In this point of view, the probability distribution you describe simply does not have an expectation value. Which is fine, in some sense; some distributions don't. But if you then turn around and try to use expectations to define a strategy, you're stuck. And the problem is not one of infinity, it's of trying to apply expectation values where they simply aren't defined.

    You could argue, "Okay, fine, so expectation isn't defined. But what happens if I actually do this?" But here too you run into problems. Of course any mathematical concept is only a description of the real world to the extent that its assumptions fit. For a Gaussian distribution (say), the fact that really extreme values would never get measured (say because they'd destroy the equipment) doesn't much affect the expectation value, or the standard deviation of a sample, or any quantity we'd be interested in. But for this crazy distribution, that long tail where the assumption doesn't work is heavy enough that it does matter.

    This sort of thing can happen in physics: normally if you're integrating over (say) a distribution of particles there are so few really high-energy particles that you can just integrate out to infinity and ignore that your physics is wrong that high up. If you're really unlucky, the high energies will completely dominate your problem; but this is usually a sign that you picked the wrong energy range to focus on. But it sometimes happen that you get something like a 1/x distribution of particle energies in the tail. You can't just integrate out to infinity, since it diverges. But there aren't really all that many particles out there... the usual solution is to apply an arbitrary cutoff. Your answer will depend on the cutoff, but only through a logarithm, which is frequently a mild enough dependence that you can have a very crude estimate of the cutoff and get away with it. This spares you dealing with the physics of the high-energy end of the particle spectrum.

  2. You end by stating "So, can we make the game's expected value finite and still get the two envelopes paradox? The answer is no! Paradox lost."

    Unfortunately this is not true. It is indeed possible to restate the problem in such a way that the expected value of the envelope priors are both finite.

  3. I'd love to see that!

  4. OK, this is one example. There are others as well.

    Assume you are on your way from point A to point B, a finite distance. You know that in order to go from A to B you will have to traverse an infinity of points. For example, first you have to go half the distance, then half of what is left and so on, ad infinitum. Let's transform this trivial mathematical fact into a game.

    Say you are in a competition where the goal is to end up as *far* from B as possible, on the path from A to B. You are offered one of two tickets that will magically move you to one of the infinitely many steps towards B described above. The two tickets goes to two adjacent but otherwise randomly chosen steps. You have to pick one of the two offered tickets but you don't know which one will move you the least. So you just take one of the two at random.

    Say you selected the ticket that took you to step 3 which is 1/8 from B. Now you are offered to take the other ticket instead. You know that the other ticket will move you to step 2 or step 4, but you have no clue which is the most likely alternative so you assign both alternatives probability 1/2. If the other ticket will move you to step 4 you will end up 1/16 from B. If the other ticket will move you to step 2 you will end up 1/4 from B. So either you will move 1/16 closer to B by switching or else you will move 2/16 further away from B. So either you gain 2/16 or else you lose 1/16.

    Your reward is directly proportional to the distance from B which means that you can win twice of what you can lose. Therefore it makes perfect sense to take the other ticket instead. But if you had taken the other ticket from the beginning, an analogous reasoning would come to the same conclusion: to swap.

    This version of the two envelopes problem doesn't require an infinitude of resources that we don't have (which is often blamed at). It is played on a finite (bounded) section of the real line and we only use trivial and uncontroversial properties of the real numbers.

    Moreover, whatever probabilities are attached to the prior probability distribution for the tickets chosen the expected ticket value can never exceed the distance between A and B, which by definition is finite.

  5. This doesn't seem well specified to me. You say "you have no clue which is the most likely alternative so you assign both alternatives probability 1/2," but you really need to give me the distribution or strategy that you use for generating tickets, or why should I assign both events a the probability 1/2?

    The other issue I have is that if you get a ticket to Step 1, you know not to switch.

  6. You have two good comments.

    1. Yes, but it's part of the beauty of this example that the prior doesn't have to be specified. However you define the prior distribution (or how you imagine it if you don't know it) the a priori expected value of a ticket is always finite. In fact, for all non-truncated cases where each ticket has some positive probability the a priori expected value of a ticket will be zero.

    It's reasonable to attach each option probability 1/2 because even if you know that they can't be exactly 1/2 in all infinite cases, the chances that they are very close to 1/2 is very high. There is an infinity of tickets and it's likely that three adjacent tickets are chosen with approximately the same probability. The conditional probability will therefore be very close to 1/2.

    2. True, if you get the first ticket you have won. However, as there are infinitely many tickets the probability getting the first ticket can be made arbitrary close to zero, zero included. Same goes for the second, third and so on. So you can safely discard the possibility that the sure bet will happen to you.

    So even before you open your selected ticket you know that you want to take the other one instead. Your explanation above that "infinity times 1.22 is still infinity" can't be used in this case. Instead, here you have to replace this explanation with something like "zero times 1.22 is still zero."

    But I don't know if you feel that blaming it all on the number zero is a convincing explanation...

  7. "It's part of the beauty of this example that the prior doesn't have to be specified."

    Actually, until you specify a distribution that works here, I don't find it convincing.

  8. OK, take the distribution to be a Log-Cauchy distribution then.

  9. This example really made you speechless...

  10. The details need to be worked out. But the Log-Cauchy distribution is so heavy-tailed that it has no finite mean, so it closely reminds me of the St. Petersburg paradox, as well as the distribution I specified for the two-envelopes problem.

    I wonder whether this whole business of buying tickets on the [A,B] interval is conceptually that different from payoffs, or just a reformulation.

  11. The important details are easy to work out. The larger the ticket number the smaller the ticket size and hence the reward. In the limit the ticket value is zero in size. We see immediately from this that the lack of finite mean for Log-Cauchy implies that the (unconditional) expected ticket value must be zero in size. The ticket game transformes infinity into zero.

    From a mathematical point of view this is just a simple coordinate transformation. Completely trivial.

    Philosophically, however, the difference is huge. For the ticket game no expectation is infinite or undefined, so blaming it all on the 'strange concept of infinity' is no longer possible.

    None of the usual ways to 'solve' the St Petersburg paradox works for the ticket game. (None of the unusual either, for that matter.) So, unfortunately, that paradox can't help you out here.

  12. You went silent again...
    You fully understand this example now?

  13. Maybe you like the Jailhouse Clock example better? Please see page 54 in This scenario is completely finite.

  14. In this example, it is no longer true that no matter what value you get, you want to switch. Eg if you get 11, you don't want to switch. If you get 4, it happens that you do. I don't see a paradox here.

    1. If you get 11 you do indeed want to switch. All you know is that either you have the {12, 11} pair or the {11, 9} pair in front of you, each with a 50% probability of being the case. If you switch you will either end up with 12 o'clock which is half of what you have or 9 o'clock which is twice of what you have. So to maximize the expected value you should switch. The same argument works for whatever you find in your envelope. Please note that the clock isn't an entirely ordinary clock.

    2. I'm confused about this example. Even if the clock works strangely at certain times, I don't understand how 11 is worse than 9 -- isn't it always later in the day? Or are you not committing to a day? Also I don't understand how you re-define "twice". By this circular definition it seems that every number is 2^11 times itself.

    3. No we are certainly not committing to just a single day. For example, if you get 4 you know that 2 is half as much. But the real difference between the actual times can be 2 hours, or 15 hours, or 28 hours and so on (13n+2). If it s 2 hours you will be executed the same day and you either win 4 hours or lose 2 hours by switching. If it is 15 hours you will either win 30 hours or lose 15 hours by switching. If it is 28 hours you will either win 56 hours or lose 28 hours by switching. And so on with the worse alternative 13n+2 hours earlier and the better alternative 26n+4 hours later for some n. In this way the real execution times can differ by days, weeks, months or even years and the better alternative if you switch is always twice as long as the worse alternative. So it really does matter which envelope you pick.

  15. This comment has been removed by the author.