This problem is at least half a century old, and most likely a lot older. It can be found in a 1953 book by Maurice Kraitchik which is the oldest citation in Wikipedia.
Someone places money into one of two identical envelopes and double the money into the second. We select one of the two envelopes without knowing if we have the first or the second one. We open it. Should we keep that money or return it and opt for the other envelope?
We assume that the value in the first envelope is a rational number. So, we cannot conclude with certainty which envelope we have opened. If we selected from integer numbers, we would know the envelope in the case of an even value.
The naive analysis goes like this:
Let X be the amount we have. Since we have chosen the envelopes at random, the other envelope contains X/2 and 2X with the same probability. So, our expectation after switching is
\frac{X/2 + 2 X}{2} = \frac{5}{4} XSwitching sounds like a winning strategy. It gets more striking if we consider switching before even opening the envelope. Switching back and forth drives the expected value to infinity. This is clearly nonsense.
This paradox is a confirmation of my principle:
To analyze a probabilistic problem, we need an experiment that we could, at least hypothetically, implement in a computer. Equivalently, we need a probability space to work with.
The two envelopes problem does not satisfy this principle. The reason is that it is impossible to select a rational number at random from the set of all rational numbers. You cannot even select an integer evenly from all the integers. We need a probability distribution for that. Think of how you would test the switching strategy on a computer. You will have to tell the machine how to select a number. It can select a number with equal probability from all the numbers it can represent. But it cannot do so from all, infinitely many numbers.
Now that we know that the original problem makes no sense, we can start to analyze the problem by assuming an a priori distribution for the value M in the first envelope. By doing so, we get a bunch of very interesting questions. (By the way, it is always easy to create questions in mathematics. Only a few questions have nice answers, however.)
First, we fix the envelopes simply. So, one contains 100€, say, and the other 200€. The experiment consists of selecting one envelope with equal chance. You will already find that the naive analysis above is wrong. If you select the 100€, so X=100, the other envelope has a chance of 1 to contain 2X. If you select the 200€, so X=200, the other has a chance of 0 to contain 2X. On average, the chance is 1/2 for 2X. We simply get X as expected. I.e., changing makes no progress. The probabilities simply depend on X.
Let us continue by selecting M evenly from 1 to n (and putting 2M into the other envelope). We will keep the money only if X>n. For n which is a multiple of 4, we have the following cases:
- M <= n/2 : We will switch no matter if X=M or X=2M. Thus, the average outcome is 3/2 M.
- M > n/2 : We get 2M in every case.
It is an exercise to compute that our average result is
E = \frac{15n+14}{16}This is a blog about Euler Math Toolbox too. So let us simulate the strategy in EMT. In this case, a loop would be a good idea, maybe written in C or Python. However, it is also possible to do this elegantly with the matrix language
>n=10; N=1000000; >M=intrandom(N,n); // select a number between 1 and n >sel=intrandom(N,2); // select 1 or 2 envelope >X1=M*sel; X2=M*(3-sel); // X1 is in the selected, X2 in the other >sum((X1>n)*X1+(X1<=n)*X2)/N // X1 for X1>n, X2 else 10.253055 >(15*n+14)/16 // expected outcome 10.25
We could also try a distribution on the positive real numbers for M. To reflect the experiment above, we could select M (the smaller envelope), randomly between 0 and 1. We switch below 1, and keep above 1.
>N=10000000; >M=random(N); >sel=intrandom(N,2); >X1=M*sel; X2=M*(3-sel); >mean((X1>1)*X1+(X1<=1)*X2) 0.937723633608 >15/16 0.9375
The expected value without ever switching is clearly
\frac12 \left( \int_0^1 x \,dx + 2 \int_0^1 \, dx \right) = \frac34
The first integral is the result whenever the smaller envelope is picked, and the second the result for the larger. If we switch whenever the envelope is less than 1, we get the following
\frac12 \left( \int_0^1 2x \,dx + \int_0^{1/2} x \,dx + \int_{1/2}^1 2x \,dx \right) =\frac{15}{16}The first integral is for picking the lower envelope, the other two for picking the higher envelope. In general, a switching strategy with density w(x) has the outcome
\int_0^1 2x w(x) \,dx + \int_0^1 x (1-w(x)) \,dx = \frac12 + \int_0^1 x w(x)
in case the lower envelope is selected, and
\int_0^1 x w(2x) \,dx + \int_0^1 2x (1-w(2x)) \,dx = 1 - \int_0^1 x w(2x) \,dx
in case the bigger envelope is selected. The average turns out to be
\frac34 + \frac12 \int_0^1 x (w(x)-w(2x)) \,dx.
It is not immediately obvious, why we have to select w(x)=1 between 0 and 1 and zero elsewhere to maximize this integral. But that choice makes w(x)-w(2x) minimal on [0,1/2] and maximal on [1/2,1].
Another typical candidate is the exponential distribution. We decide ourselves to keep a value greater than some a>0.
In this case, we switch for all M<a/2 and M>a, getting 3/2 M on average. In half of the cases between a/2 and a, we get 2 M. In the other half we still get 3/2 M. Thus
E = \frac{3}{2} + \frac{1}{2} \int_{a/2}^a x e^{-x} \,dxThe best choice is a = 4 ln(2) with
E \sim 1.68
We can simulate that too.
>n=10; N=1000000; >M=randexponential(N); // select a number between 1 and n >sel=intrandom(N,2); // select 1 or 2 envelope >X1=M*sel; X2=M*(3-sel); // X1 is in the selected, X2 in the other >a=4*ln(2); sum((X1>a)*X1+(X1<=a)*X2)/N // X1 for X1>n, X2 else 1.68097393969
Note that switching all the time or never both expect E=3/2.
You might ask if there is a distribution for M which ensures that it does not matter to look inside the first envelope. But that is not the case. Such a distribution does not exist. Knowing the distribution and looking at the first envelope will always yield an expected overhead for us.
There is an interesting twist of this problem which I recently found on YouTube. This time, we restrict the choice of for the envelopes to the following pairs, selected with the indicated probabilities:
P\{(1,10)\} = \frac{1}{2}, \quad P\{(10,100)\} = \frac{1}{4}, \quad P\{(100,1000)\} = \frac{1}{8}, \quad\ldots This is an experiment we can carry out. It satisfies the criterion I gave above for a good question about probabilities.
However, we could now ask about the value of the switching strategy given that we see a specific number in our envelope, say the number 10. It is easy to see that switching gives us a better result in each case. This is essentially like restricting the envelopes to the two pairs which contain 10, i.e., (1,10) and (10,100), and knowing that only those are possible. Clearly, we switch once we see the 10.
This sounds paradoxical at first. It sounds as if you need to switch every time in the full experiment with all envelopes. You may do indeed do so. But computing the average outcome of your switching strategy reveals that it is infinit. The non-switching strategy has the same expected value. It does not make sense to compare them. If you do the experiment by selecting envelopes a given number of repetitions over and over again, you will not see an advantage of switching. Half of the time, one is better, and half of the time the other.
If the number of envelopes is restricted to some finite number, it is obvious that the switching does not have any advantage. The wrong reasoning above just ignores the big loss when the highest value in the envelopes is selected and there is no higher number in any envelope to compensate this.