Fog Creek Software
Discussion Board




Two envelopes

I have 2 envelopes; one has twice as much money in it as the other.  I choose one at random (both equally likely), and give it to you.  Do you want to switch envelopes?

Do you want to switch again?  again?

Where's the hole in this logic:  my envelope has n dollars, the other envelope has either 2n or n/2 dollars, with equal likelihood, so my expected value of switching is 5n/4, so I want to switch.

schmoe
Saturday, April 12, 2003

The flaw is you're using the same letter to refer to two different amounts. In one case the envelope has $2N, in the other case the envelope has M/2, but M=2N.

Peter Meilstrup
Tuesday, April 15, 2003

You are right in that a nicer way to answer the problem is to say that the envelopes have amounts n and 2n, and by switching, I'd either gain n or lose n, with equal likelihood.  This description is very clear.

However, if we call the amount in your envelope n, then my envelope must have either 2n or n/2.  Put another way, suppose you opened your envelope and found $50.  You'd know my envelope would have either $25 or $100, and you're just as likely to get the high envelope as the low envelope, so it seems like your expected value of switching is $62.50, versus $50 for not switching.  But knowing your envelope contains $50 isn't really any different than knowing it has $n, is it?

schmoe
Tuesday, April 15, 2003

I think the error is in that your two possibilities suppose a different amount of total money in the game. You are considering n to be a constant, and comparing 3n/2 with 3n. Obviously in this case switching would seem to be advantageous. The total amount of money in the game is fixed - say x. If the other envelope contains 2n dollars, then n was only x/3. If the other envelope contains n/2 dollars, then n was 2x/3.

Expected gain = Gain(n=2x/3)*P(n=2x/3) +Gain(n=x/3)*P(n=x/3)
Expected gain = -x/3 * 1/2 + x/3 * 1/2 = 0 as expected.

I hope that's clear. It's been a long time ...
To summarize, you can't directly compare n/2 and 2n - It's not the same n.

Paul Viney

Paul Viney
Wednesday, April 16, 2003

If you are allowed to open the envelope, and you see $50 in the envelope, AND (your unstated assumption) you know that envelopes containing $50 and $100 are just as likely as envelopes containing $25 and $50, then you should switch.

But when you don't open the envelope, you can't assume that a smallest envelope containing $n is as likely as a smallest envelope containing $2n. There is no probability distribution on n which has that property, except the one where the envelopes never have any money at all. So the problem is ill-defined.

Peter Meilstrup
Wednesday, April 16, 2003

I have to say I find this one hard to get to grips with. I think several of the posters have good explanations. I'm just posting my version because I like to talk.

Assume the envelopes contain N and 2N (you don't know what N is yet).Let's say you see a $100 envelope, so you have N=100 or N=200

I don't have time to work out the details, but if you calculate this by Bayes theorem you end up dividing by the a priori probability of N being 100 plus probability of N=200. But because there is no limit or distribution of N, that probability is zero and you end up with an impossible division.

If you were to tell the guesser that N was evenly distributed between 1 and 1 billion (say) then it would be correct to switch for any number less than half a billion.

David Clayworth
Tuesday, April 22, 2003

"If you were to tell the guesser that N was evenly distributed between 1 and 1 billion (say) then it would be correct to switch for any number less than half a billion."

Yes - if the amount in either envelope is discovered, and you know something about the distribution from which n and 2n are chosen, you can make an intelligent decision.  (I think you also need to be able to guarantee that the distribution is bounded, which we can if the amounts are actual currency.)

Without knowing either number, there's no reason to switch  The only explanation I've heard about why the expected value of n isn't 5n/4 is this:  If you have n and switch, you either gain n or lose n/2.  However, when you gain n, n is "relatively small", and when you lose n, n is "relatively big", which makes the n's you gain have the same size on average as the n/2's you lose.  This doesn't really show the flaw in the expected value computation well enough for me, but it illustrates the effects of pulling n and 2n from some bounded distribution.

I've never actually asked someone this in an interview, and I don't think I would, but it's a mildly interesting diversion...

schmoe
Friday, April 25, 2003

The problem with the expectation calculation is to do with dividing by zero. If you expand the full Bayes theorem calculation (probability of the other envelope having $200 given that I have an envelope with $100) you will find that you are dividing by the a priori probability that the first envelope has $100. For an unbounded even distribution, this probability is zero. If you can divide by zero you can make anything equal anything (e.g. 2x=x => 2=1). So the expectation calculation is meaningless.

David Clayworth
Friday, April 25, 2003

It ought to be possible to come to the "correct" answer without opening the envelopes, and without assuming anything about the prior distribution of money in envelopes, and by using values of "money in this envelope" and "money in the other envelope" since it's just as valid a distinction as "smaller envelope" versus "bigger envelope."

Call the probability distribution of the envelope you first choose P(A), and the distribution of the other envelope P(B). We don't know anything about these distributions except that they are distributions, so their indefinite integrals must equal 1.

You know that its equally likely for envelope B to have either half or twice as much money as envelope A, so we relate the two distributions

P(B) = a*P(2*A) + b*P(A/2)

the first term reflecting the contribution from the case where the other envelope is smaller, and the second term from the case where the other envelope is bigger. Since either case is equally likely the indefinite integrals of the first and second terms must each equal 1/2. This works out to a=1 and b=1/4 (aha?)

P(B) = P(2*A) + P(A/2)/4

Now just take the expected value:

E(B) = E(A)/2 + 2*E(A)/4 = E(A)

so there is no expected advantage to switching.

In the "fake" solution we say that the value of the first envelope equals some number N. If we were to express the value of the first enveolpe as a distribution P(x) that means that P(x) = d(x-A) where d is the Dirac delta function. Recall that the Dirac distribution has the property d(x/2) = 2*d(x), and the error should be more clear, maybe...

I think I see another way of stating the flaw. The problem with the 5/4 answer is that n is not a number, it's what in probability theory is called a "random variable." RVs behave differently than numbers so it's not always valid to multiply and divide them in the same way that you do numbers. The error comes about by treating it like a number in one step then as an RV in the next.

I remember sitting in freshman stat class being completely baffled as to the difference between a random variable and a regular variable. I'm only slightly less unclear about it now.

Peter Meilstrup
Tuesday, April 29, 2003

*  Recent Topics

*  Fog Creek Home