3 ms·

No, quite the opposite unfortunately :(

jamii 13y ago
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 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 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 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 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.
- jamii 13y ago
  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-Algorithms-Probabilistic/dp/0521835402/ 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.
- briancaw2 13y ago
  Sorry but right after you finish the basic probability coverage it stops making sense. -> 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. Right there.
  - jamii 13y ago
    Well, with the distribution I gave it could be $2 (with probability 1/2), or $4 (with probability 1/4), or $8 (with probability 1/8) etc. That distribution doesn't have a maximum. For a simpler example, imagine tossing a coin and counting the number of tosses it takes you to get a head. There is no limit on the number of tosses it might take, it just gets less and less likely as the numbers get bigger. We could get any positive integer and there are an infinite number of integers. Similarly, the envelope problem has an infinite number of possibilities because there is no maximum amount that could be in the envelope. The article doesn't specify the exact odds of any given amount showing up in the envelope so I gave some specific odds that demonstrate the problem. Probability theory still works when you have an infinite number of possibilities but it has a few subtleties that aren't commonly taught until undergrad. One of those is that the expected/average value of a random variable doesn't always exist so you have to be careful when reasoning informally.

jamii 13y ago

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 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 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 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 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.

jamii 13y ago
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-Algorithms-Probabilistic/dp/0521835402/ 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.
briancaw2 13y ago
Sorry but right after you finish the basic probability coverage it stops making sense. -> 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. Right there.
- jamii 13y ago
  Well, with the distribution I gave it could be $2 (with probability 1/2), or $4 (with probability 1/4), or $8 (with probability 1/8) etc. That distribution doesn't have a maximum. For a simpler example, imagine tossing a coin and counting the number of tosses it takes you to get a head. There is no limit on the number of tosses it might take, it just gets less and less likely as the numbers get bigger. We could get any positive integer and there are an infinite number of integers. Similarly, the envelope problem has an infinite number of possibilities because there is no maximum amount that could be in the envelope. The article doesn't specify the exact odds of any given amount showing up in the envelope so I gave some specific odds that demonstrate the problem. Probability theory still works when you have an infinite number of possibilities but it has a few subtleties that aren't commonly taught until undergrad. One of those is that the expected/average value of a random variable doesn't always exist so you have to be careful when reasoning informally.