[Previous] Quality of Argument | Home | [Next] Being Sympathetic To Children

Envelope Paradox

Here is an interesting math problem about a paradox with envelopes. The answers given there are incorrect so I've written better ones.

Problem
There are two envelopes each with a random number inside. You open one and guess if the other number is bigger or smaller. Can you do better than chance?

Problem 2
There are two envelopes with money in them. One has twice as much as the other. You open one and then choose to keep it or swap envelopes. Is there a strategy that makes more money than never swapping?

Wrong Answer 1
Before you open the envelope, choose a pivot number like 500. If the number you open is over 500 guess the other number will be smaller. If it's under 500, guess bigger. The following can happen:

Both numbers are over 500. You score 50%
Both numbers are under 500. You score 50%
One number is over 500 and the other is under 500. You score 100%

Therefore on average the pivot strategy scores over 50%!

Wrong Answer 2
Say you open 100. Four possible things can happen. The total money in both is 300 or 150 and we keep or swap.

total 300 swap get 200
total 300 keep get 100
total 150 swap get 50
total 150 keep get 100

Total for keeping: 200
Total for swapping: 250

Therefore swapping makes more money than keeping.

Answer 1
There is no such thing as choosing a random integer (with equal probability for all integers). You can't choose randomly from an infinitely large set. You can think of it as each individual number has a 1 in infinity chance to be chosen, which is zero.

Answer 2
Again, there is no such thing as choosing a random integer (with equal probability for all integers). So it's not possible to be presented with that situation.

But that's boring! And it's still hard to see why the wrong answers are wrong besides that the problems technically don't make sense. So I tried putting money into envelopes in some possible ways and then seeing what strategy would be best (if any).

I used ruby to help out. Here's the code. But first I'll try to explain why the wrong answers are false in English.

The pivot strategy only does better than chance if you can ever guess a pivot that is between the two numbers. There are infinite choices of pivot, but only finite integers between the two numbers. So your chance of guessing correctly is finite divided by infinite. It's zero.

The money strategy (always swap) can't be right because it doesn't use the information of how much money you opened. So you could swap without even opening an envelope. That can't possibly be profitable.

Now let's put some money into envelopes! We'll need a strategy for deciding what goes in the envelopes. Let's try this: take the numbers from 0-5. For each one, make the pairs [x, x*2] and [x, x/2]. So we'll get 12 pairs of envelopes and each pair will correctly have one envelope with twice as much cash. Here are all the pairs:

[[0, 0.0], [0, 0.0], [1, 0.5], [2, 1.0], [2, 1.0], [3, 1.5], [4, 2.0], [4, 2.0], [5, 2.5], [6, 3.0], [8, 4.0], [10, 5.0]]

If we look closely we can figure out what we might get if we swap each number. All you do is imagine you open a 4 and then look for all the envelopes that have a 4 paired with them. There's two 2's paired with 4, and an 8. Here's all of them:

0: 0 0 0 0
.5: 1
1: .5 2 2
1.5: 3
2: 1 1 4 4
2.5: 5
3: 1.5 6
4: 2 2 8
5: 2.5 10
6: 3
8: 4
10: 5

So you can see you don't wanna swap any high numbers (6-10), swapping 0 and 4 breaks even, and swapping 1, 2, 3, 5 and fractions gains. So there is a strategy to make extra money, but it's not "always swap". You have to look at what number you open and only swap certain numbers.

Now suppose the envelope filling scheme is to take all the numbers from 1-1000 and make pairs of x,x+2 and x,x-1. The edge cases only have a small effect instead of being many of the numbers. So suppose you open the number 500.

500 is in the following pairs:

x = 498 => 498,500
x = 500 => 500,502, 500,499
x = 501 => 501,500

So if you swap you can get: 498 499 501 502

So despite the imbalance that a 10 can turn into 9 or 12 which average to 10.5 ... away from the edges swapping doesn't matter, swapping breaks even. Yay, the world is sane again! It's because and 8 and 11 can turn into a 10, which balances it out.

Now lets go back to having one envelope with double the money using x,x*2, x,x/2

500 is in the following pairs:

x = 250 => 250,500
x = 500 => 500,1000, 500,250
x = 1000 => 1000,500

So if you swap you can get 250 250 1000 1000. So swapping non-edge cases seems to be profitable! Is that really weird? Indiscriminate swapping can't be right!

Well, it's not as counter-intuitive as it seems. Think of it this way: there are some really big jackpots you can get. If the numbers range from 1-1000 before halving and doubling then there is an envelope with $2000. If you get a low number then it's worth shooting for doubling. But if you get a really high number then you should obviously keep it. So it's not crazy if we should swap more than half the time.

Now let's look at some more detailed results. Here is the half the output to my ruby program:

Results for *2 and /2 envelopes
sum simple swap results 11361136.0
sum smart swap results 13177840.0
avg of envelopes 113.0625
avg simple swap results 113.61136
avg smart swap results 131.7784
count of envelope pairs is 400
total envelopes is 800
swap 550
keep 100
tie 150
total unique values you can open is 400
unique swap 250
unique keep 100
unique tie 50
first swap index is 0 val is 0.5
last swap index is 696 val is 199.0
first keep index is 700 val is 202.0
last keep index is 799 val is 400.0
first tie index is 452 val is 102.0
last tie index is 699 val is 200.0


So what does all that mean in English? The envelope creation process used range 1-200 and made envelopes with x,2x and x,x/2 for a total of 800 envelopes we could open. And the results are: for 550 we should swap, 100 we should keep, and 150 it doesn't matter. Of the 400 actual different numbers we could open, we should swap 250 of them, keep 100, and for 50 it doesn't matter. We should swap 68.75%, and only keep 12.5% of the time!

From some extra output I disabled here (it's 800 lines long) I was able to see how the keep/swap/tie decisions were distributed (the summary of how they are distributed is above). All numbers up to 100 we should swap. All numbers over 200 we should keep. In the middle some should be swapped and some don't matter either way. It alternated 2 swaps then 3 ties.

So a new way to think about what happens if the numbers are chosen from an infinite range is: there are three sections: always swap, swap or tie, and always keep. Two are near the edges. In an infinite range there are no edges, so you get a biased set of envelopes with only the middle cases. But that's not possible.

If you use an envelope stuffing strategy with simple addition then the entire middle is ties, one end is swaps and the other end is keeps. You can see output for this at the bottom of my ruby code here.

By the way, I included a method in my script to make the ruby program learn how to play correctly and then play. I also had it play randomly. At the half/double envelopes game, the random program makes $113 per play and the smart one makes about $132. So it works! Soon I'll be rich...

Update I meant that you can't choose a random integer *with equal probability for all integers*. I've corrected the text above.

Elliot Temple on June 28, 2006

Comments (3)

Interesting!

However, you say:

if the numbers are chosen from an infinite range is: there are three sections: always swap, swap or tie, and always keep. Two are near the edges. In an infinite range there are no edges, so you get a biased set of envelopes with only the middle cases.

In the money problem, wouldn't you have an 'always swap' end, because you can't have negative money? The range is infinite, but only in the positive direction. So, your chances of doing better than a low number is high. For example, assuming you are working in dollars and cannot receive fractional pennies: if you open the envelope and there is $1 inside, you know there is a 99/infinity (or 100/infinity if you count $0 I guess) chance of getting less that $1, but infinity/infinity chance of getting more than $1. So, naturally you should swap.
But can that be generalized? I'm not sure, because even 1mill/infinity is going to be less than infinity/inifity. If you played the game over and over I guess you could pick numbers statistically.

Thanks for sharing...

Justin at 4:12 PM on June 28, 2006 | #19
We are assuming that you get an envelope with a positive amount of money.

The method of generation of the amount in it doesn't matter, as long as it is promised that a perfect coin flip equivalent was used to decide if half the amount or double the amount is placed in the other envelope.

In this case - blindly swapping is profitable:

Be x a real.

avg(2*x, 0.5*x) = 1.25x

It is profitable!

That's why bets are made "double or nothing" - 50/50 - and not "half or nothing" - unequal.

What you did is answer a different question: "You have an integer i between 0 and x. 2*i is also between 0 and x. What is the relation between i and 2.5*i?" the answer of which is quite easy to get at algebraicly.

SonOfLilit
SonOfLilit@GMail.com

SonOfLilit at 4:34 AM on June 29, 2006 | #20
Here's my understanding of it:

Problem 1

Suppose you have a random number generator that produces an uniform distribution over integers.

Now a generated number has a 50% chance of being positive and a 50% chance of being negative.

Cut the negative side in half at -q, defined as such that a generated negative number has a 50% chance of being larger than -q and a 50% chance of being smaller than -q.

As a result 25% of all generated numbers are smaller than -q, 75% are larger.

The average of all generated negative numbers is -q.

As a consequence, if the first number is negative, it will behave like -q on average and give us a 75% chance of any other random integer being larger than it.

Symmetric for the positive side.


Problem 2

The envelopes contain 6X coins in total. The envelope you have may contain 2X coins or 4X coins.

On average, you have (2X + 4X) / 2 = 3X coins.

By swapping, you come into possession of (on average) (4X + 2X) / 2 = 3X coins.

Ilmari at 8:27 PM on July 14, 2006 | #21

What do you think?

(This is a free speech zone!)