The Two-Envelope Problem Solution: Part II

Read Part I first. We are in the peek first game here.

The distribution of N

When X is odd, and all X are discrete, we know we should always switch regardless of N’s size. We also discovered we should keep large, even Xs when X + 2X = 3X > N. We also tacitly assumed that the money in the game, 3X, was uniformly likely between the values 3, 6, 9, …, Max <= N. Suppose you are playing with an obscure internet billionaire (and if there are any obscure internet billionaires out there, my email is matt@mwbrigg.com). N, it is important to understand, is not necessarily equal to the amount of money in the envelopes; it might differ. That is, our billionaire sets aside a pile N high, and then grabs two amounts, X and 2X, where X + 2X might be less than N. OK: you peek and see a large, even X, and because you know N, it is clear that 3X < N. So it appears that keeping or switching is equivalent. But this is false because we have information about how the game master chose the amounts for the game from his N. That information is the tacit assumption that the money in the game was uniformly likely between the values 3, 6, 9, etc. Logical probability interlude: It is crucial, and painfully so, to remember that all probabilities are conditional on certain given information or premises. Change the premises, changes the probabilities!

Return to the peek

Let’s recap our solution to (2), where we first peek and see X and are allowed to keep or switch. The going, dear readers, is about to get rough.

Switch for odd X. Because we know that, because all X are discrete, the other envelope certainly contains 2X.

Keep for even X when X + 2X = 3X > N. Because we know that the other envelope cannot have 2X; thus, ours is the largest.

Keep or Switch? for even X such that 3X <= N. The surprising answer, given our tacit premise of uniform game amounts, is that you should always switch. Here’s why.

First suppose you keep the X you see. What do we know about that X? It’s even and its only possible values are 2, 4, 6, …, up to N/3 (actually, the nearest integer less than or equal to N/3, which we math types call the floor of N). Why? Well, suppose X is larger than N/3, then 3 times that number would be larger than N, which is impossible because we already decided to keep such X.

The X we see is, by our tacit assumption, equally likely to be any even number up to the floor of N/3. But the number of the other envelope is not equally likely to be any even number.

Suppose the X we see is 2, then the unopened envelope might be 1 or it might be 4. Thus it is possible that the unopened envelope is odd. Change gears now and think about the amount you win in this situation only, which is either an even X less than or equal to floor(N/3) or the value in the unopened envelope. We have just learned that that amount might be odd (if we peeked and saw that X was odd, we would have already switched).

Suppose the unopened envelope is odd. Then X can only be even and only be less than or equal to floor(N/3). This means that the unopened envelope can only be odd values up to floor(N/3)/2 (actually, the nearest odd less than or equal to this): it may not take odd values larger than this because that would make 3X > N.

Next suppose that the unopened envelope turned out to be 4, then X could have been 2 or 8. But if the unopened value was 6, then X can only be 12 but not 3; if it was 3, we would have already switched. This is the crucial point!

We have already discovered that X is equally likely to be any even number up to floor(N/3). And we know that the unopened envelope can be any odd value up to floor(N/3)/2. It may also take each even value up to this level. But after that, it may only take even values that are divisible by 4! Why? Because only numbers divisible by 4 when divided by 2 are even: and we know that X must be even (and less than or equal to floor(N/3)). Think of numbers divisible by 4 as 2*even, which when divided by 2 leaves the even number.

Let’s collect the possibilities of the unopened envelope:

• (a) Odd numbers up to floor(N/3)/2.
• (b) Even numbers up to floor(N/3)/2.
• (c) Even numbers divisible by 4 larger than floor(N/3)/2 up to a maximum 2*floor(N/3).

But each of these possibilities are not equally likely: even numbers divisible by 4 but still less than floor(N/3)/2 can appear in two ways (when X is twice or half the value). Odd numbers (a) are just as possible as large even (c), but each (b) is twice as likely.

Still with me? What it means is that the values for the unopened envelope are not equally likely. This is a consequence of two things: the tacit assumption of equally likely game amounts, and our knowledge that X must be even and less than or equal to floor(N/3).

Now, the probability that the unopened envelope contains values larger than floor(N/3) is non-zero. But X is stuck below these values. Switching can lead to higher win amounts, keeping guarantees lower amounts.¹ Thus, switching is better.

Keeping, however, guarantees that you win at least $2 (in this situation), whereas it is possible with switching that you win only $1. Thus, if you are playing not to maximize your winnings, but to guarantee a minimum, keeping can be a better strategy.

Non-uniform N

We still haven’t gotten to this! If there is interest, I will post a Part III (maybe after a break), where we deal with non-uniform or unknown N.

——————————————————————————-

¹The exact probabilities for any win amount are tedious to calculate, but not difficult to understand. Note that we have not anywhere said anything about repeated trials of this game. These are certainly possible, but it is easy to see that the strategy above is still optimal.

Read Part I first.