Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Two envelopes problem

en.wikipedia.org

Post reply on HN
Print view View original

51–60 of 96 posts

Re: Two envelopes problem

#51

Post by jamii »

staccatomeasure wrote: post #36
jamii wrote: post #28

Earlier quoted context omitted.

Sorry, I rushed it. Did the edit make it clearer?

No, quite the opposite unfortunately :(

I guess I skipped a lot of background knowledge :)

The quantity everyone is arguing about is 'the expected gain from swapping envelopes' (http://en.wikipedia.org/wiki/Expected_value). Informally, you might say 'the average gain from swapping envelopes'. The way you work this out is you take all the possible things that could happen and for each one multiply the probability of it happening by the amount you gain if it happens. For example, suppose we play a game where I toss a coin. If it's heads I give you $2 and if it's tails you give me $1. Your expected gain from playing this game is:

    E(Gain) = P(Heads)*Gain(Heads) + P(Tails)*Gain(Tails)
            = 1/2 * $2 + 1/2 * -$1
            = $1 - $0.5
            = $0.5
If you play the game repeatedly, your average gain will converge to the expected gain ie if you played the game a million times you would win pretty close t half a million dollars. That's called the law of large numbers (http://en.wikipedia.org/wiki/Law_of_large_numbers). That's why we care about expectation - it tells us what would happen on average over large numbers of repeated trials. It's also very simple to calculate and quite intuitive to reason about.

In the case of the two envelopes the problem comes from the fact that there are an infinite number of possible amounts in the envelope. It turns out that adding up an infinite series of numbers doesn't always behave the way you would expect eg

     1 + (-1  +  1) + (-1  +  1) ... = 1 + 0 + 0 ... = 1
    (1 +  -1) + (1  +  -1) + (1 ...  = 0 + 0 + 0 ... = 0
In the example above we are adding up the same numbers in both cases, but depending on how we group them we get different answers. The same thing is happening in the envelope problem. The different arguments in this thread are just different ways of adding up all the possible cases and they get different results. The actual problem here is that the theory of expectation only applies when the sum is well behaved (http://en.wikipedia.org/wiki/Absolute_convergence).

Because the expectation is not well-defined for the envelope problem the law of large numbers does not apply either. If you play the game millions and millions of times your average win per game will not settle down but will keep jumping around forever.

Like the Monty Hall problem (http://en.wikipedia.org/wiki/Monty_Hall_problem), it's interesting because even expert mathematicians often get the wrong answer if they don't carefully work it out step by step. It shows the value of having a formal system of probability to back up intuition.

Re: Two envelopes problem

#52

Post by olalonde »

RockyMcNuts wrote: post #27
EllaMentry wrote: post #4

That is a very long article based on flawed argument. Given no other information, assuming someone gave you 2 envelopes and told you one has $40 vs $20, common sense dictates choose 1 randomly and walk away - with no other information it is illogical to reason any other way. The chance you choose the lower value is 1/2. Now, if you are allowed to look inside the envelope (which gets introduced further down) then it b…

Suppose you restate it. You own a $100 stock. It has a 50% chance of doubling, and a 50% chance of going down 50%. Should you sell it, or hold onto it? Expected value of holding is ($200 + $50)/2 = $125 . So it seems like you should hold on! If you repeat that wager indefinitely, the standard deviation of the net wins (number of ups-downs) goes up according to a square root law. And the value of your stock goes up ex…

Javascript simulation (might freeze your browser so would be a good idea to run it in Node):

    var t = 100; for (var i = 0; i  0.5) { t = t * 2; } else { t = t / 2; } console.log(t); }
It's interesting how quickly the return goes from extremely small to extremely big amounts.

Re: Two envelopes problem

#53

Post by [deleted] »

jere wrote: post #48
olalonde wrote: post #35

Earlier quoted context omitted.

There is additional information in the Monty Hall problem: the host never opens the door with a car. In the two envelope's problem, the "host" merely restates the question no matter which envelope was chosen.

Folks, it's an analogy. An analogy compares two different things... trust me, I know they're different and I know in which ways. All I was saying is common sense doesn't get you far in the Monty Hall problem. It really doesn't: >[Vos Savant] received thousands of letters from her readers; 92% of the general public, 65% of universities, and many with PhDs, were against her answer. Thus, it's kind of silly to say we're…

[deleted]

Re: Two envelopes problem

#54

Post by thatthatis »

If it is possible to switch and gain on the average we could write a 10,000 or so iteration monte-carlo simulation of this switching algorithm to demonstrate the gains.

The envelope has either x or 2x. One envelope has amount z, but the agent doesn't know if z = x or z = 2x.

If it is true that not switching leads to an EV of 3x/2 but switching leads to a higher EV: then a single switch each round should come back with an average value of greater than 3x/2.

In the Montey Hall problem, we can code up such an agent to demonstrate that the naive intuition is wrong. However, in this case, regardless of how many times we switch, we still end up with an average value of 2x/3.

Therefore there is an error in the math that says that switching has a higher EV than staying.

Re: Two envelopes problem

#55

Post by scythe »

This is a fantastic and subtle paradox, and not at all taken to quick resolution. A resolution follows, first to spot a problem (if there is one) gets a cookie.

Consider the amount in the lower to be f(x), the higher to be x, given f(z) such that f(z) all distributions, as the problem clearly applies to all distributions. You open the first envelope, which contains A. The second envelope contains B. The challenge is to calculate the value of B.

First we must calculate x. The chance that A = f(x) is 1/2, the chance that A = x is 1/2. The average value of A is (x + f(x))/2, so the average value of x is [f+I]^{-1}(2A), where I is the identity function and [g]^{-1} denotes an inverse function.

Now we calculate B. The trick lies in this: both calculations must lie in the same reference frame. So B = x with probability 1/2, and B = f(x) with probability 1/2, giving us B = (x + f(x))/2.

The rest is plug-and-chug: B = ([f+I]^{-1}(2A) + f([f+I]^{-1}(2A))/2 --> B = [f+I]([f+I]^{-1}(2A))/2 --> B = 2A/2 thus B = A.

Therefore over all probability distributions that can be defined we have the average value of B equal to A in any case. A purely mathematical resolution is satisfying, but I am not in any case an epistemologist, so it may not satisfy people who take a different interpretation of math than me. It works, and I like it.

Re: Two envelopes problem

#56

Post by jamii »

jamii wrote: post #51
staccatomeasure wrote: post #36

Earlier quoted context omitted.

No, quite the opposite unfortunately :(

I guess I skipped a lot of background knowledge :) The quantity everyone is arguing about is 'the expected gain from swapping envelopes' ( http://en.wikipedia.org/wiki/Expected_value ). Informally, you might say 'the average gain from swapping envelopes'. The way you work this out is you take all the possible things that could happen and for each one multiply the probability of it happening by the amount you gain if…

If you want to learn more about this sort of thing there is an excellent textbook which teaches probability theory using randomised algorithms (eg uniform hashing, load balancing, queueing theory etc).

http://www.amazon.com/Probability-Computing-Randomized-Algor...

It's one of my favourite textbooks and it's full of powerful methods and intuitions for any programmer.

NINJA EDIT PLUG: If anyone wants to work through that book I would be more than happy to help out and answer questions (jamie@scattered-thoughts.net). I wouldn't mind a refresher myself and I've always found that explaining things to other people helps clarify my own thinking.

Re: Two envelopes problem

#57

Post by olalonde »

jere wrote: post #48
olalonde wrote: post #35

Earlier quoted context omitted.

There is additional information in the Monty Hall problem: the host never opens the door with a car. In the two envelope's problem, the "host" merely restates the question no matter which envelope was chosen.

Folks, it's an analogy. An analogy compares two different things... trust me, I know they're different and I know in which ways. All I was saying is common sense doesn't get you far in the Monty Hall problem. It really doesn't: >[Vos Savant] received thousands of letters from her readers; 92% of the general public, 65% of universities, and many with PhDs, were against her answer. Thus, it's kind of silly to say we're…

Sorry for misunderstanding you. I guess I lacked a bit of common sense...

Re: Two envelopes problem

#58

Post by jamii »

thatthatis wrote: post #54

If it is possible to switch and gain on the average we could write a 10,000 or so iteration monte-carlo simulation of this switching algorithm to demonstrate the gains. The envelope has either x or 2x. One envelope has amount z, but the agent doesn't know if z = x or z = 2x. If it is true that not switching leads to an EV of 3x/2 but switching leads to a higher EV: then a single switch each round should come back wit…

Go ahead and run a few million simulations of the problem and graph the running mean over time. You might be surprised :)

Be sure to use exact arithmetic (eg http://docs.python.org/2/library/fractions.html)

Re: Two envelopes problem

#59

Post by [deleted] »

sillysaurus2 wrote: post #38

I'd like to offer my own humble solution. Maybe it's flawed. Maybe you can embarass me. :) Here it is: the goal is to choose a strategy which statistically maximizes our return. I.e. strategy A is superior to strategy B if it yields higher returns after, say, 1,000,000 iterations. So there are two envelopes, X and 2X. You select one, then you're offered a chance to change your selection. What do you do? Let's write o…

[deleted]

Re: Two envelopes problem

#60

Post by Mazz »

Just read it... Here is what I came up with. I start work at 9:00 am, before work I always go to my favorite coffee bar called "Muazam's Coffee" it's 10 minutes walk from my workplace. So I arrive there 8:30 am to have a morning mocha with breakfast while reading the newspaper. One day a man approached me right before the coffee bars entrance and asked me if he could experiment a problem on me, he promised I would get enough cash for a coffee.

Well, why not I thought. He presented me Two Envelopes and said "One contains twice as much as the other. You may pick one envelope and keep the money it contains. You pick at random, but before you open the envelope, you are offered the chance to take the other envelope instead."

Without giving it a single thought, I picked the one on left for me, and began to unfold it. He looked at me and said "don't you want to swap?!", I had just unfolded the envelope and pulled out $20 bucks, "too late for that I guess" I said. I could tell by the look of his face that he was disappointed, he unfolded the other envelope and pulled out $10 bucks. He left me without saying a word.

I went to the coffee bar and spent the money I've just gotten. I took my coffee and breakfast and sat down on one of the outside tables. I saw the Envelop man again, this time he had found another guy. He had two new envelopes and asked the guy the same question. But this guy took out a pen and paper and started doing some math. It was already 8:47, I had to go to work.

Next day, same routine. I go to the Muazam's Coffee bar, and I see Envelope and mathematician guy(let's call him Joe) sitting on one of the tables outside the bar. The guy is still trying to solve the problem. I was kinda impressed how much Joe had put effort into this, he already had four A4 full of notes that seemed like formulas.

This went for weeks, months, years.

Everyday, before work I would see them outside. The Envelope man having two envelopes by his side and Joe trying to solve the problem.

28 years had passed...

I was going to Muazam's Coffee bar as usual when I noticed there was ambulance outside. I went to see who they came for, for my surprise it was Joe. I asked the envelope man, what had happened, he told me Joe had a heart attack.

Joe was admitted in a hospital, he was in bad condition. The envelope man visited him and said "Joe, I am proud of you. We have spent so much time together and you still don't have the perfect formula to solve this problem. Maybe this problem can't be solved with math..".

Joe looked him in the eye and said "No, I won't give up. I will get this right and get the highest amount of cash". The envelope man said "You can have them both" and he unfolded both of the envelopes. One containing $1 and the other one $2. This is where Joe had another heart attack.

Post reply on HN