Here is an
interesting math problem about a paradox with envelopes. The answers given there are incorrect so I've written better ones.
ProblemThere 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 2There 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 1Before 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 2Say 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 1There 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 2Again, 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.0So 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.