Comment by jamii | Hacker News Reader

Comment by jamii | Hacker News Reader

Parent Full thread

You can even explicitly define the distribution as P($2^i) = 1/(2^i) and the 'paradox' remains. The problem is that you are reasoning about the expected gain of swapping but that expectation is a sum over a series which is not absolutely convergent (http://en.wikipedia.org/wiki/Absolute_convergence) so it's value depends on the order in which you sum over the different cases.

In fact, if you repeatedly simulate the problem (make sure you use bignums) you will find that the mean gain from swapping is not well behaved at all and refuses to converge. The law of large numbers only applies if the expectation is well-defined.

The lesson here is: when in doubt, explicitly write out the probability space over which you are working. Problems like this and the Monty Hall problem are trivially solvable on paper. There is a reason that mathematicians get all hot and bothered about formalism - it gives you a solid base from which to build correct intuitions.

EDIT Let's write this down properly.

    i | gain from swapping if I have the smallest | gain from swapping if I have the largest
    1 $2 -$2
    2 $4 -$4
    3 $8 -$8
    etc

There are two arguments.

The first is that the situation is symmetric so you can't possibly gain. That is:

    E(Gain) = (1/4 * $2 + 1/4 * -$2) + (1/8 * $4 + 1/8 * -$4) ...
            = $0 + $0 + $0 + $0 ...
            = $0

The second argument is that swapping from small to large is a bigger gain than the loss of swapping from large to small. That is:

    E(Gain) = (1/4 * $2) + (1/4 * -$2 + 1/8 * $4) + (1/8 * -$4 + 1/16 * $8) ...
            = $0.5 + $0 + $0 + $0 ...
            = $0.5

Adding up an infinite series is tricky :)

Well, yeah :) The problem is still in assuming something about the distribution without having any good reason to. In original "paradox" reasoning it was impossible uniform distribution. What you show is that even assuming possible distribution could still lead nowhere. It still doesn't mean there is any reason to assume it's P($2^i) = 1/(2^i). I may just as well assume it's exactly 100$-200$ and that switching from 100$ gives me guaranteed payoff. It would be as baseless as assuming uniform distribution or the one given by you.

I think the main lesson from this puzzle is that you can't assume stuff without good reason to.

I'm not assuming that that is the distribution. I'm saying that the problem as presented is underspecified, but even if you give this specific distribution in the problem you can still cause confusion. Assuming stuff is bad but the original 'paradox' still doesn't go away if you nail everything down. It's a useful problem for education people about the subtleties of infinite sums.

Well, there are distributions which don't have well defined expected value and I agree that it's valuable lesson. I would argue though that this is not the best example to show it. The point of two envelope problem comes much earlier and specifically giving distribution defined by you would make it completely different problem and assuming it in original form would already be a mistake.

I think there are better examples to show how infinite sums and relying on expected value based on those might leads to problems. Like this one for example:

http://plato.stanford.edu/entries/paradox-stpetersburg/

The expected value in the St Petersburg game is actually well-defined - it converges to positive infinity. That is a subtly different result than not converging at all. Both problems are useful.

This is either way over my head or not at all clear. More explanation would be appreciated.

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.

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.

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.

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.

Reply on news.ycombinator.com