# CSE Blog - quant, math, computer science puzzles

Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

## Jan 12, 2010

### Two envelopes Problem

Source: Wikipedia (Classical "Exchange Paradox" problem)

Problem:

The setup:

The player is given two indistinguishable envelopes, each of which contains a positive sum of money. One envelope contains twice as much as the other. The player may select one envelope and keep whatever amount it contains, but upon selection, is offered the possibility to take the other envelope instead.

The switching argument:
1. Denote by A the amount in the selected envelope.
2. The probability that A is the smaller amount is 1/2, and that it's the larger also 1/2
3. The other envelope may contain either 2A or A/2
4. If A is the smaller amount, the other envelope contains 2A
5. If A is the larger amount, the other envelope contains A/2
6. Thus, the other envelope contains 2A with probability 1/2 and A/2 with probability 1/2
7. So the expected value of the money in the other envelope is: $\frac{1}{2} 2A + \frac{1}{2} \frac{A}{2} = \frac{5}{4}A$
8. This is greater than A, so swapping is favored
9. After the switch, reason in exactly the same manner as above, but denote the second envelope's contents as B
10. It follows that the most rational thing to do is to swap back again
11. This line of reasoning dictates that envelopes be swapped indefinitely
12. As it seems more rational to open just any envelope than to swap indefinitely, the player is left with a paradox.
The puzzle:

The puzzle is to find the flaw, the erroneous step, in the switching argument above. This includes determining exactly why and under what conditions that step is not correct, in order to be sure not to make this mistake in a more complicated situation where the misstep may not be so obvious. In short, the problem is to solve the paradox.

Disclaimer: The problem sometimes is included under "unsolved" problems. A thought and study should be great anyways. :)

1. Flaw : Probabilities of individual steps should not be independent but dependent on path already taken in decision tree .

So if we use conditional probabilities instead 1/2 , we know that once we have seen both envelopes all probability variables should be 0 or 1.

PS: If it is unsolved , then it is obvl wrong. So lets find flaw in this simple argument first :P

2. I'll go with the assumption that you are not shown contents of envelope before finally deciding on one.....For that case I'll go with choosing any envelope shouldn't matter and no swapping is needed...but if contents are shown then Nikhil is correct.
So, I think the question is whether contents are shown or not.....In either case there is no point in going on swapping forever.

3. @viki.. For the paradox, it does not matter whether you show the contents or not. It seems whether u see the content or not, you will have to swap forever.

@nikhil.. Your argument is correct. Seeing the money to be x in the first envelope does not imply that with probability half the amount of money in second envelope is 2x and with prob half it is x/2. But, as given in the wikipedia link, its dependent on conditional probabilities. Lack of information about an object should not be mistaken with randomized object.

@Nikhil.. You have a good eye for probability (Refer to the classroom scene of the movie 21 :P).. Nice. Wikipedia says this is still an open problem among the subjectivists as no consensus has been reached yet. (No citation :P)

4. @ Pratik : AAaah , not quite the scene of 21 - I dont get a cool sports car ! :P

5. One solution is this: Switching when you find a very low value is obviously a good plan. But if you see a value so large that it surprises you, then it might be a bad idea to switch. If the amount X in the envelope surprises you because it is very large... that's because you guess than the average envelope contains much less. The fact that you saw X is consistent with one of the following:

> The envelopes are better than I thought, and the prizes are X and X/2.

> The envelopes are much better than I thought, and the prizes are X and 2X.

If your "surprise curve" says that odds of those two conditions are, say 9:4 in favor of the first case, then you should not switch, as the costs of switching down exceed the benefits of switching up. Now, suppose you are surprised to see \$3000, but you figure "I would be more surprised to see twice as much, but not twice as surprised," then you are assuming that the distribution of
"what the value could be" is very flat. But, in fact, that distribution is so flat that it doesn't have a finite integral. That is: the distribution of "what a value could be" has to be
rather tight in order to be integrable. You believe in integrability if you believe "the probability that the prize is between 1 and a million coins is greater than 0.00001" or any
similar statement, with the parameters "1", "a million" and "0.00001" replaced by anything.

I think that this paradox is compelling because you should definitely switch from a median value. This is balanced in the expected-value calculation by the great sums you would lose by switching from a high value.

6. one approach that comes to my mind is to analyze the case when the money in envelope is a real number in the interval [0,A]. Then take limit A->infinity.

in this approach, it will matter if u see the contents of envelope because, if the number > A/2, then for sure, u wont swap.