This was a question posed in my Discrete Mathematics class at MIT one
day at the end of lecture...
You have two envelopes marked A and B.  You know each envelope
contains a positive integer of dollars.  One of the envelopes contains
k dollars and the other envelope contains 2k dollars where k is a
positive integer.  You are allowed to open one of the envelopes so you
choose envelope A at random and inside are 8 dollars.  You have a
choice of giving the money back and keeping what's in envelope B or
just keeping the eight dollars that were in envelope A.  Which is the
best strategy for making the most money?  Proove this method.

jellojoe,

Assuming we cannot tell anything by the appearance of the envelopes
(for example, the one have more money being thicker), there is an
exactly 50% chance of an envelope having k dollars, and an envelope
having 2k dollars.  However, we've seen inside envelope A, and it has
$8.

Now, if envelope A is 2k dollars, then envelope B is half that of A, or $4.
But if envelope A is k dollars, then envelope B is twice that of A, or $16.

As gabor mentions below, the probability of envelope B having more
dollars than envelope A is exactly the same as envelope A having more
dollars than envelope B.  So neither strategy has a higher probability
of being $2k.  However, suppose you are the betting type, and are
willing to take a potential loss of money by choosing envelope B?

Envelope A has only one potential state.  We know it has $8, so it's
potential value is $8.  However, envelope B still has two potential
states:  $4 and $16.  Each of these states has a 50% chance of being
true.  So we can find the potential value of Envelope B by multiplying
the potential value of each state by the potential probability of each
state, and adding them all together:

(50%)$4 + (50%)$16  =  $2 + $8  =  $10

The potential value of Envelope B, based on the possibilities and
probabilities of what is in it, is $10.  In it's unopened state, the
potential value of envelope B is higher than the potential value of
envelope A.

Personally, I would choose Envelope B, then, without opening it, sell
it to somebody for $9, thus assuring I made more money in the deal. 
;-)

---

Request for Answer Clarification by jellojoe-ga on 20 Feb 2004 20:32 PST

Ok, that was exactly what I was thinking, but the above argument seems
intuitively faulty, since it does not matter what amount of money is
revealed to be in the envelope you picked, as the other envelope will
always be expected to be worth more on average. Therefore, you might
as well not look at how much money is in the first envelope and just
pick the second. However, if you do not look in the first envelope,
there is nothing to distinguish the first envelope from the second! We
have the paradox that no matter which envelope is picked, the other
one will be expected to contain more money. It does not hurt you to
switch (and you could use your argument as the rationale), but it
should really not make a difference.

---

Clarification of Answer by hailstorm-ga on 21 Feb 2004 02:49 PST

jellojoe,

The extra information you have is what makes the difference.  Knowing
nothing about either envelope, envelope A and envelope B both have a
potential value of 1.5k dollars:

(50%)k + (50%)2k  =  .5k + k  = 1.5k

This is because both envelope A and envelope B have the same two
potential states.  In the problem above, this changes because our
information changes.  As a result, envelope A has but one potential
state, whereas envelope B still has two.  Because we can now
differentiate between envelope A and B, we can make an informed
decision based on what is known about them.

Let's consider the case where one envelope has k dollars, and one
envelope has ak dollars, where a is a real constant greater than 0. 
Envelope A has $8, so it's potential is $8.  Envelope B's potential
states are 8a dollars and 8(1/a) dollars.  Envelope B's total
potential value can be expressed as follows:

(50%)(8a) + (50%)(8/a)  = 4a + 4/a  = 4(a + 1/a)

4(a + 1/a) is greater than 8 in the case where (a + 1/a) is greater
than 2.  The lowest possible value for a positive number a is the case
where a=1, which gives us exactly 2.  That is to say, the case where
both envelope A and envelope B contain exactly the same amount.  In
any other case, where envelope A and envelope B contain differing
positive amounts of money, and the value of envelope A is known, the
potential value of envelope B is always higher.

So it is the case that knowledge of either of the envelopes contents
decreases its potential value as relates to the other envelope. 
Therefore, if you know the contents of one envelope, it is
fundamentally a better strategy to choose the unknown envelope.

Very good answer, the question actually turned out to be a probability
of expectations type of question.  I hope this is what my professor is
looking for.  The answer given to me though is sound and proven, good
work.

This might be useful to you:

http://www.j-bradford-delong.net/movable_type/archives/001395.html

thanks for the link, the solution offered though changes the problem
around, so ultimately their answer doesn't suit my problem, but it
raises some interesting thoughts.

I wrote up my take on the answer here:
http://n.ethz.ch/student/cselleg/ganswers/ganswer1.html

Hope it helps.

hailstorm: In my first answer, I disregarded that opening the first
envelope does actually give you additional information - that makes my
answer incorrect. :-(

|Let X1 and X2 be random variables for the amount of money in
envelopes 1 and 2. Now, before selecting and opening an envelope, the
entropies are H(X1) = H(X2) = inf (as both can take any value). Let's
say we pick envelope 1, so we know X1; obviously H(X1|X1) = 0. Now
H(X2|X1) = 1, as it X2 could either be 2*X1 or X1/2. By having opened
the first envelope, we have a different situation at the start.

hailstorm: I saw your clarification just after I wrote the last
comment. Like I said, I think you're right.

Alright I definitely agree with your answer now hailstorm, the problem
I now have is convincing my professors its the right answer.  Thanks
for your help.  Those mit professors are picky as hell, so I better
get my wording down exactly right.

It is right that the probability of the envelope being worth twice or
half as much is equal (as Gabor excellently pointed out), however..
the outcome is not symmetrical.

That means: if you would take the other envelope, you would get ($4 +
$16)/2 = $10 on average, as hailstorm has already pointed out.

If you do that 10 times, you will (statistically) get 5x $4 and %x
$16, that's $100 compared to $80 if you hadn't changed.

However: this is only correct under the false assumption that you will
ALWAYS have $8 in the envelope that you pick first.

You might as well get $4 or $16 in the next envelopes.. let's look
what differs now:
let's assume, you get envelopes twice with $4, $8 and $16:
if you always keep it, you will get:
   2x$4 + 2x$8 + 2x$16  = $48
if you always take the other envelope, you will get: 
   ($2 + $8) + ($4 + $16) + ($8 + $32)
 = $2 + $4 + 2x$8 + $16 + $32

Now what do we see here? The term 2x$8 turns up again. This gives us a
hint of what is happening here.
If you do that for every even number between an upper and a lower
limit, you will easily see that it doesn't matter whether or not you
change the envelope. On the average it's the same. That is, of course,
except for the limits.

That means: if you're on the upper limit and change your envelope, you
will loose massive amounts of money, while when you're at the lower
limit, you will gain a small amount of money. So the intuitive
solution turns out to be right: it doesn't matter! (except for the
limits)

Back to our little riddle:
There is now upper limit given here. This is what startles us. If
there were no limit given at all (i.e. including negative numbers) it
would be clear that all gain is equal to all loss. But we've got a
lower limit here at $0. So the riddle works by suggesting that it
won't average itself out (which it does, as we've proven). Of course,
in the real world there will always be an upper limit.

So, the logical strategy for gaining the biggest amount of money would be:

1. if you've got an odd amount of money, get the other envelope
2. if you've got an even amount of money, keep your envelope, it
doesn't matter, you won't gain or loose money by choosing the other
one.
3. (additional) if your envelope contains more that one third of the
total amount of money on earth (or, alternatively: more than one third
of the amount of money you think the test conductor can get). KEEP IT!
KEEP IT! KEEP IT! Buy an island in the carribean and be sure to send
me 10%!

Fabian

P.S.: I've written my answer before hailstorm posted his
clarification. But I still think my answer is correct.

very thoughtful reasoning fsiegel, but i do not understand how you
conclude steps 1 and 2 of your strategy from the notion of the limits
and its affect on "averaging" out your expected gain/loss.

You're right, I made a bit of a jump there. I just wanted to sketch
the concept of the proof.

a) Let's assume I get two envelopes for each number n between 1 and L (the
   upper limit), once the other envelope contains n/2 Dollars, the other time,
   it contains 2n Dollars. (except for those cases when n is odd, because n/2
   is not an integer)

b) if I always keep my first envelope, I will get for any even value m: 2*m

c) if I always trade my envelope, I will get m/2 + 2*m .  BUT (as shown above)
   I will always get m (exactly once) when I traded my m/2 evelope with the
   second containing m, and I will get m (exactly once) when I traded my 2*m
   evelope with the second containing m. That sums up to EXACTLY 2*m, because
   m has exactly two neighbours that are either m/2 or 2*m.

d) This is true except for two cases:
 i) m is bigger than L/2 (that's because 2*m would be larger than the limit L)
 ii) m is not even.

e) as there is no upper limit L given, d.i) is not important to us, i.e. I
   will get all even values exactly twice.

f) in all cases I get an odd value j, the result is easy, as there is no
   preceeding value j/2, the other envelope HAS to be 2*j, so I need to
   trade. Additionally, j also "contributes" so that 2*j again has exactly
   one predecessor (in that case j) and one successor 4*j.

g) this also shows another facett for the proof of this argument: every odd
   number is the "foundingstone" for an infinite number of even values m, that
   all have one successor 2*m and one predecessor m/2. Also all even number
   have exaclty one such "foundingstone".

h) we have now proven that for every even value, the difference between
   trading and not averages itself out with the help of
    i) the odd number at the beginning of the sequence
    ii) infinity
   and that every odd number doesn't have a predecessor and therefore is not a
   good value to keep.


I hope this clarifies it a bit, it's not a perfect proof for writing
down, but I think there's not much missing. I might have been a little
bit repetitive, but I'm a bit in a hurry. If you won't believe it,
writing a small computer program for simulating it, might clarify what
I meant.

Fabian

Addendum:
step 3 of my strategy: it's clear from the above that it really should
be "more than half of the upper limit".. however.. in a real world, he
needs to have all money present on the table, so this reduces to "more
than one third of the total amount of money available"

fsiegel-ga,

I'm afraid that you are also guilty of a false assumption:  that you
will have to open envelope B.

Nowhere in the question is this stated.  And, as I have shown above,
the potential value of envelope B in its unknown, unopened state is
$10, compared with the known $8 in envelope A.

So as I made mention to in my answer, if you can find someone to sell
the envelope to, you have a 100% chance of making more money using
envelope B than by keeping what you know is in envelope A.

Hailstorm,

you are right, but only under the assumption that you'll find soomeone
who is willing to risk the 50% chance of losing money. (granted: there
are many people out there who would risk this)

If you indeed can find someone and you'll draw an envelope only once,
then that's a correct solution.
But you might need to convince someone to do so. Which would be very
easy, as he would be guaranteed to make $1/envelope over the time, if
he did that for a statistically relevant number of turns.

But.. if repeating this process really IS an option, then why not keep
it and keep your potential $10? The answer is: you should, because (it
might not have been obvious from my proof) you *will get them*. My
proof only showed that you will get them whether or not you trade the
envelope.

So, effectively, you will lose money by selling the envelope to another guy.

Fabian

Another false assumption you're making is that you'll have an endless
number of chances at this.  Although I would love to have mysterious
benefactors give me infinite chances to choose between envelopes with
money in them, I am assuming that this is a one shot deal.

For this case, with my sell-the-envelope strategy, you have a 50%
chance of making more money than exists in either envelope!  The other
50% of the time, you still make more money than the lowest price
envelope.  Whereas if you choose to open the envelope, 50% of the time
you will have the lowest money value you can possibly get.

By the way, if you sell the envelope for under $10, you are still
selling that person something that is greater in value than the
purchase price.  When you consider the millions of people who purchase
lottery tickets, bet on horses, or play the slot machines, all of
which have potential values *less* than their purchase price, I think
that finding a buyer shouldn't be too difficult.

I totally agree with you, and that's what I've already said before.
If you only get to pull an envelope once, you only need someone to buy
the other potential $10 envelope from you. Like I already said.. many
people would do so.

But to be honest, you would have to tell him:
"Hello, I'm a maths student at MIT and I'm not willing to risk the 50%
chance of losing $4 versus winning $8." (Because that's what it
essentially is) "So I ask you, are YOU willing to risk the 50% chance
of losing $5 versus winning $7?"

Like I already said.. many people would do so.. no question.
But on the other hand.. I'm no specialist in psychology or marketing,
so I hope that said MIT-student (jellojoe) will tell us what his
professor really wanted to hear.

Fabian

I certainly hope jellojoe comes back to tell us how it all turned out.
 I have enjoyed the mental excerises with him and everyone who has
contributed to this question!

This is great reading you guys going back and forth, I'm glad there is
so much interest in this problem.  I especially like it because my
professor let me hang on to the money and the other envelope until he
says he will reveal the answer.  I am assuming within the next few
weeks he will let us know what the answer is.....I think he is holding
off on the answer until we learn some technique in class that will
help us understand what the answer is.

I figure if I drop the class I can make up to $24, not too bad, haha,
but I don't think I would do that.  I was thinking of taking the money
from the envelope too and leaving a note inside that reads "You forgot
to take into account the probability of Joe taking the
money"......then again, I don't see myself doing that either....so i
guess I'll have to wait until he tells me to bring in the envelope one
day.....I'll keep you posted.

oh yeah, i also tried holding the envelope up to a light (its one of
those yellow envelopes) and i guess he put an envelope inside an
envelope so I couldn't see what is inside.  I tried shaking it too, to
get the bills to seperate, but no luck, I figure if i see three bills
in there, then there is no way there are 4 dollars in the envelope, I
thought i saw only three, but two might have been stuck together

By dumb luck I was reading my probability textbook tonight and it
contained the same problem posed in my discrete math proofs
course....so just by chance I got an answer to this question from
another class!!!! talk about dumb luck!

I won't post the answer here because it is too long to type, but
hailstorm was on the right track to the answer.  The knowledge of a
limit would also change the problem, so if you can guess an upper and
lower limit the answer changes, but if there is no limit then it is
always better to switch....if you want to look at the answer get your
hands on "Introduction to Probability" by Dimitri Bertsekas and John
N. Tsitsikilis on page 107.  ISBN 1-886529-40-X

jellojoe: Unfortunately, I don't have the book the book you mentioned,
but I dug in my bookshelf for the example that had been on my mind all
along: The St. Petersburg Paradox. The book I have is John A. Rice:
"Mathematical Statistics", 2nd ed and you can find this example on
page 113.

"A gambler has the following strategy for playing a sequence of games: 

- he starts off betting $1; 
- if he loses, he doubles his bet; and he continues to double his bet
until he finally wins.

To analyze this scheme, suppose that the game is fair and that he wins
or loses the amount he bets. (For example, when he bets $8, he wins
another $8 with p = 1/2 and loses the money with p = 1/2).

At trial 0, he bets $1; if he loses, he bets $2 at trial 1, and if he
has not won by the k-th trial, he bets $2^k. When he finally wins, he
will be $1 ahead, which can be checked by going through the scheme for
the first few values of k. This seems like a foolproof way to win $1.
What could be wrong with it?"

The answer is fairly obvious when you think about it for a while.

The fundamental issue behind this problem is the probability
distribution underlying the amounts of money in the envelopes.  In
stating that, having picked one envelope and looked inside, there is a
probability of exactly 0.5 that the other envelope contains half as
much, and a probability of exactly 0.5 that the other envelope
contains twice as much, there is a tacit assumption that the
distribution is uniform.  But if it is uniform over all integers from
zero to infinity, the expectation value of the amount of money in the
evelopes in infinite.  That is, there is zero probability of finding a
finite amount of money in an envelope.  So, to be realistic, we have
to pick a probability distibution function that eventually goes to
zero as the amount of money increases.  Once we do this, it is no
longer true that the probabilities of halving or doubling your money
are equal.  So the answer to the question is that it is impossible to
answer without more information on the probability distribution
describing the possible amounts of money in the envelopes.

There is no limit on the amount of money possible in the envelopes,
but in this case we know what the possibilities are for dollar
amounts, so i was asking what the best strategy is given that we know
one envelope contains 8 dollars.

jellojoe:
nice to see that you seem to have solved it.

But I'm curious.. obviously, my solution has to be false. At the
moment I just can't figure out why. Does anyone care to help me with
that? I supppose I handled infinity incorrectly.

Unfortunately I can't get my hands on the textbook you mentioned. It's
not available in the entire city.

I also greatly enjoyed this mental exercise, it was fun discussing it.

Fabian

http://www.math.hmc.edu/funfacts/ffiles/20001.6-8.shtml

From the link given by racecar:

"For instance, suppose that amount of money in the two envelopes
is($2k,$2k+1) with probabilty (1/2)k, for each integer k>0. It is a
fun exercise to check that no matter what you have in your envelope,
the other envelope has higher expected value, and you should switch!"

I'll claim victory here.  ;-)

See, that answer is similar to the one given in the book i wrote down.
 The book goes into a few more cases and details than the website, but
yet I am still confused.... first it says there is a paradox, but then
it never gives a definitive answer, it seems like the one case the
website talks about is you already know whats in both envelopes which
makes no sense, how can you know what is in both envelopes?? the
problem never stated that, and the second method with the
2^(something), whatever it was....well thats nice and all, but its not
an overall answer.....grrr to mathematicians and their inability to
explain things in english.....I swear, mathematicians will know that a
solution exists and that is good enough for them, but not good enough
for an engineer like me