Friday, February 20, 2015

On the Envelope Problem

A continuation of a discussion from Facebook, with hopefully enough context that others can catch up using this post.  (or pose questions in the comments that I can respond to).



The Envelope Problem:

Omega (who never lies) walks up to you and states "these envelopes contain the values X and 2X" He then SHUFFLES them up [this informs us our subsequent switching strategy should be irrelevant], slides one over to you. He states "I have given you an envelope containing either X or 2X. You can open it, and then decide whether you'd like to switch for the other envelope." You open it up, see a $100 bill. Do you switch? Some decision theory has to take you from probabilistic knowledge about the world to an action you should take, if you care about acting (VNM) rationally.

Premises and Conclusion of EV Calculus Using the Same EV Calculus Rules We Normally Use:

1) Your envelope contains $100.
2) the other envelope contains $50 with .5 probability, and $200 with .5 probability
3) Half the time, switching costs me $50.  Half the time, switching gains me $100
4) therefore, I stand to gain an average of $25 by switching.

Which numbered part do you think is false?

If you think it's 2) because the state of the world is already fixed by Omega, rather than variable, then I offer this: when something has a fixed state, but your knowledge of it is probabilistic, ev calculus treats it as if it is not determined but will be at the stated probabilities.  If you disagree, then your next task is to explain how we calculate the odds of being dealt an ace from a shuffled but now fixed-state deck of playing cards.

We can solve this using logic other than EV calculus, namely an observation that since the envelopes were shuffled and fixed, switching can't change our actual EV unless we know something new about the other envelope, and we do not.  We know as much as we did before our envelope was opened.  But why are steps 1-4 above so persuasive under the same logic we correctly apply to cards being dealt from a shuffled deck, despite leading to the wrong conclusion (that switching is +ev)?

"When we switch we stand to finish with 1.5x, if we don't switch, we stand to finish with 1.5x" is incomplete work.  You observe $100 in your envelope.  So at the very least you should be able to redo your math and get us an actual dollar amount EV.  It has to be $100 since your premise is switching doesn't matter.  That means X = $66.66 in the earlier formulation of "we are guaranteed 1.5x."  Well, if X = $66.66, your envelope must contain either $66.66 or $123.33 by reference to the rules of the game.  So your solution is not well formed, it is not coherent.

[EDIT 1 Below]

Stolzman is arguing that EV calculus doesn't apply here, but that's not an issue.  Well, it's a major issue if EV calculus gives you neither the correct answer nor an indication as you work through steps 1-4 that you shouldn't be using this method.  In other words, it doesn't just fail to return an answer, it returns the wrong answer!  Only because we have access to other logic do we even realize it has failed.  This is a big problem.

[EDIT 2 Below]

Well, I correctly predicted Step 2 is where the action is, but people don't seem to agree with my note on it above.  Yes, the state of the universe is fixed.  No, your knowledge about the state of the universe does not therefore use only 1 and 0 as probabilities.  If a coin is biased (unfair) but you do not know in which direction, your probability estimates of heads and tails are each .5.  Probability is in the mind.  http://lesswrong.com/lw/oj/probability_is_in_the_mind/

Omega may have filled the envelopes with $50 and $100 because his son was born in the galaxy his people call "50zba100".  Or he may have filled them with $100 and $200 for any other whismsical reason.  We do not have access to his algorithm.  But since he has not given any hints as to which he picked, why should you not switch?  Why should you not act under P(50) = .5 and P(100) = .5, which most closely approximates your state of knowledge?  Furthermore, NOT switching is implying that $50&$100 is LESS likely than $100&$200 (otherwise you're a fool).  That is your implied conclusion when you do not switch, having seen $100.  How did you arrive there with such confidence?

66 comments:

  1. Part (2) is wrong indeed. The problem statement doesn't provide a probability distribution for X from which you can infer part (2).

    ReplyDelete
    Replies
    1. From what I can tell, that doesn't make step 2 wrong, just unprovable. If we decide that (2) is reasonable, we should switch. If we consider the dollar amount to be extraordinarily high, however, we might reasonably assign the probabilities differently.

      Delete
    2. I feel like Frank is right. My reasoning goes as follows: let's say we decide step 2 is reasonable. What does the distribution of possible envelope contents look like? We have that
      P(X=2a | Y=a) = p(X=0.5a | Y=a), and equivalently
      P(Y=2a | X=a) = p(Y=0.5a | X=a) for all positive a.
      This leads to the expectations E(X | Y=y) = 1.25y and E(Y | X=x) = 1.25x, which was the troubling result from the original problem.

      If we received 50 dollars in our envelope, under the EV calculus logic above we'd conclude 25 and 100 were equally likely. 200 -> 100 and 400. Since we got 100, if we believe the distribution that Omega sampled the envelope contents from a distribution with this property then we have to conclude that 100*(any integer power of 2) is a valid number for the contents. That is, there are infinitely many outcomes, all equally likely. This means that the probability of any particular outcome (or finite range of outcomes) is zero. The distribution only assigns mass to the values 0 dollars and infinity dollars. These values satisfy the problematic expectations above.

      But we got 100 dollars already, so Omega *cannot* be sampling from a distribution with this property - step 2 has to be wrong. How the probabilities of the other envelope containing twice or half as much are assigned is still unknown, but they can't be equal for arbitrary amounts in the starting envelope. The fact that we've observed 100 dollars is information with which we should condition our expectations, but doing that depends on additional knowledge about Omega's process that we don't have in the problem statement. The EV calculus logic can't be applied.

      Delete
  2. Step 2 is wrong because you switched your variables. You can't say that if my envelope has $100 in it, the other envelope has either $50 or $200, because you've switched your frame of reference - you've changed the value of X. You're positing then the either you're in the winning half of a small game, or you're in the losing half of a big game. But the game is set.

    The envelopes have the values X and 2X, for some value of X. Let's say X is $50, and therefore the envelopes have $50 and $100 in them. You pick one of the envelopes at random, and so you have a 50% chance of hitting the $100. If you did and you switch, you lose $50. You also have a 50% chance of hitting the $50 envelope, and if you did and you switch, you gain $50. Therefore the EV of switching is 50% of -$50 + 50% of $50 = 0 as we expect.

    ReplyDelete
  3. Step 2 is wrong because once you see that your envelope has $100, the probability is no longer 50% that the other envelope has $50 and 50% that it has $200. It may or may not be possible for you to calculate what the probabilities now are, but whatever method Omega used to determine how much money to put in the initial envelope, the number of possible universes where there is $50 in one and $100 in the other is not guaranteed to be the same as the number of possible universes in which there is $100 in one and $200 in the other. (It might be... for instance, he could flip a coin and go 50/100 on heads and 100/200 on tails. In that case, if you see 100, then switching is correct because of the original argument. BUT, in that case, if you saw 50 then switching would be correct and if you saw 200 it would be incorrect). So there isn't necessarily a winning strategy for that game without perfect information. But the paradox vanishes.

    ReplyDelete
  4. Alex. I feel like Matt's response to this might go something like this (Matt, feel free to correct me if I'm wrong): If you had to guess the probability with which a certain card was on top of a deck of playing cards, you would be correct to say 1/52. This is the case even if Omega stacks the deck beforehand. Even though you don't know his motivations (he might shuffle it fairly, or he might always put the 7 of spades on top), you can still come up with a "fair betting line" with anyone who doesn't know Omega's process. In the case of the envelopes, it SEEMS the fair betting line for switching is 100 to win 125. Now, I do think there is a problem here somewhere, but I'm not sure you've addressed it...?

    ReplyDelete
  5. Alex, I feel like you were more on the right track with your first comment, that you switched your variables.

    You don't need to find out how much is in the envelope for the problem to emerge...you simply have to switch your variable. For example, you know the envelopes contain X and 2X. Now he hands you one. You assign it the value "X" (this is an incorrect assignment). Now you assign the other envelope a value of 2X or X/2 from your faulty premise. So you determine envelope 2 is worth 1.25X. So you switch and now you have the other envelope with value 1.25X. Well, if it's worth 1.25X, you certainly know the other envelope must be worth either 2.5X or ..625X. So the other envelope is worth 1.5625X now....Repeat ad infinitum.

    When you open the envelope and it contains 100, you have gained precisely 0 information, and cannot do any math to make switching correct. The mistake is that when you realized the value, you suddenly "switched the variables" and made 100 worth X. Which solves a different problem entirely, namely the one in which the other envelope truly is still probabilistic.

    ReplyDelete
  6. I feel like the counter-intuitiveness is exactly opposite from the Monty Hall Problem. In MHP, it feels like you haven't gained as much information as you actually have. In this paradox, if it is one, it feels like you've gained information that you actually haven't.

    ReplyDelete
  7. I think the boring answer from a bayesian theory of probability/decision theoretic perspective is that you are confusing subjective probabilities (à la Savage) with objective probabilities (à la VNM). A decision maker who had some "rational" decision rule would act as though they were evaluate EVs with respect to their subjective beliefs over the possible values of X (or of the top card). Seeing the $100 would cause them to update their beliefs via bayes rule, and they would choose to switch or not based on that.

    ReplyDelete
  8. This might be a little "out there," but is it possible to reject premise 3 without rejecting premise 2? When considering the top card of a shuffled deck, the actual experimental outcomes will behave in a probabilistic way. If you repeat the experiment over and over, 1/52 times the ace of spades will be at the top. If you repeat this envelope experiment over and over it will absolutely NOT be the case that half the time you will lose 50 and half the time you will gain 100. Either 100% of the time you will lose 50 or 100% of the time you will gain 100. Maybe there needs to be an addendum to calculation of EV that says you cannot use it as normal if it will not behave in a probabilistic way over repeated trials?

    ReplyDelete
  9. John: I don't think what you're saying makes any sense. I'm claiming that once you see that $100 is the value in the first envelope you have gained new information, and the probability is no longer 50% $50 and 50% $200. You seem to be disagreeing, I guess. But if you disagree, then there is a paradox. You can't resolve the paradox just by saying "well, keep switching and you'll see that you end up back where you started". That IS the paradox. The paradox is that IF you believe that the two probabilities (that you have big and that you have small) are equal, then switching is correct. (And in fact switching is correct in the $100-then-flip-a-coin case.) So what's different about the X-and-2X-and-you-see-$100 case and the $100-and-flip-a-coin case? The only difference is that once you have opened one of the envelopes you have information. That _has_ to be where the trick/paradox is because there isn't anywhere else for it to be.

    ReplyDelete
  10. You can't "repeated the experiment over and over", because you will NOT see $100 in a random envelope 50 times in a row. At least, you certainly can't guarantee it. You can repeat the $100-and-flip-a-coin-for-$50-or-$200 experiment over and over, and it will fairly quickly be clear that in fact you should switch because that comes out better on average. But to repeat this experiment over and over again, we'd need to know what methodology Omega used to generate the first number, which he then doubled to generate the second number. It's because such a methodology must exist in order for the experiment to be performed at all that new information is gained once we open the envelope, even if it's hard for us to know what that information is.

    ReplyDelete
    Replies
    1. "new information is gained once we open the envelope" Have I converted you to a switcher?? If it's new information, I hope you aren't backing up to your prior estimates from before you had that new information?

      Delete
  11. Alex, if you don't know what is in either envelope, no one would argue for a switch. That is clear, because it is clear that you are doing fuzzy math when you start the logic of "if my envelope is worth X then the other envelope is worth 1.25x, but if that is worth 1.25x then mine is worth 1.5625x..." It is very clear that it does not matter if you switch if you do not know the contents of either envelope.

    What people seem to believe is that there is an information change when you do open the envelope, which would make switching correct. We agree it is not the case that switching is any better. But you argue that you HAVE gained information, but you still arrive at the same result as not knowing what's in your envelope?

    ReplyDelete
  12. EV theory is based on something called the tower rule or law of iterated expectations, if that jogs anyone's memory or provides people better google terms.

    The problem with the 4 steps above is in step 2.
    You can't do step 2 just ONE time, you need to do it twice, because $50 and $200 can never exist together! Above, you say the envelope is either 50 or 200 with a .5 probability, but that's not what we are calculating, we are calculating the EV of choosing to switch or stay. Remember that STAY is always $100. So if you compare 50 and 200, you are comparing SWITCH and SWITCH! But you never have that option, so a comparison of those numbers is irrelevant.

    There are four possible outcomes from the whole game: subgame one: 50 and 100 or subgame two: 100 and 200. You can't just add these up and divide by four, however, *because we aren't choosing from four envelopes*, we are choosing from two envelopes, given a condition, and we don't know whether that condition is true.

    So we are either in a world where we stand to win an expected $75, or we are in a world where we stand to win an expected $150, and we just don't know yet. In either world, there's no value in switching.

    To calculate EV, we calculate average amount to be won in the *game we are playing* (game 1 is 100 v 50, game 2 is 100 v 200).
    The envelope game is two games, so it introduces conditional probability, and has two expected values for two different games, which do not get added up until the very end. In each game, the value of choosing to switch is zero, and zero plus zero is nil.

    ReplyDelete
    Replies
    1. "So we are either in a world where we stand to win an expected $75, or we are in a world where we stand to win an expected $150, and we just don't know yet. In either world, there's no value in switching." Great, I switch! If I don't switch, I never realize a gain in the $150 ev universe, so I'm leaving money on the table. You've reformulated the problem; you've managed to arrive at the same dilemma in a different place, you have not provided a justification for not switching.

      Delete
    2. If you switch, aren't you realizing a loss in the (50, 100) universe? Does that not matter?

      Delete
    3. You realize a loss absolutely, but it is smaller in size than the gains in the other universe. Since we have no reason to assign lower probability to either universe, we should let the outcomes drive the decision and switch - says ev calculus.

      Delete
    4. SWITCHING has an expected value of zero, as a choice. You're using the EV of getting to play the game at all as the justification for making a choice within the game! The value of playing the subgame of 100 v 50 is $75, and value of playing the subgame of 100 v 200 is $150, but there is nothing you can do to change what universe you are in. Given that you are in only one universe, the strategy of switching doesn't add value.

      Delete
    5. Matt, the distribution that each state is equally likely that's not the only prior you can evaluate things. There are other priors where you don't switch (also risk aversion could lead you not to switch).

      Connor's answer is close to what I'd guess the frequentist answer to this is.

      Delete
    6. "Since we have no reason to assign lower probability to either universe, we should let the outcomes drive the decision and switch"

      That is not correct, we have no reason to assume these probabilities to be equal, nor different. They are just not defined. Treating the absence of information as information is logically faulty and is the error that spawns your paradox. When you chose to consider them equal because nothing proves you are necessarily wrong in doing so you are biasing the analysis imposing on your problem constraints that are not there (p[100/200]=p[50/100]). You could have just as easily (and wrongly) decided that nothing prevents you from saying p[100/200]=0. Then switching is always wrong ! The outcome in the analysis is driven by the bias we introduce (with no valid reason).

      Delete
  13. Alex, you say "you cannot repeat the experiment because you will not see $100 in a random envelope over and over." This isn't exactly what I meant by repeating the experiment. You use the same envelopes every game (the ones Omega picked) and keep repeating the experiment. Every time you pick 100, switching will yield the same result. With a deck of cards, you can use the exact same deck, but the results will behave in a probabilistic way, which will not be true for repeating this experiment with the same envelopes.

    ReplyDelete
  14. People are using paradox way too loosely, this problem is well formulated, at least from a bayesian perspective.

    Writing this out way too formally, let (x,y) be money in envelope 1, and money in envelope 2. Without looking in the envelope, the possible events are W={(x,2x)| for all x in R^2} U {(2x, x)| for all x in R^2}. The problem without opening an envelope and looking in it is to choose the envelope that you believe to have the higher value (assuming expected values are well defined), i.e.

    Max_i E(value in envelope i)

    Once you've looked in an envelope, you've gained the information, so the new problem is
    Max_i E(value in envelope i| $100 in envelope j)
    where envelope j is the one you opened. This changes the set of possible events to {(100,200), (100,50)} (when j=1). This is how you are using the information gained. Your beliefs on this could potentially be different than your beliefs ex-ante that envelope 1 is on average more valuable than envelope 2.

    A natural prior is to put equal probability on all events in W (or put equal probability on a subset of events in W and 0 on the rest), then knowing $100 was in envelope 1 wouldn't change anything really (it would change the expectations, the expected value from both envelopes is now $100), but another prior could justify switching.

    A frequentist would say this is all bullshit, but I think this is roughly the bayesian setup for this problem.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. Oops, assuming equal probabilities on events you do switch, this is the calculation done in the post.

      Delete
  15. Oh, while I was writing people already touched on this, cool.

    ReplyDelete
  16. This was such an interesting problem.

    The scenarios before anything happens are below, there are only four scenarios.

    Scenario A - First Envelope is x, 2nd Envelope is x/2

    Envelope 1 (chosen) --> x
    Envelope 2 (value after switch) --> x/2

    Scenario B - First Envelope is x/2, 2nd Envelope is x

    Envelope 1 (chosen) --> x/2
    Envelope 2 (value after switch) --> x

    Scenario C - First Envelope is x, 2nd Envelope is 2x

    Envelope 1 (chosen) --> x
    Envelope 2 (value after switch) --> 2x

    Scenario D - First Envelope is 2x, 2nd Envelope is x

    Envelope 1 (chosen) --> 2x
    Envelope 2 (value after switch) --> x


    So, the "extra value" comes from seeing a value, and that we PRESUME the value we see is x as if x is random. The problem is, we never pick the small envelope in this example, because if we did, we would have x/4 somewhere in our calculations, and we won't have that if we always assume we pick x and the only other options for the other envelope is x/2 and 2x.

    There is a chance that if you choose an envelope that you pick the x/2, and before seeing anything, you need to include that possibility. The "knowledge" of seeing a number is what allows us to presume we chose x, it normalizes the variable x in a way that we are not allowed to if we never see anything - not seeing any envelopes requires that we consider 4 situations instead of 2, "which x did i choose, the lower of the [x,2x], the higher of [x,2x], or the lower of [x,x/2] or higher of [x,x/2].

    By seeing an envelope, we go from 4 options to 2 options, and our probabilities and ev change when we lose those two options.

    If we know an envelope x, the other envelope is 2x or x/2, the average lets ev = 5x/4. Cool.

    If we don't know x, then we have 4 options and we average all of them.

    Scenario A total value after switching = x/2
    Scenario B total value after switching = x
    Scenario C total value after switching = 2x
    Scenario D total value after switching = x

    Average of values = (x/2 + x + 2x + x) / 2 = 9x/8. Whoa.

    I think the extra value comes from having 50% chance to end up with x, in the abstract. Basically, if we never look and always switch, there's only a 25% chance we ever get the lowest value (x/2), and a 25% chance we get the highest value (2x), and a 50% chance we end up with x.

    However, if we SEE a value, and consider that to be x and average our 2 remaining scenarios, we get rid of our middle two options, leaving us with 2x 50% of the time and x/2 50% of the time.

    So, that's where it went. There's probably a lot more to glean inside of this rabbit hole of a problem, it only seems hard because of how our brain misfires in terms of specific instances of intuitive calculations of probability, much like the kinds of mistakes we would make if our number system was base 7 or base 12, or something. Our instincts keep this problem complicated, I think.

    ReplyDelete
  17. Suppose I present the same puzzle, but prefix it with by saying "Omega rolls 8d20 to generate a number, writes it on a piece of paper, then doubles it..." or "Omega goes to a random wikipedia page, finds the first positive integer he sees, and writes it on a piece of paper" or "Omega generates a random 32-bit positive integer and writes it on a piece of paper...". In any of those cases, knowing the methodology clearly makes the paradox vanish, because now seeing the number absolutely lets you do some math and assign probabilities that are not guaranteed to be equal to the two cases. My argument is that Omega HAD to have had a methodology for how he came up with the first number, even if you don't know what that methodology is. Therefore, seeing the number generates information even if you don't know what the correct thing is to do with that information. So while in a practical sense I have no idea what the "right" answer is if you actually play the game with a live person and see $100, there is no longer a paradox as long as you are sure that there was some method, even a non-mathematical-seeming-one, for generating the number in the first place. I'm not interested in trying to come up with how to actually play the game, I'm interested in why the obvious and generally sensible mathematical analysis leads to a seeming paradox.

    ReplyDelete
    Replies
    1. So do you switch? Your reasoning that the value observed is useful information would lead me to conclude you switch.

      Delete
    2. How (or even if we can) to interpret in probability with respect to non-random events has been a debate in probability theory for a long time. This may not be the easiest thing to read, but the wikipedia entry is a reasonable reference.

      http://en.wikipedia.org/wiki/Probability_interpretations

      Delete
    3. Anon, the problem is indeed very old and very much under debate. My beef is with those who claim to have it all figured out, which on this particular problem you will encounter over and over and over again if you pose it correctly as I have tried to do.

      Delete
  18. Consider this version of the game: Omega selects a random integer from 1 to 1000, flat distribution. All parties know that. Then we play the game. I open the envelope and see 100. At this point, it is correct to switch, by the obvious EV math. Interestingly, if someone else is playing at the same time and he gets the other envelope, he sees either 50 or 200, and it is correct for HIM to switch as well, given the information. Which is weird, a correct strategy in which both of us pick up our envelopes, look at the numbers and both correctly choose to switch, given the information that we have. But there is no paradox, because if you look at your envelope and see a number > 1000 then you don't switch. So while it's still counterintuitive, it's no longer paradoxical... you no longer have a winning strategy of picking up the envelope, looking at the number, then always switching no matter what. As for whether I would actually switch, I have no idea, it's beyond me to properly calculate it. But that doesn't mean it's paradoxical.

    ReplyDelete
  19. I would ask Omega to take mt to his OWN envelope, ensuring I will get to the city of truth tellers either way.

    ReplyDelete
  20. Huh. I was reading about this on Wikipedia, and my impression is that the appearance of paradox comes from mixing up some subtly different scenarios. Consider two possibilities:

    1. An amount of money, X, is chosen. This money is then split into two envelopes, such that one envelope has X/3 dollars and the other envelope has 2X/3 dollars. These envelopes are shuffled, and you're given one of them. It has either X/3 or 2X/3 dollars, with equal probability. Switching gives you a 50% chance of gaining X/3 dollars, and a 50% chance of losing X/3 dollars. Switching is therefore neutral.

    2. An amount of money, X, is chosen. This money is then put into envelope A. Then, 2X is put into envelope B. These envelopes are shuffled, and you're given one of them. It has either X dollars or 2X dollars, with equal probability. Switching gives you a 50% chance of gaining X dollars, and a 50% chance of losing X dollars. Switching is therefore neutral.

    3. An amount of money, X, is chosen. That money is point into envelope A. Then, either X/2 or 2X is put into envelope B. The process for determining which of these happens could vary, but for this let's put it as a random process with equal odds. So, the amount of total money in the envelopes is either 3X/2 or 3X, with a 50% chance of each. There is no shuffling. You are given envelope A. Now, there is a 50% chance that switching costs you X/2, and a 50% chance that switching gains you X. So, switching is correct.

    The shuffling is the key thing. Since Matt's description specifies that the envelopes were shuffled, we know that we aren't in scenario 3. Therefore, switching is neutral.

    ReplyDelete
    Replies
    1. The problem is that we don't know what scenario we're in. We only know the dollar amounts of one of the envelopes. So from our perspective, the situation looks like this:

      An amount of money, X, is chosen. This money is then split into two envelopes, such that one envelope has X/3 dollars and the other envelope has 2X/3 dollars. These envelopes are shuffled, and you're given one of them. You open it, finding Y dollars. (Y may be either X/3 or 2X/3.) One of two scenarios is possible:

      1. Y is X/3, such that X=3Y. You gain 2Y dollars by switching.
      2. Y is 2X/3, such that X=1.5Y. You lose 0.5Y dollars by switching.

      Since all we know is Y, our choice hinges on the probabilities that we assign to being in scenario 1 or 2. If we suppose that the probability is 50/50, we should switch. It might be reasonable to suppose that the probability is not 50/50 under certain circumstances, however (e.g., if Y is very large).

      Delete
    2. Your Y is not the same in 1 and 2, which obfuscates what is actually happening. X is the only fixed amount.

      1. Y is X/3, such that X=3Y. You gain 1Y dollars (you already have Y, and switch to 2Y) to go from X/3 to 2X/3.
      2. Y is 2X/3, such that X=1.5Y. You lose 0.5 Y (you have Y, switch to 0.5 Y) to go from 2X/3 to X/3.

      It makes no difference whether we switch in a 50/50 scenario.

      Frank Karsten is correct: seeing $100 does not provide new information unless we already have information about the likelihood of the total dollar amount.

      Delete
    3. If it weren't for the element of incomplete information, you'd be absolutely right. In terms of the way God/the universe/Omega see the situation, you're right. But from the perspective of the person opening the envelope, only Y is known, not X. So the solution to the problem hinges on one's guess at what the probability distribution P(X) looks like. The main problem, I think, is that assuming P(X) = 0.5 for all X doesn't make sense. If there's only one dollar in the envelope, the probability that we're in the Y=X/3 situation is probably more than 50% (he really just put quarters in the other one?). If there's 1 trillion dollars in the envelope, we're almost certainly in the Y=2X/3 situation (there aren't 3 trillion physical dollars in circulation).

      Under the very strange circumstance that Omega is an omnipotent alien who creates dollars from thin air and attaches no special significance to any number in particular, then I accept that switching is appropriate. The problem is, that assumption leads to an unbounded, uniform probability distribution that cannot be treated using normal probability math. If we assume any reasonable distribution, the probability distribution P(X) has to go to zero at some point, and there will be some dollar amounts for which we do not switch.

      If you're still not convinced, I'll agree to disagree.

      Delete
  21. https://www.youtube.com/watch?v=kpj5PwydV9o

    This guy explains it better than my previous comment, but we are saying the same things.

    ReplyDelete
  22. This is actually very simple. Your 2) stating that it's 50% each is incorrect. There's actually a 66.6% chance that the other envelope contains $50 and 33.3% chance that it contains $200.

    Changing envelope or not doesn't matter EV wise of course, the other envelope has an average value of 0.666 * $50 + 0.333 * $200 = $100, same as the one you already have (duh).

    ReplyDelete
    Replies
    1. Um...no. There is no way to definitively assign those probabilities, given the parameters of the problem.

      Delete
  23. OK...I'd like to try to bring some common sense to bear on this problem.

    First, note that this is qualitatively different than the Monty Hall problem. In that case, we know the distribution of the rewards, and are given incomplete information and asked to make a decision. That incomplete information allows us to increase our probability of a favorable result.

    A corollary to this problem offers a useful counterpoint. Say you know that the envelopes contain $100 and $50; they are shuffled, you're handed one, but you *don't* get to look at it before deciding whether to switch. It's fairly intuitive that switching is EV-neutral; you'll either gain or lose $50.

    Unlike the Monty Hall problem and this much simpler variant on the envelope problem, in the actual envelope problem, we don't know what the possible rewards are, and therefore can't definitively assign probabilities without invoking an external assumption. IF the external assumption we invoke is Matt's premise 2, then I'm perfectly happy to accept the conclusion that we should switch. However, we do have a few pieces of information on which to build a slightly more sophisticated version of premise 2, most notably the information that we will get dollars. The total number of dollars in circulation is $1.34 trillion, so if there is more than a third that amount in the envelope, we should certainly not switch. It also seems reasonable to expect that the probability of doubling up is much less than 50% for a wide range of dollar amounts below $446.67 billion as well. For instance, it is probably rational, on finding $20,000 in the envelope, to think "There's no way there's $40,000 in the other one; I'm surprised I even got this much" and not switch. Or perhaps you need $500 for rent money, and there's $600 in the envelope. You might be incentivized not to switch in order to make sure you can pay your rent.

    Now, you might argue that all these practical considerations have nothing to do with the mathematics of the situation. I agree. But they have a lot to do with people's "gut reaction" to the problem, and I would say most people intuitively expect that there is some value above which one should not switch. With a purely mathematical, EV-based approach and accepting premise 2 (which is neither "correct" nor "incorrect" but an external assumption that can neither be proven nor disproven), we should switch every time.

    ReplyDelete
    Replies
    1. Came here to say this but Joshua already got it - just wanted more people to see it who are scrolling through -

      "A corollary to this problem offers a useful counterpoint. Say you know that the envelopes contain $100 and $50; they are shuffled, you're handed one, but you *don't* get to look at it before deciding whether to switch. It's fairly intuitive that switching is EV-neutral; you'll either gain or lose $50."

      Delete
  24. Matt would you still switch if you didn't get to look at the envelop? If he handed you an envelop and said "Would you like to switch?"

    ReplyDelete
    Replies
    1. To be clear, I don't switch. I think ev calculation returns the wrong result, and I don't follow it. Do you mean, would your ev calculation still return "Switch is +ev" if the envelope is not opened? Yes, it would, but it just makes the moving parts harder to keep separated (it's hard to remember which X means what, but easy to remember $100 bills are worth $100.). But ya, .5 *.5x + .5 * 2x = 1.25x.

      Delete
    2. This is of course an absurd result, as the second you receive another choice to switch you will choose to switch back. I'm not a switcher. But I can't use ev calculus to show why, and that is the paradox.

      Delete
    3. Right, I didn't realize until I reread the thread that you think this is a deficiency with the EV method. The "blind switching" just reaffirms the absurdity of it. Then what about if he offers you to switch it back again? :D

      It's really bothering me and I'm trying to understand it. The youtube connor posted is nice but it still doesn't explicitly make me see what's wrong with Step 2. Patrick's point where you are off by more in the 50/100 universe than in the 100/200 seems to be getting through to me though.

      Delete
    4. I think Connor and Chapin are wrong and are doing mental gymnastics to make it look like "hey, the ev calculus is fine" but their logic won't generalize to other scenarios and thus is not a real decision theory but merely an explanation after other observations about switching are observed.

      Delete
    5. I'm sorry but I don't see why 2) should be right at all. EV calculations don't prescribe that when no information on a given probability distribution is available you should assume uniform distribution. Of course, the result of the calculation depends on the distribution. So if you assume uniform you find a result and if you assume some other scenario you get something different (usually). If we lack the knowledge to discriminate between potential distributions the EV calc is not able to give us a result. In our case it is even worse since the problem is not even that we don't know but that we can not know, in the sense that these distributions are not unknown but undefined

      Delete
  25. The problem is in step 3. In order for step 3 to be true for all X, our prior for omega's choice of x has to be uniform over the integers, and such a probability distribution does not exist. If it is not uniform, then the amount of money in the envelope gives us information about whether it is X or 2X, so it is not 50/50.

    ReplyDelete
    Replies
    1. And by step 3, I meant step 2, but the point that there is no state of knowledge where 2 is true for all X remains.

      Delete
  26. This comment has been removed by the author.

    ReplyDelete
  27. Haven't read all the comments, but Frank is right. We know that that one envelope contains X and one envelope contains 0.5X, but we lack information on the distribution of the random variable X.

    We implicitly assume that the X is drawn from a uniform distribution on the interval [0 m] in the limit m going to infinity. But in this case, our EV before opening an envelope is also infinity, which leads to very weird scenarios as illustrated in this example.
    A helpful (although not very mathematical) way of thinking may be the following: Before we open an envelope, we know that our EV is infinity, but if we open an envelope we will always see a finite number, so 'it makes sense' that switching increases our EV. (This 'solves' the paradox since infinity = 1.25*infinity)

    On the other hand, lets assume there is a (finite) upper bound M for X, i.e. X is uniformly distributed on [0 M]. (You could for example think of M as the total worldwide amount of physical money ;)). Then, if we open an envelope which contains less than M/2, switching indeed increases our EV, but if we open >M/2 we are sure that the other envelope only contains half as much money.

    ReplyDelete
    Replies
    1. Another 'weird scenario involving an unbounded expectation':

      Assume that you are offered the following a game: You throw a coin until it lands 'heads' for the first time, and then get a payout of 2^N dollar, where N is the number of throws.

      How much would you be willing to pay to play the game once? :)

      Delete
  28. The video posted by Connor was pretty helpful, to be honest. Patrick Chapin's comment from his article today (which was what brought me here in the first place) was actually pretty astute as well. For me, the comparison between this situation and the one where, instead of shuffling two envelopes, you have an envelope and are offered a chance at switching it for an envelope that contains either half or twice as much is what cleared was very helpful. While the situations may seem identical on the surface, the subtle difference between them is what resolves the paradox to my satisfaction (which is definitely different from completely resolving it).

    I'll admit that every time I think I have resolved the paradox in terms of my understanding of the problem, the moment of resolution is brief and fleeting. The wikipedia article seems to reinforce that experience. Despite there being apparently simple resolutions to the paradox, there is a lot to explore with regards to how the paradox reveals flaws in different methods of mathematical reasoning.

    wiki article: http://en.wikipedia.org/wiki/Two_envelopes_problem

    ReplyDelete
  29. Are all things equal for the us as the person choosing as well? I feel like I would switch 100% of the time because it's irrelevant to me if I receive 50.00$, 100.00$ or 200.00$ If I opened the envelop and it had 1 000 000.00$ inside I doubt I would go for the bigger score.

    ReplyDelete
    Replies
    1. After a few more seconds of thought I'm just asking is this a question of a person doing this exercise or are we trying to be logic robots.

      Delete
  30. Omega shuffles the envelopes right... doesn't that imply he doesn't know which is which?

    ReplyDelete
  31. Just one more way to look at things if people are still having problems:

    If you open $100, and you decide that there is a 50/50 chance that the other envelope has either $50 or $200, then you have to include the scenario where you opened those envelopes too. In the situation where you open that $50, you would assume there is either $25 or $100 in the other envelope. If you open the $200 envelope, you would assume the other envelope has either $100 or $400. The confusion comes from ignoring these lines of the possibility tree. There is no value in switching.

    If someone posted this already I apologize for not reading the comments thoroughly enough. I am lazy and there are a lot of them.

    ReplyDelete
    Replies
    1. This is still a bit confusing. Your line of reasoning explains why it doesn't make sense to switch without opening, but if you open and see 100$, it could very well be the case that you benefit from switching. Whether or not this is the case depends on how the contents of the envelopes are generated (i.e. the distribution of the contents).

      Delete
    2. Assume that, before handing you the envelopes, Omega determines their content in the following way: with probability p he puts 50$ in one envelope and 100$ in the other one, and with probability 1-p he chooses 100$ and 200$. He then shuffles the envelopes and lets you choose one of them. Lets call the envelope you choose A and the one you didn't choose B.
      For the expected value of envelope A holds:

      E[A] = p*(0.5*50$+0.5*100$)+(1-p)*(0.5*100$+0.5*200$)=150$-p*75$

      The same is obviously true for E[B] so switching doesn't make any sense. But if you open A and see 100$, you have gained additional information and this changes everything.

      The easiest examples are the limiting cases p=0 and p=1. Then you know for certain what is inside B, and you always gain/always lose by switching. In general, there holds:

      E[B | A=100$] = 50$*P(B=50$ | A=100$)+ 200$*P(B=200$ | A=100$)=p*50$+(1-p)*200$=200$-p*150$.

      E[B | A=100$] > 100$ if and only if p<2/3. So if p<2/3, you should switch after seeing 100$, and if p>2/3 you shouldn't.

      Delete
    3. To see what is wrong in this paradox, imagine Omega had prefaced his offer this way: “Yesterday, I asked Alpha (who always follows requests exactly) to perform the following task. I gave him eighteen $50 dollar bills, two blank envelopes, a third envelope that was stamped and addressed to me, and a six-sided die. I asked him to privately roll the die, and put that many $50 bills in the first blank envelope, twice that many in the second, and whatever was left in the addressed envelope. He was then to put the addressed envelope in the mail, and give me the other two. These are the envelopes I now offer to you.”

      Essentially, this is telling you that X is uniformly distributed in {$50, $100, $150, $200, $250, $300}. Before you open an envelope, each envelope has an expected value of $262.50. If you don’t look inside the first one you choose, there is no reason to switch, even though you know one envelope has X and the other has 2X.

      If you do look and see $100, you still don’t know if this is X or 2X. And it is only your knowledge of the range of values X can take on that allows you to say the probability of $50 (or $200) being in the other envelope is 50%. If the preface had used $100 bills, then you’d be certain the other envelope contained $200. Or if $8.33 bills existed, and were used, then you’d be certain the other envelope contained $50.

      The point is that there are two random variables in this problem, X and N, and what you know is that your envelope contains N*X. If you know nothing of X, then odds that N is 1 or 2 are 50:50. But your envelope contains N*X, and the other contains (3-N)*X. The expected value of each is 3X/2. If you know the value of your envelope without knowing how X is distributed, that value is not X. It is either X, or 2X, and is expected to be 3X/2.

      Delete
  32. I didn’t read if anyone else came to this conclusion, but what follows appears to hold true. If anyone can spot any errors that would be most appreciated!
    Receiving X or 2X is a 50:50 probability which results in us receiving an average of 1.5X, in the long run. We can treat this average 1.5X as just some number or amount of money denoted as Y. By exchanging/switching the amount Y, we stand to either receive 2Y (double that amount of money) or 1/2Y (half that amount of money). This is also a 50:50 probability, resulting in:
    Switch = 1/2(2Y) + 1/2(1/2Y) = Y + 1/4Y = 5Y/4

    We are now left with:
    Stay = Y
    Switch = 5Y/4

    Gain = Switch – Stay = 5Y/4 – Y = Y/4

    Substituting X back in, we get:
    Stay = 1.5X, on average
    Switch = 5(1.5X)/4 = 1.875X, on average

    So, by switching, on average we gain 0.375X, if we assume X can take any value > 0 with an equal probability distribution. i.e. the envelopes contain any dollar amount greater than zero, and one envelope has twice as much as the other.

    Example:
    Suppose in one instance, envelopes A and B respectively contain $100 and $200. If we open envelope A, half of the time we will suspect B to contain $50 (in the case where X = $50 and envelope A contains 2X), and the other half of the time it will contain $200 dollars. By switching, we gain $25 on average.

    This is verified using the first formula above:

    Stay = Y
    If Y = $100 (i.e. keep envelope A)
    Switch = 5Y/4 = 5(100)/4 = $125
    Gain = Switch – Stay = $125 - $100 = +$25
    Now if we opened envelope B, half of the time we will suspect A to contain $100, and the other half of the time it will contain $400 dollars. By switching, we gain $50 on average.

    Again, this is verified using the first formula above:

    Stay = Y
    If Y = $200 (i.e. keep envelope B)
    Switch = 5(200)/4 = $250
    Gain = $250 - $200 = $50
    If we are always switching the envelopes when we know the dollar amount inside, we should always switch when we don’t open them either.

    In that case, keeping with the $100 and $200 envelopes, half of the time we’ll switch a $100 envelope which gains us $25 on average, and the other half of the time we’ll switch a $200 envelope witch gains us $50 on average.

    Therefore, if we always switch we’ll gain: 0.5($25) + 0.5($50) = $37.5
    This is verified using the second formula above:

    If X = $100
    2X = $200
    Stay = 0.5(X) + 0.5(2X) = 1.5X or 0.5($100) + 0.5($200) = $150

    Keeping the received envelope gives us $150 on average
    Switch = 5(1.5X)/4 = 5($150)/4 = $187.5

    Gain = Switch – Stay = $187.5 - $150 = $37.5

    Which leads us to the general solution of switching, without looking at the contents, gaining, on average, 0.375X:

    e.g. if X = $100 then 0.375($100) = $37.5

    ReplyDelete
    Replies
    1. If this holds true, and X is any value > 0 with an equal probability distribution, is this a game with an infinite expected value?

      The whole thing kind of reminded me of the St. Petersburg lottery, which is interesting to read about. Definitely leads to more practical scenarios when you start considering expected utility rather than just value/payoff.

      Delete
  33. You are calculating EV wrong here.

    You get an enveloppe with a certain Value (v) in it. Half the time you get X, half the time you get 2X, but you don't know which you get. Let's call the low values x, the high values X.
    25% you get x, call this v
    25% you get 2x, call this 2v

    25% you get X, also 2v
    25% you get 2X, this equals 4v

    So, EV before switching:
    0,25 * v +
    0,25 * 2v +
    0,25 * 2v +
    0,25 * 4v =
    2,5v

    If you switch, you get:
    0,25 * 2v (x into 2x)
    0,25 * v (2x into x)
    0,25 * 4v (X into 2x)
    0,25 * 2v (2X into X)
    total 2,5v

    ReplyDelete
  34. Hello my name is Kathy Smith and i want to testify about the powerful magical mirror that helped my life in positive ways and that blessed me. I have been hearing about this magical mirror for long and i have been searching for a way to get it but to no avail all my efforts seemed to be in vain but my cousin's friend told me how she ordered for the magical mirror from Dada Magical a powerful man from Africa and how she used it and how she became blessed. At first i thought it was a joke but i decided to order for it by contacting Magicalmirrorofgoodness@hotmail.com and i got it. To my greatest surprise, the mirror was even better than what i expected. The magical mirror is really a good one and it worked and it is still with me and it is still working. The magical mirror is HARMLESS and it is not scaring. it tells me what to do and what not to do, it reveals deep secret to me, it protect me and it tells me who is against me and who is my true friend. It suggest good ideas for me and it has made me rich too and in fact the magical mirror is a solution because is provide and can tell you solution to your problems. Am so excited and am so endowed and blessed to have the magical mirror with me. This magical mirror helps protect against evil. This is real and you can get it and see for your self so if you need the magical mirror don't hesitate to get it and you can get it by contacting Magicalmirrorofgoodness@hotmail.com

    ReplyDelete