First-Envelope Problem, Probabilistic Reasoning

Suppose you are given two envelopes both containing money, and you know that no matter what the amounts are, one envelope contains double the amount of the other. You want to choose the envelope that contains the largest amount.

Without loss of generality, assume that the money are of integer type. Denote the two envelopes as

X = n  
Y = 2n, n $\in \mathbb{N}$

You pick one envelope of the two at random, and before you open it, you are given the opportunity to change your choice and pick the other envelope instead. What would you do, and why?

It is natural to think that this question is meaningless, since both envelopes are pressumably assigned probability 0.5 of containing the largest amout, and thus by choosing to change your choice you are basically changing your probability of success from 0.5 to 0.5, which is trivial.

It's like betting on "Heads" on a coin flip game, and then choosing to bet on "Tails" instead. You can certainly do that, however you still have the same probability of success. Right?

In a zero-sum, fair coin flip game this is correct. But is it really correct in the envelope problem as well? Surprisingly, not quite!

To show this, assume a 2-dimensional random vector (X, Y) where X and Y are as defined above. Assume that we pick the envelope X, that contains n money. What is the conditional expectation of Y in this case? In words, how much money we expect the Y envelope to contain given that our chosen X envelope contains n money?

Let's see:

If X = n, then either Y = 2n or Y = $\frac{n}{2}$. Since we picked X with p = 0.5, then

P(Y = 2n | X = n) = P(Y = $\frac{n}{2}$ | X = n) = $\frac{1}{2}$

That is, the probability that Y contains double the money or half the money of X, conditioned on X containing n money, is the same.

However, if you look at the conditional expectation of Y:

E(Y | X = n) = $\frac{1}{2} 2n + \frac{1}{2} \frac{n}{2} = n + \frac{n}{2} = \frac{5}{4} n > n$

This is bizzare. This tells us that no matter what the value of X is, we would expect the value of Y to be strictly larger than X, so we should indeed change our initial choice and prefer the other envelope.

Wait what? Are the math broken or something?

Although this looks the case, there is an erroneous assumption here that triggers the above contradictory result.

Consider the following reasoning:

In order to distribute money in the envelopes, we need to have a distribution according which we put the money in the envelopes.

Claim: Such distribution is impossible to assign n and 2n money inside the two envelopes with probability of 0.5 in each. 

Proof:

Looking at the marginal distributions, we would expect them to be the same:

P(Y = n) = P(Y = n | X = 2n) P(X = 2n) + P(Y = n | X = $\frac{n}{2}$) P(X = $\frac{n}{2}$)

or

P(Y = n) = $\frac{1}{2}$ * P(X = 2n) + $\frac{1}{2}$ * P(X = $\frac{n}{2}$)

Again, without loss of generality, assume that n is some power of 2. Define:

$q_n$ := P(X = $2^n$)

Then:

P(Y = $2^n$) = $\frac{1}{2}$ P(X = $2^{n+1}$) + $\frac{1}{2}$ P(X = $2^{n-1}$)

or

$q_n = \frac{1}{2} q_{n+1} + \frac{1}{2} q_{n-1}$

If we plot all (n, $q_n$) points, they must lie on a straight line. Then, there are 3 cases to examine about the slope of that line:

1) Slope $\neq 0 \rightarrow$ $\exists$ $q_n$ points with $q_n < 0$, which is impossible since $q_n$ represents a probability

2) Slope = 0 $\rightarrow$  $q_n = c$, where $c$ is some constant. From that we derive two cases:

1. c = 0 $\Rightarrow$ $\sum_n q_n$ = 0, which is impossible since $q_n$s must add to 1
2. c > 0 $\Rightarrow$ $\sum_n q_n = \infty$, which is also impossible

As a result, such random vector with the predescribed properties does not exist, i.e. the setup of the problem is false.

This means that picking an envelope between two, both coming from such distribution, cannot happen with 50% chance. That is, one of the two has higher probability of containing more or less money than the other.

In particular, a possible distribution would look like the following:

E(Y | X = n) = $\frac{n}{2} p + 2n (1-p) = n$ $\Rightarrow$

$\frac{n}{2} p + 2n  - 2np = n$ $\Rightarrow$

$\frac{n}{2} p + n  - 2np = 0$  $\Rightarrow$

$n (\frac{1}{2} p + 1  - 2p) = 0$ $\Rightarrow$

$\frac{1}{2} p + 1  - 2p = 0$ $\Rightarrow$

$p (\frac{1}{2} - 2) = -1$ $\Rightarrow$

$p = \frac{-1}{- \frac{3}{2}} = \frac{2}{3}$

Thus, such distribution would distribute the $\frac{n}{2}$ quantity with $p = \frac{2}{3}$ and the 2n quantity with $(1-p) = \frac{1}{3}$.

In summary:

"It is impossible to distribute amounts of money over the envelopes such that no matter what I see in the first, the amounts in the other are either half or twice as much this amount, with equal probability"

Source: 

A Natural Introduction to Probability Theory, Ronald Meester