Solving the two envelopes problem

post by rstarkov · 2012-08-09T13:42:19.982Z · LW · GW · Legacy · 33 comments

Contents

  The flawed argument
  Game master strategies
  What's going on here?
  Solution
None
33 comments

Suppose you are presented with a game. You are given a red and a blue envelope with some money in each. You are allowed to ask an independent party to open both envelopes, and tell you the ratio of blue:red amounts (but not the actual amounts). If you do, the game master replaces the envelopes, and the amounts inside are chosen by him using the same algorithm as before.

You ask the independent observer to check the amounts a million times, and find that half the time the ratio is 2 (blue has twice as much as red), and half the time it's 0.5 (red has twice as much as blue). At this point, the game master discloses that in fact, the way he chooses the amounts mathematically guarantees that these probabilities hold.

Which envelope should you pick to maximize your expected wealth?

It may seem surprising, but with this set-up, the game master can choose to make either red or blue have a higher expected amount of money in it, or make the two the same. Asking the independent party as described above will not help you establish which is which. This is the surprising part and is, in my opinion, the crux of the two envelopes problem.

This is not quite how the two envelopes problem is usually presented, but this is the presentation I arrived at after contemplating the original puzzle. The original puzzle prescribes a specific strategy that the game master follows, makes the envelopes indistinguishable, and provides a paradoxical argument which is obviously false, but it's not so obvious where it goes wrong.

Note that for simplicity, let's assume that money is a real quantity and can be subdivided indefinitely. This avoids the problem of odd amounts like $1.03 not being exactly divisible by two.

The flawed argument

The flawed argument goes as follows. Let's call the amount in the blue envelope B, and in red R. You have confirmed that half the time, B is equal to 2R, and half the time it's R/2. This is a fact. Surely then the expected value of B is (2R * 50% + R/2 * 50%), which simplifies to 1.25R. In other words, the blue envelope has a higher expected amount of money given the evidence we have.

But notice that the situation is completely symmetric. From the information you have, it's also obvious that half the time, R is 2B, and half the time it's B/2. So by the same argument the expected value of R is 1.25B. Uh-oh. The expected value of both envelopes is higher than the other?...

Game master strategies

Let's muddy up the water a little by considering the strategies the game master can use to pick the amounts for each envelope.

Strategy 1

Pick an amount X between $1 and $1000 randomly. Throw a fair die. If you get an odd number, put X into the red envelope and 2X into blue. Otherwise put X into blue and 2X into red.

Strategy 2

Pick an amount X between $1 and $1000 randomly. Put this into the red envelope. Throw a fair die. If you get an odd number, put 2X into blue, and if it's even, put X/2 into blue.

The difference between these strategies is fairly subtle. I hope it's sufficiently obvious that the "ratio condition" (B = 2R half the time and R = 2B the other half) is true for both strategies. However, suppose we have two people take part in this game, one always picking the red envelope and the other always picking the blue envelope. After a million repetitions of this game, with the first strategy, the two guys will have won almost exactly the same amounts in total. After a million repetitions with the second strategy, the total amount won by the blue guy will be 25% higher than the total amount won by the red guy!

Now observe that strategy 2 can be trivially inverted to favour the red envelope instead of the blue one. The player can ask an independent observer for ratios (as described in the introduction) all he wants, but this information will not allow him to distinguish between these three scenarios (strategy 1, strategy 2 and strategy 2 inverted). It's obviously impossible to figure out which envelope has a higher expected winnings from this information!

What's going on here?

I hope I've convinced you by now that the information about the likelihood of the ratios does not tell you which envelope is better. But what exactly is the flaw in the original argument?

Let's formalize the puzzle a bit. We have two random variables, R and B. We are permitted to ask someone to sample each one and compute the ratio of the samples, r/b, and disclose it to us. Let's define a random variable called RB whose samples are produced by sampling R and B and computing their ratio. We know that RB can take two values, 2 and 0.5, with equal probability. Let's also define BR, which is the opposite ratio: that of a sample of B to a sample of R. BR can also take two values, 2 and 0.5, with equal probability.

The flawed argument is simply that the expected value of RB, E(RB), is 1.25, which is greater than 1, and therefore E(R) > E(B). The flawed argument continues that E(BR) is 1.25 too, therefore E(B) > E(R), leading to a contradiction. What's the flaw?

Solution

The expected value of RB, E(RB), really is 1.25. The puzzle gets that one right. E(BR) is also 1.25. The flaw in the argument is simply that it assumes E(X/Y) > 1 implies that E(X) > E(Y). This implication seems to hold intuitively, but human intuition is notoriously bad at probabilities. It is easy to prove that this implication is false, by considering a simple counter-example courtesy of VincentYu.

Consider two independent random variables, X and Y. X can take values 20 and 60, while Y can take values 2 and 100, both with equal probability. To calculate the expected value of X/Y, one can enumerate all possible combinations, multiplying each by its probability. The four possible combinations of X and Y are 20/2, 20/100, 60/2 and 60/100. Each combination is 25% likely. Hence E(X/Y) is 10.2. This is greater than 1, so the if the implication were to hold, E(X) should be greater than E(Y). But E(X) is (20+60)/2 = 40, while E(Y) is (2+100)/2 = 51. Hence, the implication E(X/Y) > 1 => E(X) > E(Y) does not hold in general.

So there you have it. The proposed argument relies on an implication which seems true intuitively, but turns out to be false under scrutiny. Mystery solved?... Almost.

Imprecise language's contribution to the puzzle

The argument concerning the original, indistinguishable envelopes, is phrased like this: "(1) I denote by A the amount in my selected envelope. (2) The other envelope may contain either 2A or A/2, with a 50% probability each. (3) So the expected value of the money in the other envelope is 1.25A. (4) Hence, the other envelope is expected to have more dollars."

Depending on how pedantic you are, you might say that the statement made in the third sentence is strictly false, or that it is too ambiguous to be strictly false, or that at least one interpretation is true. The expected value 1.25A is "of the amount of money contained in the other envelope expressed in terms of the amount of money in this envelope". It is not "of the amount of money in the other envelope expressed in dollars". Hence the last sentence does not follow, and if the statements were made in full and with complete accuracy, the fact that it does not follow is a little bit more obvious.

In closing, I would say this puzzle is hard because "in terms of this envelope" and "in terms of dollars" are typically equivalent enough in everyday life, but when it comes to expected values, this equivalence breaks down rather counter-intuitively.

33 comments

Comments sorted by top scores.

comment by VincentYu · 2012-08-04T17:58:31.898Z · LW(p) · GW(p)

But we know from basic probability theory that for two independent random variables, E(X/Y) > 1 does actually imply E(X) > E(Y).

This does not follow; a counterexample:

Suppose X and Y are independent random variables, with X taking the values {2,100}, and Y the values {1,150}, each with equal probability (i.e., each of X and Y follows the Bernoulli distribution with p = 0.5). Then we have
E(X/Y) = (2/1 + 100/1 + 2/150 + 100/150) / 4 = 25.67 > 1,
but
E(X) = 51 < 75.5 = E(Y).

Keep in mind that the equation E(1/Y) = 1/E(Y) does not hold in general, because taking the inverse is not a linear transformation. To evaluate the expectation after a nonlinear transformation, one requires not just the orignal expectation, but also the pdf of the distribution. (I can't be sure this is what you did, but misapplying this gives: E(X/Y) = E(X)E(1/Y) = E(X)/E(Y). The first equality holds if X and Y are independent or by definition if X and 1/Y are uncorrelated, but the second equality does not hold in general.)

Replies from: Manfred, rstarkov, tgb
comment by Manfred · 2012-08-04T19:50:03.378Z · LW(p) · GW(p)

Thanks, good point. Hopefully I don't turn out to be falsely complacent about this conclusion too :)

comment by rstarkov · 2012-08-05T18:58:22.389Z · LW(p) · GW(p)

Addressed by making a few edits to the "Solution" section. Thank you!

comment by tgb · 2012-08-04T18:35:40.629Z · LW(p) · GW(p)

An even easier example: X is always -4 and Y is always -2.

Replies from: Manfred, VincentYu
comment by Manfred · 2012-08-05T05:04:04.822Z · LW(p) · GW(p)

Since amounts of money are positive, this is a counterexample to a mistake not in the original article.

comment by VincentYu · 2012-08-05T00:10:57.460Z · LW(p) · GW(p)

Thanks, this is indeed a simpler counterexample. Note that it is a counterexample to a different error in the original statement. In particular, the error you've caught here is that from
X/Y > 1,
one cannot conclude that
X > Y.

comment by CronoDAS · 2012-08-06T02:44:48.836Z · LW(p) · GW(p)

Another commentary I once read regarding the "two envelopes paradox":

In order to make any sense out of this problem, you have to assume some prior probability distribution over the amount of money in the two envelopes. For many of these possible distributions, once you open one of the envelopes and learn how much money is inside, you now know more about whether the other envelope has more or less money than the one you opened. For example, if you assume that neither envelope has more than $1,000 and then open an envelope with $800, the other envelope has to have $400, so, contrary to the line of reasoning in the "paradox", switching would be bad.

On the other hand, perhaps you only want to think about distributions for which it seems the paradox still holds: ones in which that, regardless of how much money you find in envelope A, envelope B still has an equal chance of being twice as much or half as much. Well, it turns out that you can prove that this criterion also implies that the expected value of the amount of money in envelope A is infinity. This makes the paradox seem much less paradoxical: first, when your expected value is infinity, any specific finite result is disappointing (which is why switching is always correct), and second, any finite number multiplied by infinity is still infinity (which explains how each envelope can have an expected value of 1.25 times the other).

(Apparently, my original source was David Chalmers, of all people.)

Replies from: Omegaile, Sniffnoy
comment by Omegaile · 2012-08-13T19:02:07.432Z · LW(p) · GW(p)

On the other hand, perhaps you only want to think about distributions for which it seems the paradox still holds: ones in which that, regardless of how much money you find in envelope A, envelope B still has an equal chance of being twice as much or half as much

I don't see your conclusion holding. I am inclined to say: Therefore there are no distributions which that, regardless of how much money you find in envelope A, envelope B still has an equal chance of being twice as much or half as much.

Replies from: wedrifid
comment by wedrifid · 2012-08-13T19:42:07.331Z · LW(p) · GW(p)

I don't see your conclusion holding. I am inclined to say: Therefore there are no distributions which that, regardless of how much money you find in envelope A, envelope B still has an equal chance of being twice as much or half as much.

I suppose "numbers selected from all the numbers in the series 2^n" and so forth are ruled out of being distributions based on the "infinities and uncomputable things are just silly" principle? (I am fairly confident that) something on that order of difficulty is going to required to provide the envelopes. A task that is beyond even Omega in the universe as we know it but perhaps not beyond an intelligent agent in the possible universes that represent computational abstractions natively.

Replies from: Omegaile
comment by Omegaile · 2012-08-13T19:49:20.206Z · LW(p) · GW(p)

Actually there are no uniform distribution in this set (an infinite enumerable set). You may select numbers from this set, but some of them will have higher probability than others.

Replies from: wedrifid
comment by wedrifid · 2012-08-13T20:23:11.224Z · LW(p) · GW(p)

Actually there are no uniform distribution in this set (an infinite enumerable set).

That is what I was getting at with 'ruled out of being distributions'.

Replies from: Omegaile
comment by Omegaile · 2012-08-13T20:33:41.143Z · LW(p) · GW(p)

Oh... I misunderstood you then.

comment by Sniffnoy · 2012-08-09T19:00:39.601Z · LW(p) · GW(p)

Moreover, this means that if we want to do this with utility rather than money, you'd need an unbounded utility function, which can't happen if you're obeying Savage's axioms.

comment by thomblake · 2012-08-09T15:05:08.751Z · LW(p) · GW(p)

Generally, people do take R and B to be fixed amounts of money - then, it's worth pointing out that the expected value of the blue envelope is not .5*.5R+.5*2R, because R there stands for 2 different amounts of money.

If the amounts of money are $5 and $10, then R in the first case stood for $10 and R in the second case stood for $5, so it should really be .5*.5($10)+.5*2($5), and the expected value is just $7.50.

Replies from: mwengler
comment by mwengler · 2012-08-30T14:31:16.571Z · LW(p) · GW(p)

Yes, I like your simplification.

To amplify it and make the results explicit, Suppose my envelope strategy is to flip a fair coin and
heads: R=$5 B=$10
tails: R=$10 B=$5.

Then
E(R) = E(B) = $7.50
E(B)/E(R) = E(B)/E(R) =1
E(R/B) = E(B/R) = 1.25

comment by Decius · 2012-08-05T19:52:45.545Z · LW(p) · GW(p)

One of the envelopes contains 2 glort's worth of dollars, and the other envelope contains 4 glorts' worth of dollars. I don't know the exchange ratio of glorts to dollars, except that it is positive.

Now it is clear that the expected value is 3 glorts' worth of dollars, regardless of the envelope picked. It's still possible that the game master is using some variant of "if the value of the glort is low for the duration of this trial, put the larger amount of money in envelope B; if the value of the glort is high, put the larger amount of money in envelope a" that favors one envelope over the other.

comment by Douglas_Knight · 2012-08-04T16:39:50.182Z · LW(p) · GW(p)

It is aimed at people with only basic command of probabilities

Such people have probably not heard of the two envelopes problem and thus the title is not informative for them.* It seems to me that it would be useful to put something in the title to indicate that this post is about probabilities and maybe that it is fairly introductory. I could be wrong about how people read this site. Maybe everyone clicks through to the article and reads as far as the italicized section, but it seems low cost to give it a more informative title.

* Also, I doubt that people who do associate "two envelopes" with probability are not very likely to think of this particular problem, for what it's worth.

Added: "this site" = discussion. If the plan is to move this to main, the structure makes more sense. But I still think the title could be better.

Replies from: rstarkov
comment by rstarkov · 2012-08-05T15:02:14.904Z · LW(p) · GW(p)

All fair points. I did want to post this to main, but decided against it in the end. Didn't know I could move it to main afterwards. Will work on the title, after I've fixed the error pointed out by VincentYu.

comment by Omegaile · 2012-08-13T19:43:45.146Z · LW(p) · GW(p)

There is another very cool puzzle that can be considered a followup which is:

There are two envelopes in which I, the host of the game, put two different natural numbers, chosen by any distribution I like, that you don't have access. The two envelopes are indistinguishable. You pick one of them (and since they are indistinguishable, this can be considered a fair coin flip). After that you open the envelope and see the number. You have a chance to switch your number for the hidden number. Then, this number is revealed and if you choose the greater you win, let's say a dollar, otherwise you pay a dollar.

Now, before everything I said happens, you must devise a strategy that guarantees that you have a greater than 1/2 chance of winning.

Some notes:

1- the problem may be extended for rational, or any set of constructive numbers. But if you want to think only in probabilities this is irrelevant, just an over formalism.

2- This may seem uncorrelated to the two envelopes puzzle at first, but it isn't.

3- I saw this problem first on EDITthis post on xkcd blag. Thanks for Vaniver for pointing out.

Replies from: Vaniver, Pentashagon, wedrifid
comment by Vaniver · 2012-08-13T20:56:34.439Z · LW(p) · GW(p)

I believe you're thinking of this blag post.

Replies from: Omegaile
comment by Omegaile · 2012-08-13T21:36:09.055Z · LW(p) · GW(p)

Yes, that's it! Thanks.

comment by Pentashagon · 2012-08-17T16:22:29.515Z · LW(p) · GW(p)

Isn't there an additional requirement that there is a minimum element in the set?

Replies from: Omegaile
comment by Omegaile · 2012-08-18T19:05:19.864Z · LW(p) · GW(p)

No, you can think on the rationals, for example.

comment by wedrifid · 2012-08-13T20:45:27.714Z · LW(p) · GW(p)

There are two envelopes in which I, the host of the game, put two different natural numbers, chosen by any distribution I like, that you don't have access.

Now, before everything I said happens, you must devise a strategy that guarantees that you have a greater than 1/2 chance of winning.

Well natural numbers and simple greater than satisfying makes it easy. "If one THEN swap ELSE keep."

Replies from: Omegaile
comment by Omegaile · 2012-08-13T21:33:57.706Z · LW(p) · GW(p)

Maybe I didn't express myself well, but this strategy should work regardless of the distribution I choose. For example, if I choose a distribution in which 1 has probability 0, than your strategy yield 1/2 chance.

Replies from: wedrifid
comment by wedrifid · 2012-08-14T01:53:11.427Z · LW(p) · GW(p)

Maybe I didn't express myself well, but this strategy should work regardless of the distribution I choose. For example, if I choose a distribution in which 1 has probability 0, than your strategy yield 1/2 chance.

If that kind of selection of distributions is possible then there is no free lunch to be found.

For any strategy of envelope switching a hostile distribution selector who knows your strategy in advance can trivially select distributions to thwart it.

Replies from: Oscar_Cunningham
comment by Oscar_Cunningham · 2012-08-14T14:45:16.320Z · LW(p) · GW(p)

Have you looked at the "solution"? There really isn't a counter-strategy that reduces it to 1/2 chance, although there are strategies moving it arbitrarily close to 1/2.

comment by Stuart_Armstrong · 2012-08-09T15:00:30.177Z · LW(p) · GW(p)

It is easy to prove that this implication is false, by considering a simple counter-example courtesy of VincentYu.

Even simpler counter example: X and Y take values 1 and 100, independently and with equal probability. Then E(X/Y) = 1/4 ( 1/1 + 1/100 + 100/100 + 100/1), which is basically 25.5. Ditto for E(Y/X).

Expectation is a mean, and in means, large terms dominate - for E(X/Y), the (X=100,Y=1) situation dominates, while for E(Y/X), the (X=1,Y=100) situation dominates.

In fact, if X and Y are independent, identically distributed, strictly positive and non-trivial (ie not just constants), then I think that we always have E(X/Y) > 1.

comment by Manfred · 2012-08-04T14:03:54.648Z · LW(p) · GW(p)

Nice.

comment by selylindi · 2013-10-31T21:57:54.202Z · LW(p) · GW(p)

I think you reached the wrong conclusion in your final paragraphs. Can you show how the expected value calculation could be different for "the amount of money contained in the other envelope expressed in terms of the amount of money in this envelope [which is in dollars, BTW]" versus "the amount of money in the other envelope expressed in dollars"?

I see that Wikipedia says that there is no generally accepted solution to the paradox. That almost certainly means people are interpreting it differently. I'll give my opinion. But let me recast the problem in more pointed terms.

Mr Moneybags writes a check for some real positive amount of money and puts it in an envelope. Then he writes a check for double the amount of the previous check and puts it in another envelope. He shuffles the envelopes. You pick one and open it, and you find $N. He offers to let you switch to the other just this once. Should you?

On first glance it appears that the other envelope could have $N/2 or $N*2, and that you are entirely ignorant about which is the case, so your ignorance priors are 1/2 for each possibility. Then the expected value calculation comes up all wrong! Call the hypothesis that you opened the lower value envelope L and the hypothesis that you opened the higher value envelope H.

E(switching)=P(H)*(N/2)+P(L)*(N*2)=(1/2)*(N/2)+(1/2)*(N*2)=(5/4)*N.  

But that's nonsense. My opinion as to what went wrong was that it's false that you are entirely ignorant after opening the envelope, because you can now do an update on your ignorance prior.

We'll start, of course, with Bayes' formula P(H|N)/P(L|N) = P(N|H)/P(N|L) * P(H)/P(L) * P(N)/P(N). The last ratio cancels. The second-to-last ratio also cancels because the shuffling of the envelopes made it equally likely you'd open either one. We know basically nothing about the distribution that the lower value was first drawn from, so a convenient ignorance prior on it is that it was some uniform distribution over the interval $A to $B. Consequently, the higher value would be described by a uniform distribution over the interval 2*$A to 2*$B. The distributions may or may not overlap. I'll take each case separately.

Common start: A=0.

P(N=k|H)={1/3 for 0<k<=B; 1 for B<k<=2B}
P(N=k|L)={2/3 for 0<k<=B; 0 for B<k<=2B}
Integrate each with respect to k from 0 to 2B, then plug in
P(H|N)/P(H|L) = (4/3*B)/(2/3*B) = 2
and convert back to probabilities
P(H|N)=2/3, P(L|N)=1/3.

Separate start: A>0 and 2A<B.

P(N=k|H)={0 for A<k<2A; 1/3 for 2A<=k<=B; 1 for B<k<=2B}
P(N=k|L)={1 for A<k<2A; 2/3 for 2A<=k<=B; 0 for B<k<=2B}
Integrate each with respect to k from A to 2B, then plug in
P(H|N)/P(H|L) = P(N|H)/P(N|L) = (4/3*B-2/3*A)/(2/3*B-1/3*A) = 2
and convert back to probabilities
P(H|N)=2/3, P(L|N)=1/3.

No overlap: B<2A.

P(N=k|H)={0 for A<=k<=B; 1 for 2A<=k<=2B}
P(N=k|L)={1 for A<=k<=B; 0 for 2A<=k<=2B}
Integrate each with respect to k from A to 2B, then plug in
P(H|N)/P(H|L) = P(N|H)/P(N|L) = (2B-2A)/(B-A) = 2
and convert back to probabilities
P(H|N)=2/3, P(L|N)=1/3.

So viewing your prize, you suddenly feel it's twice as likely that you got the higher amount. Bizarre, huh? And your expected value calculation becomes

E(switching)=P(H|N)*(N/2)+P(L|N)*(N*2)=(2/3)*(N/2)+(1/3)*(N*2)=N,

so there's no point switching after all. Even weirder is that, before you open the envelope, this is a situation where you know for sure what you will believe in the future, but you nevertheless can't make that update till then.

comment by ScottMessick · 2012-08-09T03:18:02.692Z · LW(p) · GW(p)

This is a really good exposition of the two envelopes problem. I recall reading a lot about that when I first heard it, and didn't feel that anything I read satisfactorily resolved it, which this does. I particularly liked the more precise recasting of the problem at the beginning.

(It sounds like some credit is also due to VincentYu.)

comment by roryokane · 2013-10-29T02:40:07.305Z · LW(p) · GW(p)

The flaw in the argument is simply that it assumes E(X/Y) > 1 implies that E(X) > E(Y).

I didn’t understand this sentence very well at first, because the inequality on the right is two steps removed from the one on the left. I find this version clearer:

The flaw in the argument is simply that it assumes E(X/Y) > 1 implies that E(X) / E(Y) > 1. (If E(X) / E(Y) > 1, that would imply that E(X) > E(Y).)

comment by William_Kasper · 2012-08-12T03:15:24.629Z · LW(p) · GW(p)

Here's a solution to a more general version of the problem:

Let's say that the red envelope contains N times as much money as the blue envelope with probability p, and the blue envelope contains N times as much money as the red envelope with probability (1 - p).

Without loss of generality, N is at least 1.

If N = 1, both envelopes contain the same amount, and there is no point in switching.

If N > 1, let the variable s represent the smaller amount of money between the amounts of the two envelopes. So one envelope contains s, and the other envelope contains Ns.

Scenario 1: The blue envelope contains s, and the red envelope contains Ns. This scenario occurs with probability p.

Scenario 2: The red envelope contains s, and the blue envelope contains Ns. This scenario occurs with probability (1 - p).

Assume s is not less than 0.

The expected amount of money in the blue envelope, E(B) = sp + Ns(1 - p) = s(p + N - Np).

The expected amount of money in the red envelope, E(R) = s(1 - p) + Nsp = s(1 - p + Np).

If s = 0, both envelopes contain the same amount, and there is no point in switching.

If s > 0, compare the expectations of the amounts of money in the envelopes in terms of s:

E(B) > E(R) when

s(p + N - Np) > s(1 - p + Np)

p + N - Np > 1 - p + Np

2p - 2Np > 1 - N

2p(1 - N) > 1 - N

2p < 1, because (1 - N) < 0

p < 1/2

Similarly, E(B) < E(R) when p > 1/2, and E(B) = E(R) when p = 1/2.

The ratios of the expected amounts of money in each envelope depend only on p when s > 0 and N > 1.

Both envelopes contain the same amount of money when s = 0, N = 1, or both.

So if your degree of belief that the red envelope contains more money than the blue envelope is the same as your degree of belief that the blue envelope contains more money than the red envelope, don't bother switching, unless you need to kill time (which you already knew intuitively, but Q.E.D.)

I got the idea of using the variable s to represent the smaller of the amounts in the two envelopes from R Falk 2008: "The Unrelenting Exchange Paradox".