# Two envelopes problem

(Redirected from Exchange paradox)
Jump to: navigation, search

The two envelopes problem, also known as the exchange paradox, is a brain teaser, puzzle, or paradox in logic, probability, and recreational mathematics. It is of special interest in decision theory, and for the Bayesian interpretation of probability theory. Historically, it arose as a variant of the necktie paradox. The problem typically is introduced by formulating a hypothetical challenge of the following type:

Of two indistinguishable envelopes, each containing money, one contains twice as much as the other.
The subject may pick one envelope and keep the money it contains.
Having chosen an envelope at will, but before inspecting it, the subject gets the chance to take the other envelope instead.
What is the optimal rational strategy for maximising the amount of money to be gained?

There is no point at all in switching envelopes as the situation is symmetric. However, the story now introduces the so called switching argument that shows that it is more beneficial to switch. The problem is to show what is wrong with this argument.

## Introduction

### Discussion

Consider the following argument. Suppose the amount in a selected envelope happened to be $20. If the envelope happens to be the larger of the two envelopes ("larger" meaning the one with the larger amount of money), that would mean that the amount in the envelope is twice the amount in the other envelope. So in this case the amount in the other envelope would be$10.

However, if the selected envelope is the smaller of the two envelopes, that would mean that the amount in the other envelope is twice the amount in the selected envelope. In this second scenario the amount in the other envelope would be $40. The probability of either of these scenarios would appear to be one half, since there is a 50% chance that the larger envelope was selected and a 50% chance that the smaller envelope was selected. The expected value calculation for how much money is in the other envelope would be the amount in the first scenario times the probability of the first scenario plus the amount in the second scenario times the probability of the second scenario, which is$10 × 1/2 + $40 × 1/2. The result of this calculation is that the expected value, i.e., average, of the amount of money in the other envelope is$25. Since this is greater than the amount in the selected envelope, it would appear to the person selecting the envelope's advantage to switch envelopes.

Imagining any other amount, e.g. $200 instead of$20, leads to the same conclusion. This means that even before you open your selected envelope you know that you will want to take the other envelope instead, because on average you will gain by the switch. This conclusion is obviously ludicrous.

### Proposed solutions

Many solutions have been proposed. Commonly one writer proposes a solution to the problem as stated, after which another writer shows that altering the problem slightly revives the paradox. Such sequences of discussions have produced a family of closely related formulations of the problem, resulting in a voluminous literature on the subject.

No proposed solution is widely accepted as definitive.[1] Despite this it is common for authors to claim that the solution to the problem is easy, even elementary.[2] However, when investigating these elementary solutions they often differ from one author to the next. Since 1987 new papers have been published every year.[3]

## Problem

Basic setup: You are given two indistinguishable envelopes, each of which contains a positive sum of money. One envelope contains twice as much as the other. You may pick one envelope and keep whatever amount it contains. You pick one envelope at random but before you open it you are given the chance to take the other envelope instead.[4]

The switching argument: Now suppose you reason as follows:

1. I denote by A the amount in my selected envelope.
2. The probability that A is the smaller amount is 1/2, and that it is the larger amount is also 1/2.
3. The other envelope may contain either 2A or A/2.
4. If A is the smaller amount, then the other envelope contains 2A.
5. If A is the larger amount, then 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:
${1 \over 2} (2A) + {1 \over 2} \left({A \over 2}\right) = {5 \over 4}A$
8. This is greater than A, so I gain on average by swapping.
9. After the switch, I can denote that content by B and reason in exactly the same manner as above.
10. I will conclude that the most rational thing to do is to swap back again.
11. To be rational, I will thus end up swapping envelopes indefinitely.
12. As it seems more rational to open just any envelope than to swap indefinitely, we have a contradiction.

The puzzle: The puzzle is to find the flaw in the very compelling line of reasoning 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.

## Simple resolutions

A common way to resolve the paradox, both in popular literature and part of the academic literature, especially in philosophy, is to assume that the 'A' in step 7 is intended to be the expected value in envelope A and that we intended to write down a formula for the expected value in envelope B.

Step 7 states that the expected value in B = 1/2( 2A + A/2 )

It is pointed out that the 'A' in the first part of the formula is the expected value, given that envelope A contains less than envelope B, but the 'A', in the second part of the formula is the expected value in A, given that envelope A contains more than envelope B. The flaw in the argument is that same symbol is used with two different meanings in both parts of the same calculation but is assumed to have the same value in both cases.

A correct calculation of the would be:

Expected value in B = 1/2 ( Expected value in A (given A is larger than B) + Expected value in A (given A is smaller than B) )[5]

If we then take the sum in one envelope to be x and the sum in the other to be 2x the expected value calculations becomes:

Expected value in B = 1/2 (x + 2x)

which is equal to the expected sum in A.

In non-technical language, what goes wrong (see Necktie paradox) is that when imagining the scenario when Envelope A contains less than Envelope B, one's beliefs as to its value have to be revised (downwards) relatively to what they are a priori, without such additional information. Yet in the calculation which leads to the paradoxical result that Envelope B contains on average more than in Envelope A , the writer is behaving as if his beliefs as to what is in Envelope A are exactly the same when it is the larger amount, as when it is the smaller amount, as when no such information is given. Of course, the actual amount in the envelope is fixed and doesn't change if it is revealed which envelope has more. The point is that this amount, whatever it was, is unknown to him. It is his beliefs about the amount which could not be the same if he was given further information as to which envelope has more.

Line 7 should have been worked out more carefully as follows:

$E(B) = E(B\, | \,A < B) P(A < B) + E(B\, |\, A > B) P(A > B) = E(2A\, | \,A < B) {1 \over 2} + E( {1 \over 2}A \, | \,A > B) {1 \over 2} = E(A \,| \,A < B) + {1 \over 4} E(A \,|\, A >B)$

A will be larger when A is larger than B, than when it is smaller than B. So its average values (expectation values) in those two cases are different. And the average value of A is not the same as A itself, anyway. Two mistakes are being made: the writer forgot he was taking expectation values, and he forgot he was taking expectation values under two different conditions.

It would have been easier to compute E(B) directly. Denoting the lower of the two amounts by x, and taking it to be fixed (even if unknown) we find that

E(B) = ${1 \over 2} 2x + {1 \over 2} x = {3 \over 2}x$

We learn that 1.5x is the expected value of the amount in Envelope B. By the same calculation it is also the expected value of the amount in Envelope A. They are the same hence there is no reason to prefer one envelope to the other. This conclusion was, of course, obvious in advance; the point is that we identified the false step in the argument for switching by explaining exactly where the calculation being made there went off the rails.

We could also continue from the correct but difficult to interpret result of the development in line 7: $E(B) = E(A\, |\, A < B) + {1 \over 4} E(A \,|\, A >B) = x + {1 \over 4} 2 x = {3 \over 2}x$ so (of course) different routes to calculate the same thing all give the same answer.

Tsikogiannopoulos (2012)[6] presented a different way to do these calculations. Of course, it is by definition correct to assign equal probabilities to the events that the other envelope contains double or half that amount in envelope A. So the "switching argument" is correct up to step 6. Given that the player's envelope contains the amount A, the first game would be played with the amounts (A, 2A) and the second game with the amounts (A/2, A). Only one of them is actually played but we don't know which one, and we don't know the amounts in the two games: they are different, too! These two games need to be treated differently. If the player wants to compute his/her expected return (profit or loss) in case of exchange, he/she should weigh the return derived from each game by the average amount in the two envelopes in that particular game. So the formula of the expected return in case of exchange is, seen as a proportion of the total amount in the two envelopes, is:

$E=\frac{1}{2}\cdot\frac{+A}{3A/2}+\frac{1}{2}\cdot\frac{-A/2}{3A/4}=0$

This result means yet again (as we knew in advance, by symmetry) that the player has to expect neither profit nor loss by exchanging his/her envelope.

### Nalebuff asymmetric variant

As pointed out by many authors[7][6] the mechanism by which the amounts of the two envelopes are determined is crucial for the decision of the player to switch or not his/her envelope. Suppose that the amounts in the two envelopes A and B were not determined by first fixing contents of two envelopes E1 and E2, and then naming them A and B at random (for instance, by the toss of a fair coin; Nickerson and Falk, 2006). Instead, we start right at the beginning by putting some amount in Envelope A, and then fill B in a way which depends both on chance (the toss of a coin) and on what we put in A. Suppose that first of all the amount a in Envelope A is fixed in some way or other, and then the amount in Envelope B is fixed, dependent on what is already in A, according to the outcome of a fair coin. Ιf the coin fell Heads then 2a is put in Envelope B, if the coin fell Tails then a/2 is put in Envelope B. If the player was aware of this mechanism, and knows that they hold Envelope A, but don't know the outcome of the coin toss, and doesn't know a, then the switching argument is correct and he/she is recommended to switch envelopes. This version of the problem was introduced by Nalebuff (1988) and is often called the Ali-Baba problem. Notice that there is no need to look in Envelope A in order to decide whether or not to switch.

Many more variants of the problem have been introduced. Nickerson and Falk (2006) systematically survey a total of 8.

## Bayesian resolutions

The simple resolution above assumed that the person who invented the argument for switching was trying to calculate the expectation value of the amount in Envelope A, thinking of the two amounts in the envelopes as fixed (x and 2x). The only uncertainty is which envelope has the smaller amount x. However many mathematicians and statisticians interpret the argument as an attempt to calculate the expected amount in Envelope B, given a real or hypothetical amount "A" in Envelope A. (A mathematician would moreover prefer to use the symbol a to stand for a possible value, reserving the symbol A for a random variable). One does not need to look in the envelope to see how much is in there, in order to do the calculation. If the result of the calculation is an advice to switch envelopes, whatever amount might be in there, then it would appear that one should switch anyway, without looking. In this case, at Steps 6, 7 and 8 of the reasoning, "A" is any fixed possible value of the amount of money in the first envelope.

This interpretation of the two envelopes problem appears in the first publications in which the paradox was introduced in its present day form, Gardner (1989) and Nalebuff (1989). It is common in the more mathematical literature on the problem. It also applies to the modification of the problem (which seems to have started with Nalebuff) in which the owner of Envelope A does actually look in his envelope before deciding whether or not to switch; though Nalebuff does also emphasize that there is no need to have the owner of Envelope A look in his envelope. If he imagines looking in it, and if for any amount which he can imagine being in there, he has an argument to switch, then he will decide to switch anyway. Finally, this interpretation was also the core of earlier versions of the two envelopes problem (Littlewood's, Schrödinger's, and Kraitchik's switching paradoxes); see the concluding section, on history of TEP.

This kind of interpretation is often called "Bayesian" because it assumes the writer is also incorporating a priori probability distribution of possible amounts of money in the two envelopes in the switching argument.

### Simple form of Bayesian resolution

The simple resolution depended on a particular interpretation of what the writer of the argument is trying to calculate: namely, it assumed he was after the (unconditional) expectation value of what's in Envelope B. In the mathematical literature on Two Envelopes Problem a different interpretation is more common, involving the conditional expectation value (conditional on what might be in Envelope A). To solve this and related interpretations or versions of the problem, most authors use the Bayesian interpretation of probability, which means that probability reasoning is not only applied to truly random events like the random pick of an envelope, but also to our knowledge (or lack of knowledge) about things which are fixed but unknown, like the two amounts originally placed in the two envelopes, before one is picked at random and called "Envelope A". Moreover, according to a long tradition going back at least to Laplace and his principle of insufficient reason one is supposed to give assign equal probabilities when one has no knowledge at all concerning the possible values of some quantity. Thus the fact that we are not told anything about how the envelopes are filled can already be converted into probability statements about these amounts. No information means that probabilities are equal.

In steps 6 and 7 of the switching argument, the writer imagines that that Envelope A contains a certain amount a, and then seems to believe that given that information, the other envelope would be equally likely to contain twice or half that amount. That assumption can only be correct, if prior to knowing what was in Envelope A, the writer would have considered the following two pairs of values for both envelopes equally likely: the amounts a/2 and a; and the amounts a and 2a. (This follows from Bayes' rule in odds form: posterior odds equal prior odds times likelihood ratio). But now we can apply the same reasoning, imagining not a but a/2 in Envelope A. And similarly, for 2a. And similarly, ad infinitum, repeatedly halving or repeatedly doubling as many times as you like. (Falk and Konold, 1992).

Suppose for the sake of argument, we start by imagining an amount 32 in Envelope A. In order that the reasoning in steps 6 and 7 is correct whatever amount happened to be in Envelope A, we apparently believe in advance that all the following ten amounts are all equally likely to be the smaller of the two amounts in the two envelopes: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 (equally likely powers of 2: Falk and Konold, 1992). But going to even larger or even smaller amounts, the "equally likely" assumption starts to appear a bit unreasonable. Suppose we stop, just with these ten equally likely possibilities for the smaller amount in the two envelopes. In that case, the reasoning in steps 6 and 7 was entirely correct if envelope A happened to contain any of the amounts 2, 4, ... 512: switching envelopes would give an expected (average) gain of 25%. If envelope A happened to contain the amount 1, then the expected gain is actually 100%. But if it happened to contain the amount 1024, a massive loss of 50% (of a rather large amount) would have been incurred. That only happens once in twenty times, but it is exactly enough to balance the expected gains in the other 19 out of 20 times.

Alternatively we do go on ad infinitum but now we are working with a quite ludicrous assumption, implying for instance, that it is infinitely more likely for the amount in envelope A to be smaller than 1, and infinitely more likely to be larger than 1024, than between those two values. This is a so-called improper prior distribution: probability calculus breaks down; expectation values are not even defined; see Falk and Konold and (1982).

Many authors have also pointed out that if a maximum sum that can be put in the envelope with the smaller amount exists, then it is very easy to see that Step 6 breaks down, since if the player holds more than the maximum sum that can be put into the "smaller" envelope they must hold the envelope containing the larger sum, and are thus certain to lose by switching. This may not occur often, but when it does, the heavy loss the player incurs means that, on average, there is no advantage in switching. Some writers consider that this resolves all practical cases of the problem.[8]

But the problem can also be resolved mathematically without assuming a maximum amount. Nalebuff (1989), Christensen and Utts (1992), Falk and Konold (1992), Blachman, Christensen and Utts (1996),[9] Nickerson and Falk (2006), pointed out that if the amounts of money in the two envelopes have any proper probability distribution representing the player's prior beliefs about the amounts of money in the two envelopes, then it is impossible that whatever the amount A=a in the first envelope might be, it would be equally likely, according to these prior beliefs, that the second contains a/2 or 2a. Thus step 6 of the argument, which leads to always switching, is a non-sequitur, also when there is no maximum to the amounts in the envelopes.

### Introduction to further developments in connection with Bayesian probability theory

The first two resolutions discussed above (the "simple resolution" and the "Bayesian resolution") correspond to two possible interpretations of what is going on in step 6 of the argument. They both assume that step 6 indeed is "the bad step". But the description in step 6 is ambiguous. Is the author after the unconditional (overall) expectation value of what is in envelope B (perhaps - conditional on the smaller amount, x), or is he after the conditional expectation of what is in envelope B, given any possible amount a which might be in envelope A? Thus, there are two main interpretations of the intention of the composer of the paradoxical argument for switching, and two main resolutions.

A large literature has developed concerning variants of the problem.[10][11] The standard assumption about the way the envelopes are set up is that a sum of money is in one envelope, and twice that sum is in another envelope. One of the two envelopes is randomly given to the player (envelope A). The originally proposed problem does not make clear exactly how the smaller of the two sums is determined, what values it could possibly take and, in particular, whether there is a minimum or a maximum sum it might contain.[12][13] However, if we are using the Bayesian interpretation of probability, then we start by expressing our prior beliefs as to the smaller amount in the two envelopes through a probability distribution. Lack of knowledge can also be expressed in terms of probability.

A first variant within the Bayesian version is to come up with a proper prior probability distribution of the smaller amount of money in the two envelopes, such that when Step 6 is performed properly, the advice is still to prefer Envelope B, whatever might be in Envelope A. So though the specific calculation performed in step 6 was incorrect (there is no proper prior distribution such that, given what is in the first envelope A, the other envelope is always equally likely to be larger or smaller) a correct calculation, depending on what prior we are using, does lead to the result $E(B | A = a) > a$ for all possible values of a.[14]

In these cases it can be shown that the expected sum in both envelopes is infinite. There is no gain, on average, in swapping.

### Second mathematical variant

Though Bayesian probability theory can resolve the first mathematical interpretation of the paradox above, it turns out that examples can be found of proper probability distributions, such that the expected value of the amount in the second envelope given that in the first does exceed the amount in the first, whatever it might be. The first such example was already given by Nalebuff (1989). See also Christensen and Utts (1992)[15][16][17][18]

Denote again the amount of money in the first envelope by A and that in the second by B. We think of these as random. Let X be the smaller of the two amounts and Y=2X be the larger. Notice that once we have fixed a probability distribution for X then the joint probability distribution of A,B is fixed, since A,B = X,Y or Y,X each with probability 1/2, independently of X,Y.

The bad step 6 in the "always switching" argument led us to the finding E(B|A=a)>a for all a, and hence to the recommendation to switch, whether or not we know a. Now, it turns out that one can quite easily invent proper probability distributions for X, the smaller of the two amounts of money, such that this bad conclusion is still true. One example is analysed in more detail, in a moment.

As mentioned before, it cannot be true that whatever a, given A=a, B is equally likely to be a/2 or 2a, but it can be true that whatever a, given A=a, B is larger in expected value than a.

Suppose for example (Broome, 1995)[19] that the envelope with the smaller amount actually contains 2n dollars with probability 2n/3n+1 where n = 0, 1, 2,… These probabilities sum to 1, hence the distribution is a proper prior (for subjectivists) and a completely decent probability law also for frequentists.

Imagine what might be in the first envelope. A sensible strategy would certainly be to swap when the first envelope contains 1, as the other must then contain 2. Suppose on the other hand the first envelope contains 2. In that case there are two possibilities: the envelope pair in front of us is either {1, 2} or {2, 4}. All other pairs are impossible. The conditional probability that we are dealing with the {1, 2} pair, given that the first envelope contains 2, is

\begin{align} P(\{1,2\} \mid 2) &= \frac{P(\{1,2\})/2}{P(\{1,2\})/2+P(\{2,4\})/2} \\ &= \frac{P(\{1,2\})}{P(\{1,2\})+P(\{2,4\})} \\ &= \frac{1/3}{1/3 + 2/9} = 3/5, \end{align}

and consequently the probability it's the {2, 4} pair is 2/5, since these are the only two possibilities. In this derivation, $P(\{1,2\})/2$ is the probability that the envelope pair is the pair 1 and 2, and Envelope A happens to contain 2; $P(\{2,4\})/2$ is the probability that the envelope pair is the pair 2 and 4, and (again) Envelope A happens to contain 2. Those are the only two ways that Envelope A can end up containing the amount 2.

It turns out that these proportions hold in general unless the first envelope contains 1. Denote by a the amount we imagine finding in Envelope A, if we were to open that envelope, and suppose that a = 2n for some n ≥ 1. In that case the other envelope contains a/2 with probability 3/5 and 2a with probability 2/5.

So either the first envelope contains 1, in which case the conditional expected amount in the other envelope is 2, or the first envelope contains a > 1, and though the second envelope is more likely to be smaller than larger, its conditionally expected amount is larger: the conditionally expected amount in Envelope B is

$\frac{3}{5} \frac{a}{2} + \frac{2}{5} 2a = \frac{11}{10}a$

which is more than a. This means that the player who looks in Envelope A would decide to switch whatever he saw there. Hence there is no need to look in Envelope A to make that decision.

This conclusion is just as clearly wrong as it was in the preceding interpretations of the Two Envelopes Problem. But now the flaws noted above do not apply; the a in the expected value calculation is a constant and the conditional probabilities in the formula are obtained from a specified and proper prior distribution.

### Proposed resolutions

Most writers think that the new paradox can be defused.[20] Suppose $E(B|A=a)>a$ for all a. As remarked before, this is possible for some probability distributions of X (the smaller amount of money in the two envelopes). Averaging over a, it follows either that $E(B)>E(A)$, or alternatively that $E(B)=E(A)=\infty$. But A and B have the same probability distribution, and hence the same expectation value, by symmetry (each envelope is equally likely to be the smaller of the two). Thus both have infinite expectation values, and hence so must X too.

Thus if we switch for the second envelope because its conditional expected value is larger than what actually is in the first, whatever that might be, we are exchanging an unknown amount of money whose expectation value is infinite for another unknown amount of money with the same distribution and the same infinite expected value. The average amount of money in both envelopes is infinite. Exchanging one for the other simply exchanges an average of infinity with an average of infinity.

Probability theory therefore tells us why and when the paradox can occur and explains to us where the sequence of apparently logical steps breaks down. In this situation, Steps 6 and Steps 7 of the standard Two Envelopes argument can be replaced by correct calculations of the conditional probabilities that the other envelope contains half or twice what's in A, and a correct calculation of the conditional expectation of what's in B given what's in A. Indeed, that conditional expected value is larger than what's in A. But because the unconditional expected amount in A is infinite, this does not provide a reason to switch, because it does not guarantee that on average you'll be better off after switching. One only has this mathematical guarantee in the situation that the unconditional expectation value of what's in A is finite. But then the reason for switching without looking in the envelope, $E(B|A=a)>a$ for all a, simply cannot arise.

Many economists prefer to argue that in a real-life situation, the expectation of the amount of money in an envelope cannot be infinity, for instance, because the total amount of money in the world is bounded; therefore any probability distribution describing the real world would have to assign probability 0 to the amount being larger than the total amount of money on the world. Therefore the expectation of the amount of money under this distribution cannot be infinity. The resolution of the second paradox, for such writers, is that the postulated probability distributions cannot arise in a real-life situation. These are similar arguments as used to explain the St. Petersburg Paradox.

### Foundations of mathematical economics

In mathematical economics and the theory of utility, which explains economic behaviour in terms of expected utility, there remains a problem to be resolved.[21] In the real world we presumably would not indefinitely exchange one envelope for the other (and probability theory, as just discussed, explains quite well why calculations of conditional expectations might mislead us). Yet the expected utility based theory of economic behaviour assumes that people do (or should) make economic decisions by maximizing expected utility, conditional on present knowledge. If the utility function is unbounded above, then the theory can still predict infinite switching.

Fortunately for mathematical economics and the theory of utility, it is generally agreed that as an amount of money increases, its utility to the owner increases less and less, and ultimately there is a finite upper bound to the utility of all possible amounts of money. We can pretend that the amount of money in the whole world is as large as we like, yet the utility that the owner of all that money experiences, while rising further and further, will never rise beyond a certain point no matter how much is in his possession. For decision theory and utility theory, the two envelope paradox illustrates that unbounded utility does not exist in the real world, so fortunately there is no need to build a decision theory that allows unbounded utility, let alone utility of infinite expectation.[citation needed]

### Controversy among philosophers

As mentioned above, any distribution producing this variant of the paradox must have an infinite mean. So before the player opens an envelope the expected gain from switching is "∞ − ∞", which is not defined. In the words of David Chalmers this is "just another example of a familiar phenomenon, the strange behaviour of infinity".[22] Chalmers suggests that decision theory generally breaks down when confronted with games having a diverging expectation, and compares it with the situation generated by the classical St. Petersburg paradox.

However, Clark and Shackel argue that this blaming it all on "the strange behaviour of infinity" does not resolve the paradox at all; neither in the single case nor the averaged case. They provide a simple example of a pair of random variables both having infinite mean but where it is clearly sensible to prefer one to the other, both conditionally and on average.[23] They argue that decision theory should be extended so as to allow infinite expectation values in some situations.

## Smullyan's non-probabilistic variant

The logician Raymond Smullyan questioned if the paradox has anything to do with probabilities at all.[24] He did this by expressing the problem in a way that does not involve probabilities. The following plainly logical arguments lead to conflicting conclusions:

1. Let the amount in the envelope chosen by the player be A. By swapping, the player may gain A or lose A/2. So the potential gain is strictly greater than the potential loss.
2. Let the amounts in the envelopes be X and 2X. Now by swapping, the player may gain X or lose X. So the potential gain is equal to the potential loss.

### Proposed resolutions

A number of solutions have been put forward. Careful analyses have been made by some logicians. Though solutions differ, they all pinpoint semantic issues concerned with counterfactual reasoning. We want to compare the amount that we would gain by switching if we would gain by switching, with the amount we would lose by switching if we would indeed lose by switching. However, we cannot both gain and lose by switching at the same time. We are asked to compare two incompatible situations. Only one of them can factually occur, the other is a counterfactual situation—somehow imaginary. To compare them at all, we must somehow "align" the two situations, providing some definite points in common.

James Chase (2002) argues that the second argument is correct because it does correspond to the way to align two situations (one in which we gain, the other in which we lose), which is preferably indicated by the problem description.[25] Also Bernard Katz and Doris Olin (2007) argue this point of view.[26] In the second argument, we consider the amounts of money in the two envelopes as being fixed; what varies is which one is first given to the player. Because that was an arbitrary and physical choice, the counterfactual world in which the player, counterfactually, got the other envelope to the one he was actually (factually) given is a highly meaningful counterfactual world and hence the comparison between gains and losses in the two worlds is meaningful. This comparison is uniquely indicated by the problem description, in which two amounts of money are put in the two envelopes first, and only after that is one chosen arbitrarily and given to the player. In the first argument, however, we consider the amount of money in the envelope first given to the player as fixed and consider the situations where the second envelope contains either half or twice that amount. This would only be a reasonable counterfactual world if in reality the envelopes had been filled as follows: first, some amount of money is placed in the specific envelope that will be given to the player; and secondly, by some arbitrary process, the other envelope is filled (arbitrarily or randomly) either with double or with half of that amount of money.

Byeong-Uk Yi (2009), on the other hand, argues that comparing the amount you would gain if you would gain by switching with the amount you would lose if you would lose by switching is a meaningless exercise from the outset.[27] According to his analysis, all three implications (switch, indifferent, do not switch) are incorrect. He analyses Smullyan's arguments in detail, showing that intermediate steps are being taken, and pinpointing exactly where an incorrect inference is made according to his formalization of counterfactual inference. An important difference with Chase's analysis is that he does not take account of the part of the story where we are told that the envelope called Envelope A is decided completely at random. Thus, Chase puts probability back into the problem description in order to conclude that arguments 1 and 3 are incorrect, argument 2 is correct, while Yi keeps "two envelope problem without probability" completely free of probability, and comes to the conclusion that there are no reasons to prefer any action. This corresponds to the view of Albers et al., that without probability ingredient, there is no way to argue that one action is better than another, anyway.

In perhaps the most recent paper on the subject, Bliss argues that the source of the paradox is that when one mistakenly believes in the possibility of a larger payoff that does not, in actuality, exist, one is mistaken by a larger margin than when one believes in the possibility of a smaller payoff that does not actually exist.[28] If, for example, the envelopes contained $5.00 and$10.00 respectively, a player who opened the $10.00 envelope would expect the possibility of a$20.00 payout that simply does not exist. Were that player to open the $5.00 envelope instead, he would believe in the possibility of a$2.50 payout, which constitutes a smaller deviation from the true value.

Albers, Kooi, and Schaafsma (2005) consider that without adding probability (or other) ingredients to the problem, Smullyan's arguments do not give any reason to swap or not to swap, in any case. Thus, there is no paradox. This dismissive attitude is common among writers from probability and economics: Smullyan's paradox arises precisely because he takes no account whatever of probability or utility.

## Extensions to the problem

Since the two envelopes problem became popular, many authors have studied the problem in depth in the situation in which the player has a prior probability distribution of the values in the two envelopes, and does look in Envelope A. One of the most recent such publications is by McDonnell and Douglas (2009), who also consider some further generalizations.[29]

If a priori we know that the amount in the smaller envelope is a whole number of some currency units, then the problem is determined, as far as probability theory is concerned, by the probability mass function $p(x)$ describing our prior beliefs that the smaller amount is any number x = 1,2, ... ; the summation over all values of x being equal to 1. It follows that given the amount a in Envelope A, the amount in Envelope B is certainly 2a if a is an odd number. However, if a is even, then the amount in Envelope B is 2a with probability $p(a)/(p(a/2)+p(a))$, and a/2 with probability $p(a/2)/(p(a/2)+p(a))$. If one would like to switch envelopes if the expectation value of what is in the other is larger than what we have in ours, then a simple calculation shows that one should switch if $p(a/2) < 2p(a)$, keep to Envelope A if $p(a/2) > 2p(a)$.

If on the other hand the smaller amount of money can vary continuously, and we represent our prior beliefs about it with a probability density $f(x)$, thus a function that integrates to one when we integrate over x running from zero to infinity, then given the amount a in Envelope A, the other envelope contains 2a with probability $2f(a)/(f(a/2)+2f(a))$, and a/2 with probability $f(a/2)/(f(a/2)+2f(a))$. If again we decide to switch or not according to the expectation value of what's in the other envelope, the criterion for switching now becomes $f(a/2) < 4f(a)$.

The difference between the results for discrete and continuous variables may surprise many readers. Speaking intuitively, this is explained as follows. Let h be a small quantity and imagine that the amount of money we see when we look in Envelope A is rounded off in such a way that differences smaller than h are not noticeable, even though actually it varies continuously. The probability that the smaller amount of money is in an interval around a of length h, and Envelope A contains the smaller amount is approximately $f(a) \cdot h \cdot (1/2)$. The probability that the larger amount of money is in an interval around a of length h corresponds to the smaller amount being in an interval of length h/2 around a/2. Hence the probability that the larger amount of money is in a small interval around a of length h and Envelope A contains the larger amount is approximately $f(a/2) \cdot (h/2) \cdot (1/2)$. Thus, given Envelope A contains an amount about equal to a, the probability it is the smaller of the two is roughly $f(a) \cdot h \cdot (1/2)/(f(a) \cdot h \cdot (1/2)+f(a/2) \cdot (h/2) \cdot (1/2)) = 2f(a)/(2f(a)+f(a/2))$.

If the player only wants to end up with the larger amount of money, and does not care about expected amounts, then in the discrete case he should switch if a is an odd number, or if a is even and $p(a/2) < p(a)$. In the continuous case he should switch if $f(a/2) < 2f(a)$.

Some authors prefer to think of probability in a frequentist sense. If the player knows the probability distribution used by the organizer to determine the smaller of the two values, then the analysis would proceed just as in the case when p or f represents subjective prior beliefs. However, what if we take a frequentist point of view, but the player does not know what probability distribution is used by the organiser to fix the amounts of money in any one instance? Thinking of the arranger of the game and the player as two parties in a two person game, puts the problem into the range of game theory. The arranger's strategy consists of a choice of a probability distribution of x, the smaller of the two amounts. Allowing the player also to use randomness in making his decision, his strategy is determined by his choosing a probability of switching $q(a)$ for each possible amount of money a he might see in Envelope A. In this section we so far only discussed fixed strategies, that is strategies for which q only takes the values 0 and 1, and we saw that the player is fine with a fixed strategy, if he knows the strategy of the organizer. In the next section we will see that randomized strategies can be useful when the organizer's strategy is not known.

## Randomized solutions

Suppose as in the previous section that the player is allowed to look in the first envelope before deciding whether to switch or to stay. We'll think of the contents of the two envelopes as being two positive numbers, not necessarily two amounts of money. The player is allowed either to keep the number in Envelope A, or to switch and take the number in Envelope B. We'll drop the assumption that one number is exactly twice the other, we'll just suppose that they are different and positive. On the other hand, instead of trying to maximize expectation values, we'll just try to maximize the chance that we end up with the larger number.

In this section we ask the question, is it possible for the player to make his choice in such a way that he goes home with the larger number with probability strictly greater than half, however the organizer has filled the two envelopes?

We are given no information at all about the two numbers in the two envelopes, except that they are different, and strictly greater than zero. The numbers were written down on slips of paper by the organiser, put into the two envelopes. The envelopes were then shuffled, the player picks one, calls it Envelope A, and opens it.

We are not told any joint probability distribution of the two numbers. We are not asking for a subjectivist solution. We must think of the two numbers in the envelopes as chosen by the arranger of the game according to some possibly random procedure, completely unknown to us, and fixed. Think of each envelope as simply containing a positive number and such that the two numbers are not the same. The job of the player is to end up with the envelope with the larger number. This variant of the problem, as well as its solution, is attributed by McDonnell and Abbott, and by earlier authors, to information theorist Thomas M. Cover.[30]

Counter-intuitive though it might seem, there is a way that the player can decide whether to switch or to stay so that he has a larger chance than 1/2 of finishing with the bigger number, however the two numbers are chosen by the arranger of the game. However, it is only possible with a so-called randomized algorithm: the player must be able to generate his own random numbers. Suppose he is able to produce a random number, let's call it Z, such that the probability that Z is larger than any particular quantity z is exp(-z). Note that exp(-z) starts off equal to 1 at z=0 and decreases strictly and continuously as z increases, tending to zero as z tends to infinity. So the chance is 0 that Z is exactly equal to any particular number, and there is a positive probability that Z lies between any two particular different numbers. The player compares his Z with the number in Envelope A. If Z is smaller he keeps the envelope. If Z is larger he switches to the other envelope.

Think of the two numbers in the envelopes as fixed (though of course unknown to the player). Think of the player's random Z as a probe with which he decides whether the number in Envelope A is small or large. If it is small compared to Z he switches, if it is large compared to Z he stays.

If both numbers are smaller than the player's Z, his strategy does not help him. He ends up with the Envelope B, which is equally likely to be the larger or the smaller of the two. If both numbers are larger than Z his strategy does not help him either, he ends up with the first Envelope A, which again is equally likely to be the larger or the smaller of the two. However if Z happens to be in between the two numbers, then his strategy leads him correctly to keep Envelope A if its contents are larger than those of B, but to switch to Envelope B if A has smaller contents than B. Altogether, this means that he ends up with the envelope with the larger number with probability strictly larger than 1/2. To be precise, the probability that he ends with the "winning envelope" is 1/2 + P(Z falls between the two numbers)/2.

In practice, the number Z we have described could be determined to the necessary degree of accuracy as follows. Toss a fair coin many times, and convert the sequence of heads and tails into the binary representation of a number U between 0 and 1: for instance, HTHHTH... becomes the binary representation of u=0.101101.. . In this way, we generate a random number U, uniformly distributed between 0 and 1. Then define Z = − ln (U) where "ln" stands for natural logarithm, i.e., logarithm to base e. Note that we just need to toss the coin long enough to verify whether Z is smaller or larger than the number a in the first envelope—we do not need to go on for ever. We only need to toss the coin a finite (though random) number of times: at some point we can be sure that the outcomes of further coin tosses would not change the outcome.

The particular probability law (the so-called standard exponential distribution) used to generate the random number Z in this problem is not crucial. Any probability distribution over the positive real numbers that assigns positive probability to any interval of positive length does the job.

This problem can be considered from the point of view of game theory, where we make the game a two-person zero-sum game with outcomes win or lose, depending on whether the player ends up with the higher or lower amount of money. The organiser chooses the joint distribution of the amounts of money in both envelopes, and the player chooses the distribution of Z. The game does not have a "solution" (or saddle point) in the sense of game theory. This is an infinite game and von Neumann's minimax theorem does not apply.[31]

## History of the paradox

The envelope paradox dates back at least to 1953, when Belgian mathematician Maurice Kraitchik proposed a puzzle in his book Recreational Mathematics concerning two equally rich men who meet and compare their beautiful neckties, presents from their wives, wondering which tie actually cost more money. He also introduces a variant in which the two men compare the contents of their purses. He assumes that each purse is equally likely to contain 1 up to some large number x of pennies, the total number of pennies minted to date. The men do not look in their purses but each reasons that they should switch. He does not explain what is the error in their reasoning. It is not clear whether the puzzle already appeared in an earlier 1942 edition of his book. It is also mentioned in a 1953 book on elementary mathematics and mathematical puzzles by the mathematician John Edensor Littlewood, who credited it to the physicist Erwin Schroedinger, where it concerns a pack of cards, each card has two numbers written on them, the player gets to see a random side of a random card, and the question is whether one should turn over the card. Littlewood's pack of cards is infinitely large and his paradox is a paradox of improper prior distributions.

Martin Gardner popularized Kraitchik's puzzle in his 1982 book Aha! Gotcha, in the form of a wallet game:

Two people, equally rich, meet to compare the contents of their wallets. Each is ignorant of the contents of the two wallets. The game is as follows: whoever has the least money receives the contents of the wallet of the other (in the case where the amounts are equal, nothing happens). One of the two men can reason: "I have the amount A in my wallet. That's the maximum that I could lose. If I win (probability 0.5), the amount that I'll have in my possession at the end of the game will be more than 2A. Therefore the game is favourable to me." The other man can reason in exactly the same way. In fact, by symmetry, the game is fair. Where is the mistake in the reasoning of each man?

Gardner confessed that though, like Kraitchik, he could give a sound analysis leading to the right answer (there is no point in switching), he could not clearly put his finger on what was wrong with the reasoning for switching, and Kraitchik did not give any help in this direction, either.

In 1988 and 1989, Barry Nalebuff presented two different two-envelope problems, each with one envelope containing twice what's in the other, and each with computation of the expectation value 5A/4. The first paper just presents the two problems, the second paper discusses many solutions to both of them. The second of his two problems nowadays the most common, and is presented in this article. According to this version, the two envelopes are filled first, then one is chosen at random and called Envelope A. Martin Gardner independently mentioned this same version in his 1989 book Penrose Tiles to Trapdoor Ciphers and the Return of Dr Matrix. Barry Nalebuff's asymmetric variant, often known as the Ali Baba problem, has one envelope filled first, called Envelope A, and given to Ali. Then a fair coin is tossed to decide whether Envelope B should contain half or twice that amount, and only then given to Baba.

## Notes and references

1. ^ Markosian, Ned (2011). "A Simple Solution to the Two Envelope Problem". Logos & Episteme II (3): 347–57.
2. ^ McDonnell, Mark D; Grant, Alex J; Land, Ingmar; Vellambi, Badri N; Abbott, Derek; Lever, Ken (2011). "Gain from the two-envelope problem via information asymmetry: on the suboptimality of randomized switching". Proceedings of the Royal Society A. doi:10.1098/rspa.2010.0541.
3. ^ A complete list of published and unpublished sources in chronological order can be found in the talk page.
4. ^ Falk, Ruma (2008). "The Unrelenting Exchange Paradox". Teaching Statistics 30 (3): 86–88. doi:10.1111/j.1467-9639.2008.00318.x.
5. ^ Schwitzgebe, Eric; Dever, Josh (2008), "The Two Envelope Paradox and Using Variables Within the Expectation Formula", Sorites: 135–140
6. ^ a b Tsikogiannopoulos, Panagiotis (2012). [English translation at http://arxiv.org/pdf/1411.2823.pdf "Παραλλαγές του προβλήματος της ανταλλαγής φακέλων" [Variations on the Two Envelopes Problem]]. Mathematical Review (in Greek) (Hellenic Mathematical Society).
7. ^ Priest, Graham; Restall, Greg (2007), "Envelopes and Indiference", Dialogues, Logics and Other Strange Things (College Publications): 135–140
8. ^ Nalebuff, Barry, "Puzzles: The Other Person’s Envelope is Always Greener", Journal of Economic Perspectives 3 (1): 171–81, doi:10.1257/jep.3.1.171.
9. ^ Blachman, NM; Christensen, R; Utts, J (1996). The American Statistician 50 (1): 98–99.
10. ^ Albers, Casper (March 2003), "2. Trying to resolve the two-envelope problem", Distributional Inference: The Limits of Reason (thesis).
11. ^ Albers, Casper J; Kooi, Barteld P; Schaafsma, Willem (2005), "Trying to resolve the two-envelope problem", Synthese 145 (1): 91.
12. ^ Falk, Ruma; Nickerson, Raymond, "An inside look at the two envelopes paradox", Teaching Statistics 31 (2): 39–41, doi:10.1111/j.1467-9639.2009.00346.x.
13. ^ Chen, Jeff, The Puzzle of the Two-Envelope Puzzle—a Logical Approach (online ed.), p. 274.
14. ^ Broome, John, "The Two-envelope Paradox", Analysis 55 (1): 6–11, doi:10.1093/analys/55.1.6.
15. ^ Christensen, R; Utts, J (1992), The American Statistician 46 (4): 274–76.
16. ^ Binder, DA (1993), "Letter to editor and response", The American Statistician 47 (2): 160.
17. ^ Ross (1994), "Letter to editor and response", The American Statistician 48 (3): 267.
18. ^ Blachman, NM; Christensen, R; Utts, JM (1996), "Letter with corrections to the original article", The American Statistician 50 (1): 98–99.
19. ^ Broome, John (1995). "The Two-envelope Paradox". Analysis 55 (1): 6–11. doi:10.1093/analys/55.1.6. A famous example of a proper probability distribution of the amounts of money in the two envelopes, for which $E(B|A=a)>a$ for all a.
20. ^ Binder, D. A. (1993). The American Statistician 47 (2): 160. (letters to the editor, comment on Christensen and Utts (1992)
21. ^ Fallis, D. (2009). "Taking the Two Envelope Paradox to the Limit". Southwest Philosophy Review 25 (2).
22. ^ Chalmers, David J. (2002). "The St. Petersburg Two-Envelope Paradox". Analysis 62 (2): 155–157. doi:10.1093/analys/62.2.155.
23. ^ Clark, M.; Shackel, N. (2000). "The Two-Envelope Paradox". Mind 109 (435): 415–442. doi:10.1093/mind/109.435.415.
24. ^ Smullyan, Raymond (1992). Satan, Cantor, and infinity and other mind-boggling puzzles. Alfred A. Knopf. pp. 189–192. ISBN 0-679-40688-3.
25. ^ Chase, James (2002). "The Non-Probabilistic Two Envelope Paradox". Analysis 62 (2): 157–160. doi:10.1093/analys/62.2.157.
26. ^ Katz, Bernard; Olin, Doris (2007). "A tale of two envelopes". Mind 116 (464): 903–926. doi:10.1093/mind/fzm903.
27. ^ Byeong-Uk Yi (2009). "The Two-envelope Paradox With No Probability".
28. ^ Bliss (2012). "A Concise Resolution to the Two Envelope Paradox".
29. ^ McDonnell, M. D.; Abott, D. (2009). "Randomized switching in the two-envelope problem". Proceedings of the Royal Society A 465 (2111): 3309–3322. doi:10.1098/rspa.2009.0312.
30. ^ Cover, Thomas M (1987). "Pick the largest number". In Cover, T; Gopinath, B. Open Problems in Communication and Computation. Springer-Verlag.
31. ^ Martinian, Emin, The Two Envelope Problem, archived from the original on 2007-11-14.