Earlier someone posted the “Monty Hall Problem,” which has been done to death here. Here is another brain-twisting statistical problem to think about:

Imagine someone offers you a choice between two envelopes. You pick an envelope and find that it contains $1000 dollars. The person then reveals that one of the two envelopes contains twice as much money as the other, and offers you the opportunity to switch. There are two equally-likely possibilities:

-you have the envelope with more money, in which case you would lose $500 by switching
or
-you have the envelope with less money, in which case you would win an extra $1000 by switching

Since switching would result in a ½ chance of winning $1000 and a ½ chance of losing $500 dollars, this would probably seem like a statistically good bet to you; the reward is proportionally greater than the risk. So you would likely switch.

To put it more formally, if the value of your envelope is X dollars and you know that one envelope has twice as much money in it as the other, then the other envelope has a statistical value of ½ * 0.5X + ½ * 2X = 1.25X.

The person running the game has given you new information indicating that the other envelope has a greater statistical value, so you should switch. Or has he? What if the person running the game told you at the beginning that one envelope had twice as much money as the other? Would you still switch from your initial choice if the host offered you the chance? Since the above equation should be valid for any value of X, it would seem that this problem would indicate that you should always switch envelopes, regardless of your initial choice. In fact, after you have switched you can apply exactly the same analysis to justify switching back to your original choice! Does this make sense?

I'd keep the money....thats $1000 dude...seriously! :D

Ah, but you still get to take home $500 even if switching is the "wrong" choice...

You may walk away with $500 but you will feel like a dumb ass for quite awhile.
Stick with the money you have becuase its the secure option.

Interesting problem... It's tricky because it's presented as a "double or half" bet... but is it really?

Here's an easy situation:

I offer you the chance to play a game.
Flip a fair coin, and if it comes up heads I give you $2000. If it comes up tails I give you $500.
It costs $1000 to play.

In this case, it's clear that playing the game is good sense. If you play many times, chances are excellent that you'll break the bank.


So what about the envelope problem? Exactly how does it differ from this problem, and how do those differences invalidate the "switching is better" argument?

So what about the envelope problem? Exactly how does it differ from this problem, and how do those differences invalidate the "switching is better" argument?Honestly, I am not sure. Clearly if it costs X to play a game that has a 50% chance of paying out 2X and a 50% chance of paying out 1/2X, it will be in your favor to play it.

This should be true for any value of X, so if you define the amount of money in the envelope that you have chosen as X then it would seem to me that by switching you are playing a game that costs you X but will pay out 2X or 1/2X.

I think the trick might be that X is not an independent value in the envelop game.

This looks like an example of the "sure thing" paradox.

Another example:
I am going to give you the choice of
(a) Picking envelope A, that is known to a certain amount of money, or
(b) Picking one of envelop B or C, one of which contains nothing and the other, $2000. But you don't know which is which.

For what value in envelope A would you consider the choice to be a 50-50 deal?

Statistically, the answer is $1000, since the expected winnings from choice (b) is $1000 and the expected winnings from choice (a) is whatever value you decide is "fair". Almost everyone would take the $1000 sure thing over the gamble without batting an eye. The value most people say would make them think the gamble is equivalent to the sure thing is much smaller than $1000.

BTW, this is how banks get away with the tiny interests they pay on savings accounts. The savings account is a "sure thing", and the stock market definitely is not.

For the original example:

Assuming the person always reveals that one of the two envelopes contains twice the money and there is no slight of hand involved, switching is the best bet.

You have $1000 in your hand. For all intents and purposes it is yours. Picking the other envelope is a gambling problem. Boiled down, your bet is $500. The return is your original bet plus $1000. In other words, you are putting in 1/3 of the money into the "pot".

Since the choice of the envelope is fair, the odds are 1:2 that the other envelope contains the higher amount.

Picked envelope with higher amount: 1/2
Switch: always lose
Stick: always win

Picked envelope with lower amount: 1/2
switch: always win
stick: always lose

You are betting 1/3 of the money for 1/2 of the odds. Any gambler will tell you, that's a good bet. ;)


If the person is not required to reveal that one envelope contains twice as much money as the other, then the probability of him revealing that information should be considered.

Assuming he always reveals the additional information when you pick the higher amount, but when you pick the lower amount he his choice to offer the information is evenly distributed (1/2; 1/2):

Picked envelope with higher amount (information revealed): 1/2
Switch: always lose
Stick: always win

Picked envelope with lower amount (information revealed): 1/4
switch: always win
stick: always lose

Picked envelope with lower amount (information not revealed): 1/4
Always loses

In this case you are betting 1/3 of the money for 1/4 of the odds. Any gambler will tell you, that's not a good bet. ;)

It seems to depend on my being willing to believe that the benefactor is now lying to me. If I believe I may be lied to, I will keep my $1000 which is already in my hands.

yep, with $1000 in your hand you have a 100% chance of keeping it so statistically it is safer to keep it. Because if you switch you run a chance of loosing $500.

I think the trick might be that X is not an independent value in the envelop game.Could you be a little more explicit? I'm still not understanding the trick, although there clearly seems to be one.

Assuming the person always reveals that one of the two envelopes contains twice the money and there is no slight of hand involved, switching is the best bet. Although this seems intuitively correct, it is wrong. You can easily prove it to be wrong by writing a program that randomly places X amount in envelope A and 2X in envelope B, then randomly chooses between A or B. Have the computer play a large number of rounds with itself where it keeps whatever envelope it initially picks, then have it play a large number of rounds where it switches to the other envelope. You will find that in the long run you win the same amount of money either way; the average winning will always converge to 0.75X

The question is, why is the intuitive analysis that gives a value of 1.25X for the other envelope wrong?

Could you be a little more explicit? I'm still not understanding the trick, although there clearly seems to be one.

"X", the value in the envelope you chose, is determined by your choice - it is not an independent variable, which I think might make the calculations in the intial post invalid. I'm too fuzzy on the formalism to be sure.


I am sure that it is safer to choose a truly independent variable to base the analysis on, such as the value in the lesser envelope.

If A is the lesser value, then there are two ways the game can pan out, each with a 0.5 probability:

1) You chose A. If you switch, you get 2A, if you don't, you get A.
2) You choose 2A. If you switch, you get A, if you don't, you get 2A

Note that X = A in one case, and X = 2A in the other.

Although this seems intuitively correct, it is wrong. You can easily prove it to be wrong by writing a program that randomly places X amount in envelope A and 2X in envelope B, then randomly chooses between A or B. Have the computer play a large number of rounds with itself where it keeps whatever envelope it initially picks, then have it play a large number of rounds where it switches to the other envelope. You will find that in the long run you win the same amount of money either way; the average winning will always converge to 0.75X

The question is, why is the intuitive analysis that gives a value of 1.25X for the other envelope wrong?

It's not wrong. You are misunderstanding the problem.

The problem assumes that a constant amount is always choosen first. The first envelope choosen contains $1000 (1/1). The other envelope can then contain either $500 (1/2) or $2000 (1/2).

There is no randomness for the value of the first choice. The only randomness is whether the second envelope contains more or less than the first.

Edit:

That being said:

Assume for all of the following that the player retains no information from game to game concerning the amounts in the envelopes.

If the envelopes only contain $500 and $1000 and you are able to pick either as an intial choice, then yes, which envelop you pick does not matter and the winnings converge at $750x.

Alternately, the envelopes only contain $1000 and $2000 and you are able to pick either as an initial choice, then again which envelope you pick would not matter and your winnings would converge at $1500x.

If the envelopes could contain either $500 and $1000 or $1000 and $2000 and are able to pick between either in your initial choice, still again your winnings would converge at $1125x.

removed second edit due to slowness of posting

The problem assumes that a constant amount is always choosen first.
I disagree. The problem presents the amount as a particular instance only:


"Imagine someone offers you a choice between two envelopes. You pick an envelope and find that it contains $1000 dollars. The person then reveals that one of the two envelopes contains twice as much money as the other..."

I think it is clear that it is just as likely that the other envelope (which contains $500 or $2000) could have been chosen.

Although this seems intuitively correct, it is wrong. You can easily prove it to be wrong by writing a program that randomly places X amount in envelope A and 2X in envelope B, then randomly chooses between A or B. Have the computer play a large number of rounds with itself where it keeps whatever envelope it initially picks, then have it play a large number of rounds where it switches to the other envelope. The average winning will always converge to 0.75X.

The question is, why is the intuitive analysis that gives a value of 1.25X for the other envelope wrong?

The intuitive analysis in this case is correct. Your Monte-Carlo does not test the envelope problem.

"X", the value in the envelope you chose, is determined by your choice - it is not an independent variable, which I think might make the calculations in the intial post invalid.


That is correct.

The expected value of the other envelope is indeed 1.25 X:
(1/2)*(X/2) + (1/2)*(2X)

A properly constructed Monte-Carlo experiment bears this out. The correct experiment is to have some fixed value X, say $1000, that represents the value of the envelope given to the player. Choose an envelope N times, either switching or staying each time. If the strategy is stay, just accumulate X into the winnings for each choice. If the strategy is switch, pick a random number between 0 and 1. If the number is less than 0.5, accumulate X/2 into the winnings, otherwise accumulate 2*X. You will find that the earnings from the stay strategy are of course N*1000 but with the switch strategy, the earnings are about N*1250 (the expected earnings are N*1250 plus a zero-mean random walk).


This problem is a good example of the "sure thing" paradox. A number of posters chose to stay even though the expected winnings are considerable better with the gamble. This is not to say those posters are stupid. It is a human thing to choose the sure thing. In a graduate statistics class on multi-criterion decision making, a majority of the students placed a substantial value on the sure thing. Needless to say, those students knew the odds.

Here's a twist to the envelope problem where a lot of people don't choose the sure thing.

You have two choices: one is not to play the game (that's the sure thing in this case). If you decide to play the game, you pay a small amount (say one dollar) for an envelope that you know contains either nothing or $100 million. However, the odds the envelope contains the $100 million is only 1 out of 200 million. The odds the envelope is empty is just shy of 1 out of 1 (1 out of 200 million shy, to be precise). So -- do you want to play or not?

I disagree. The problem presents the amount as a particular instance only:

"Imagine someone offers you a choice between two envelopes. You pick an envelope and find that it contains $1000 dollars. The person then reveals that one of the two envelopes contains twice as much money as the other..."

I think it is clear that it is just as likely that the other envelope (which contains $500 or $2000) could have been chosen.

Assuming the values in the envelopes were known such that the player knew that any pair of envelopes contained either ($500 and 1000) or ($1000 and $2000), the pairs of envelopes were evenly distributed (500-1000 1/2; 1000- 2000 1/2), the initial pick was random, you see the value in the envelope you choose and the choice of the exchange was always offered.


500 value: 1/4
Switch: always wins $1000
Stick: always wins $500

1000 value: 1/2
Switch: Wins 2000 1/2 (1/4)
Switch: wins $500 1/2 (1/4)
Stick: Always wins $1000

2000 value: 1/4
Switch: always wins $1000
Stick: always wins $2000

Using the information for possible values, if you picked always switch on $500 but always stick on $1000 and $2000
when you pick the envelope with $500 (1/4) you will always win $1000.
when you pick the envelope with $2000 (1/4) you will always win $2000.
When you pick the envelope with $1000 (1/2) you will always win $1000.

(1000 * 1/4) + (2000 * 1/4) + (1000 * 1/2) = $1250.


Using the information for possible values, if you picked the always switch on $500 and $1000 but stick on $2000:
when you pick the envelope with $500 (1/4) you will always win $1000.
when you pick the envelope with $2000 (1/4) you will always win $2000.
When you pick the envelope with $1000 (1/2) you would win $500 (1/2) or $2000 (1/2).

(1000 * 1/4) + (2000 * 1/4) + (500 * 1/4) + (2000 * 1/4) = $1375.

Denote the actual dollar amounts placed in the envelopes by Y and 2Y.

Denote the dollar amount in the initial envelope by X. Assume that P(X=Y) = P(X=2Y) = 1/2. The expected value of X is Y*P(X=Y) + 2Y*P(X=2Y) = (3/2)Y. This is the expected return of the "never switch" strategy.

Denote the value of the alternative envelope by Xbar. The expected value of Xbar is then 2Y*P(X=Y) + Y*P(X=2Y) = (3/2)Y. This demonstrates, then, that the "never switch" and "always switch" strategies give equal returns.

It is only when P(X=Y) is NOT equal to 1/2 that one strategy is preferable to the other. It should be mentioned that, in such a case, the player would have to know in advance which envelope was more likely in order to choose the proper strategy. If the player is ignorant of P(X=Y), he will be forced to assume that it is 1/2, and thus have no reason to favor one strategy over the other.

Consider next the strategy of switching envelopes some fixed proportion of the time, denoted by Q. Denote the value of the envelope that is finally chosen by Z. Then, P(Z=Y) = (1-Q)*P(X=Y) + Q*P(X=2Y) and P(Z=2Y) = Q*P(X=Y) + (1-Q)*P(X=2Y). Note that if P(X=Y) = 1/2, it follows that P(Z=Y) = P(Z=2Y) = (1/2), and so the expected value of Z is (3/2)Y. This proves that no switching strategy produces a greater expected return than any other, and so one may as well just keep the initial envelope.

Note that all of the above results are independent of the relationship between the dollar amounts in the envelopes. That is, the envelopes could instead contain amounts Y1 and Y2, and the expected return of any switching strategy would then be (Y1 + Y2)/2. Note that Y1 and Y2 need not be positive.

The envelope switching problem is not intended to illustrate any sort of paradox, but rather to test the reader's understanding of basic probability. The point here is to resist the temptation to phrase the problem in terms of X, the observed value, which leads to seeming paradoxes stemming from the red herring that one envelope is twice the other.

Denote the actual dollar amounts placed in the envelopes by Y and 2Y.

Denote the dollar amount in the initial envelope by X. Assume that P(X=Y) = P(X=2Y) = 1/2. The expected value of X is Y*P(X=Y) + 2Y*P(X=2Y) = (3/2)Y. This is the expected return of the "never switch" strategy.

Denote the value of the alternative envelope by Xbar. The expected value of Xbar is then 2Y*P(X=Y) + Y*P(X=2Y) = (3/2)Y. This demonstrates, then, that the "never switch" and "always switch" strategies give equal returns.

It is only when P(X=Y) is NOT equal to 1/2 that one strategy is preferable to the other. It should be mentioned that, in such a case, the player would have to know in advance which envelope was more likely in order to choose the proper strategy. If the player is ignorant of P(X=Y), he will be forced to assume that it is 1/2, and thus have no reason to favor one strategy over the other.

Consider next the strategy of switching envelopes some fixed proportion of the time, denoted by Q. Denote the value of the envelope that is finally chosen by Z. Then, P(Z=Y) = (1-Q)*P(X=Y) + Q*P(X=2Y) and P(Z=2Y) = Q*P(X=Y) + (1-Q)*P(X=2Y). Note that if P(X=Y) = 1/2, it follows that P(Z=Y) = P(Z=2Y) = (1/2), and so the expected value of Z is (3/2)Y. This proves that no switching strategy produces a greater expected return than any other, and so one may as well just keep the initial envelope.

I have 10 pairs of envelopes with the following values in each pair:

Y, 2Y
2Y, 4Y
4Y,8Y
8Y, 16Y
16Y, 32Y
32Y,64Y
64Y,128Y
128Y,256Y
256Y,512Y
512Y,1024Y
I randomly determine which pair to present to you.

What should your betting strategy be if you draw Y or 1024Y?

The correct experiment is to have some fixed value X, say $1000, that represents the value of the envelope given to the player.
Hi DH,
I don't think that's an accurate representation of the problem at hand, in which the value of $1000 in the chosen envelope was happenstance. If the other envelope happened to be chosen first, it obviously would not have contained $1000.

This is the only question I have to ask:

"What are the rules for this game and why should I play it?"

If some random guy on the street offers me a choice of 2 envelopes and tells me I can keep what's inside. I pick one and open it up and see $Y in the envelope, and then says that one of the two envelopes contains twice as much money as the other. I am walking off with his $Y.

If I come across "an envelope" game at some establishment and am placing $$ down to purchase an envelope, I certainly am not going to put money down without knowing the parameters of the game.

Assuming the values in the envelopes were known such that ...
You can get any result you want by setting assumptions appropriately, but you'd be answering a different question.

If some random guy on the street offers me a choice of 2 envelopes and tells me I can keep what's inside. I pick one and open it up and see $Y in the envelope, and then says that one of the two envelopes contains twice as much money as the other. I am walking off with his $Y.

What if the random guy offered to sell you the other envelope? How much would you be willing to pay for it?

What should your betting strategy be if you draw Y or 1024Y?
How would the drawer know that they had drawn a minimum or maximum value? What if there is no specified minimum or maximum?

What if the random guy offered to sell you the other envelope? How much would you be willing to pay for it?

I'd be half way to the donut shop before he finished his sentence. ;)

Ok that wasn't a particularly fair answer.

A. The guy just handed a stranger $1000. Thus the guy is potentially unstable.
B. The guy just realized that the stranger is walking off with his $1000. Thus the guy is potentially angry.
C. If the guy is offering an envelope with $2000 to the guy that is walking off with his $1000, he is unstable.
D. If the guy is offering an envelope with $500 to the guy that is walking off with his $1000, he thinks he can get his $1000 back by eluding to the potential that the envelope contains $2000. Not too unstable but up to something.

Regardless of any of these, I am walking off with his $1000 before he realizes that the wallet he just took from my pocket is completely empty.

How would the drawer know that they had drawn a minimum or maximum value? What if there is no specified minimum or maximum?

If the minimum and maximum were specified, how is "The player gets to look at the value before deciding to keep it or switch it". If the minimum and maximum were not specified, I would suggest not playing the game if it cost you $$ and to walk off with the guy's cash if it didn't. ;)

Hi DH,
I don't think that's an accurate representation of the problem at hand, in which the value of $1000 in the chosen envelope was happenstance. If the other envelope happened to be chosen first, it obviously would not have contained $1000.

This is a correct representation of the problem at hand. I would be willing to bet my job on it -- and one of my jobs is setting up Monte-Carlo experiments.

A properly construct Monte-Carlo experiment must be based on the given parameters. For example, when I am asked to investigate whether a disconnected piece of equipment will recontact a space vehicle due to initial relative velocity (somewhat random), orbital mechanics effects (deterministic), differential drag (somewhat random), etc., a proper Monte-Carlo simulation must start with the piece of equipment disconnected and proceed from that point. That the odds the piece of equipment becomes disconnected in the first place is very small is irrelevant.

Similarly, that the odds of being given an envelope containing $1000 by a random stranger is negligible is also irrelevant. A Monte-Carlo experiment must emulate the parameters of the game, which are
two envelopes exist, one of which contains twice the dollar amount of the other;
the envelope originally given to the player contains $1000; and
the player can keep one of the two envelopes--either the original envelope with the known quantity or the other with an unknown quantity.

Changing the amount of money in hand at the onset invalidates the Monte-Carlo experiment. That is how Nasor got the wrong results from his experiment.

The original problem assumed a "fair" host: equal odds of the other envelope containing half or twice the amount in hand. Here's a modification to the problem that guarantees that assumption:

Background: You are a contestant on a TV game show. Any winnings you walk away with is chump change compared to the advertising revenues. If you walk away with the booby prize, so much the better. One reason the audience loves the show is because they get to see participants give up a sure thing and lose.

The host hands you three envelopes and $3500. One of the envelopes is labeled $1000. The other two are unmarked. The host asks you to put money in each of the envelopes and then seal each envelope. Per his instructions, you put $1000 in the labeled envelope, $500 in one of the two unmarked envelopes, and $2000 in the other unmarked envelope. His pretty assistant thoroughly mixes up the three envelopes and lays them face-up on a table. You now get to choose one of the three envelopes. To ensure that the game was fair, the contents of all three envelopes will be revealed after you make your choice. However, you only get to keep the contents of your chosen envelope.

Which envelope do you choose?

DH:

Suppose the host allows you to play again, this time knowing from the beginning that one envelope has twice as much money as the other. The amounts in this new round are not related to the amounts in the previous round (meaning if you get $500 in your first envelope you can’t assume that you have the lower amount). Using your reasoning, it would seem that it is always statistically beneficial to switch to the second envelope, regardless of which one you pick initially. You wouldn’t even need to look in the envelope, you could just say “I pick envelope A, which has some unknown dollar value X. But the statistical value of the other envelope is 1.25X, so I should switch to envelope B.” Does that position make logical sense? Do you think that in the long run you would make 25% more in such a game if you were to always pick one envelope randomly and then switch to the other vs. picking one envelope and sticking with your first choice?

Nasor,
There has been a bit of ambiguity in how you stated the game. That's why I restated it as a three envelope game.

Here's one game: The host lets you choose among two envelopes which contain pre-ordained amounts of money X and 2*X. My a-priori expected winnings given that I get to choose an envelope are

E(winnings|random choice) = 0.5*X + 0.5*(2*X) = 1.5*X

I open the original envelope and see Y dollars:

E(winnings|initial choice made) = Y

I don't know if Y=X or 2*X. If the game is fair, that Y=X or 2*X is a 50-50 proposition. What happens if I switch? The correct calculation is

E(winnings|switch) = P(Y=X)*2*X + P(Y=2*X)*X = 0.5*2*X + 0.5*X = 1.5*X

In other words, switching has no value.

It is indeed an error in this case to compute

E(winnings|switch) = P(Y=X)*2*Y + P(Y=2*X)*Y/2 = 0.5*2*Y + 0.5*Y/2 = 1.25*Y

In this case, I, like many others, place some premium on the sure thing and would choose not to switch.


The other game is that the host gives you an envelope containing Y dollars. He then randomly puts Y/2 or Y*2 dollars in another envelope and gives you the choice of keeping your original choice or switching to this other envelope. This is how I interpreted your original post. In that case, switching gives the better odds. Suppose I stay. Then

E(winnings|stay) = Y

Suppose I choose to pick another envelope instead. Denoting the quantity in the other envelope as Z,

In this case

E(winnings|switch) = P(Z=Y/2)*Y/2 + P(Z=Y*2)*Y*2 = 0.5*Y/2 + 0.5*Y*2 = 1.25*Y

A zero-mean random walk goes along with those better odds; I might well "lose", even if given the chance to play the game many times. Nonetheless, I would switch in this game.

Nasor,
There has been a bit of ambiguity in how you stated the game. That's why I restated it as a three envelope game.

Here's one game: The host lets you choose among two envelopes which contain pre-ordained amounts of money X and 2*X. My a-priori expected winnings given that I get to choose an envelope are

E(winnings|random choice) = 0.5*X + 0.5*(2*X) = 1.5*X
This is the scenario I was suggesting.

The other game is that the host gives you an envelope containing Y dollars. He then randomly puts Y/2 or Y*2 dollars in another envelope and gives you the choice of keeping your original choice or switching to this other envelope. This is how I interpreted your original post. In that case, switching gives the better odds. Well, I think it was clear in my original post that the "host" allowed you to choose between two envelopes that already contained x and 2x amounts of money, then offeres you the chance to switch once you know the value of your envelope (but don't know if it's the smaller or larger amount).

Well, I think it was clear in my original post that the "host" allowed you to choose between two envelopes that already contained x and 2x amounts of money, then offeres you the chance to switch once you know the value of your envelope (but don't know if it's the smaller or larger amount).

It wasn't clear to me.

BTW, with this clarification, me previous bet is hereby rescinded.

Ok, here is "my envelope game":

Set up:

A large stack of envelopes, the number of which is n.
In each of these n envelopes, there are 2 other envelopes.
In each of these other envelopes there is a point value. 2^n and (2^n )/2. (Before randomization the first large envelope in the stack would contain 2^1 and (2^1)/2; the fiftieth would contain 2^50 and (2^50)/2)

The game play:
The stack of large envelopes is randomized and one is picked.
The smaller envelopes are removed from the larger and randomized.
The player pickes one of the two smaller envelopes, and reveals its point value.
The player can now choose to add the known point value to his score (opened envelope), or the unknown point value to his score (the unopened envelope).
If the player chooses the unknown point value, the unopened envelope is opened and the point value it contains is added to the players score.
Both envelopes are closed, placed back in the larger envelope, and returned to the stack.

The player may play as long as he would like.

With the information given and the information gained during play, is it possible for a player to maximize his score if he plays an arbitrarily large number of games?

Ok, here is "my envelope game":
Set up:
A large stack of envelopes, the number of which is n.
In each of these n envelopes, there are 2 other envelopes.
In each of these other envelopes there is a point value. 2^n and (2^n )/2.

With the information given and the information gained during play, is it possible for a player to maximize his score if he plays an arbitrarily large number of games?

I am assuming the envelopes are unmarked. There is no way to tell which of the big envelopes contains the big jackpot, and no way to tell which of the small envelopes inside a big envelope contains the better amount.

Switching is very harmful if you draw 2^50 points as the other envelope is now known to contain 2^49 points. Obviously one should stay in that case. Similarly, switching is slightly beneficial if you draw a 1, as the other envelope is known to contain 2 points. One only need analyze the remaining 48 cases (2^2 to 2^49). In these cases, staying pays what the envelope says but switching improves the payoff by 25%. Thus one should switch on all but the big jackpot.

E(winnings|always stay) = (3*2^50-3)/100
E(winnings|always switch) = (3*2^50-0.5)/100
E(winnings|switch on all but 2^50) = (3.5*2^50-4)/100

It wasn't clear to me.

"Imagine someone offers you a choice between two envelopes... "

BTW, with this clarification, me previous bet is hereby rescinded.
You're just lucky I'm not looking for a job :D

In these cases, staying pays what the envelope says but switching improves the payoff by 25%. Thus one should switch on all but the big jackpot.

What would your strategy be if the maximum value for n was unknown to the player?

I think the weighted payoff for staying on the maximum envelope exactly matches the weighted payoff for switching on all other envelopes.

Therefore if the maximum value is unknown, staying or switching on any value is of equal value for the first play. After the first play, I'm guessing that the best strategy would be to stay if the value is the largest seen so far, otherwise switch.

Actually, I don't think that's quite right for the first play.

Since the minimum value is known, there is a known payoff for switching if that value is drawn. My intuition says that to balance this, there should be a slight benefit to staying on the first draw if the minimum value is not drawn... but I haven't tried to prove it.

So, here's the modified strategy:
First play - switch if minimum value, otherwise stay.
Afterward - Stay if maximum seen so far, otherwise switch.

If the minimum value is unknown, then the same strategy applies except the first play has the same value for switching or staying.

Since the minimum value is known, there is a known payoff for switching if that value is drawn. My intuition says that to balance this, there should be a slight benefit to staying on the first draw if the minimum value is not drawn... but I haven't tried to prove it.

So, here's the modified strategy:
First play - switch if minimum value, otherwise stay.
Afterward - Stay if maximum seen so far, otherwise switch.

If the minimum value is unknown, then the same strategy applies except the first play has the same value for switching or staying.

Your intuition is right--unless the number of envelopes is infinite. For a finite number of envelopes, there is a finite chance you hit the big jackpot on the first draw.

I would simplify your algorithm by seeding the "maximum seen so far" with twice the minimum value prior to the first draw. Then the strategy is always to stay if maximum seen so far, otherwise switch. No special case is needed for the first draw.

Regarding the case where the minimum value is also unknown, I would modify your strategy for the first round with a bit of utility theory. Most people (me included) value money in a non-linear fashion. To illustrate, which of the following represents the most significant difference: winning 1 dollar vs 10 dollars, winning 10000 dollars vs 100000 dollars, or winning 100 million dollars versus 1 billion? All choices differ by a factor of ten. Except to someone who already has tens of millions of dollars, 100 million and 1 billion are more-or-less the same amount. I couldn't spend 100 million dollars in a lifetime, let alone 1 billion. Similarly, 1 dollar and 10 dollars are more-or-less equally worthless. It is the middle choice (10000 versus 100000) that represents the most significant difference to me.

The inflection point in my personal value-of-money curve dictates my choice on the first draw: I would switch if I drew some lousy value (e.g. 4 dollars, I don't care if I lose 2 of them) but stay if I drew something big (e.g., 32768 dollars; I would rather not take the chance of losing 16384 dollars should 32768 be the maximum).

Nice post, DH.