The envelope paradox (2006)

http://blog.plover.com/math/envelope.html

by olalonde • 11 years ago

43 74 11 years ago

blog.plover.com

throwaway_bob• 11 years ago

when he says "probability", what space does he mean? This analysis does not seem very careful.

idlewords5• 11 years ago

"Here's your winning strategy. Before you see A, choose a random number R"

Isn't it true that there's no uniform distribution over the reals? That seems to be what the whole apparent paradox hinges on.

sidedishes2• 11 years ago

One way to resolve this problem is to use a continuous, increasing map f from the reals to say, (-1, 1). Something like arctan(x)/pi. You can then pick a number randomly from (-1, 1), then compare that with f(A), rather than a random real with A.

idlewords5• 11 years ago

But then it's not really uniform, is it? That innocent instruction to 'pick a random number' is carrying a lot of conceptual baggage.

dllthomas8• 11 years ago

Per my understanding, it doesn't take the weirdness involved in the reals... there's not even a uniform distribution over the integers.

analog31• 11 years ago

True. If somebody asks you to choose a random number, you have to ask: From what distribution?

mjd5• 11 years ago

Any distribution suffices, as long as it is everywhere positive.

monochromatic2• 11 years ago

True that there's no uniform distribution over the reals (or even over the integers or the natural numbers). But just pick whatever distribution you like.

fenomas13• 11 years ago

It doesn't have to be a random number from any particular distribution - you can roll 1d20, or use your age, or anything else you like.

The point of the paradox is that picking a value and trading anything below it is always a non-losing strategy, and may also be a winning strategy, depending on factors that are not defined in the puzzle (i.e. whether your opponent's choices are anywhere close to the number you chose).

JackFr4• 11 years ago

There is no paradox, because under the conditions of the problem, the advantageous solution cannot be shown to occur with a probability greater than 0.

mjd5• 11 years ago

Rolling 1d20 doesn't work, because if the first player always chooses numbers bigger than 20 or smaller than 1, the second player wins with only probability ½.

To get a winning probability greater than ½ the second player needs to choose from a distribution that is everywhere positive, which means that a discrete distribution won't do.

mjd5• 11 years ago

You're right, but it doesn't have to be uniform, and of course it can't be. It only needs to be everywhere positive.

I wrote it up in more detail here: http://math.stackexchange.com/questions/655972/help-rules-of...

ars3• 11 years ago

Doesn't this paradox hinge on both of you having the same definition of "random" (i.e. using similar range of numbers)?

That seems to be extra information given to you, above and beyond simply an envelope with a number.

So there is no real paradox, the solution is based on a hidden assumption not directly spelled out.

marvy2• 11 years ago

The person writing down the numbers can choose them randomly, or sneakily, or whatever. Only the person choosing has to randomness. This makes no assumptions on how the numbers were generated.

ars3• 11 years ago

Only the person choosing has to randomness

No, the person solving does so by picking a random number. Implied is that that random number has the same (or similar) range to the original.

fenomas13• 11 years ago

The idea here is that any choice by the player yields a strategy which will not lose money, and may make money, depending on factors that are left undefined (i.e. whether or not the player and opponent choose similar numbers).

The fact that the author calls this state of affairs "a winning strategy" seems to be confusing a lot of commenters here. In practice you only benefit if your number sometimes falls between your opponent's choices, and your opponent can make the chances of that happening arbitrarily small. But suffice to say, if you actually play this game with a real opponent then the author's strategy will indeed let you win "at least as often" as choosing randomly, and possibly more often depending on how your opponent plays.

ars3• 11 years ago

In practice you only benefit if your number sometimes falls between your opponent's choices

Or in other words if your range for random numbers is similar to the opponents range.

Or in other words there is more information being transmitted here than just an envelope - you also need to know the range, making this paradox not actually a paradox.

dstyrb2• 11 years ago

My solution was R=0 always.

So if A is positive, always guess B < A. If A is negative, guess B > A.

Does this not work?

    import numpy as np
    import random as rnd

    trials, correct = 100000000, 0
    for i in range(trials):

        a = rnd.random()-0.5
        b = rnd.random()-0.5

        if a >= 0. and b < a:
            correct+=1
        if a < 0. and b > a:
            correct+=1

    if correct > trials/2.:
        print 'winner: '+str(correct)

idlewords5• 11 years ago

You're picking a number over the unit interval, not an 'arbitrary number'.

dstyrb2• 11 years ago

how can I generalize? edit: Oh I see that's what the whole discussion here is about -_-

landryraccoon• 11 years ago

Can the author prove that case (3): one is less than R and one is greater than R occurs with greater than zero probability?

Consider a special case of the experiment: One in which the number picker always picks numbers within a finite interval; i.e., for numbers E1 and E2 inside the envelopes |E1 - E2| < X for some X. In this case, case 3 occurs with zero probability. There is an infinite interval over which both E1 and E2 are greater than any random number R. Similarly, there is an infinite interval over which both E1 and E2 are less than any given random number R. But there is only a finite interval over which it is possible for E1 and E2 to be on opposite sides of R.

Here's another way to think of it: You have an infinitely large dartboard. The author wants to paint a finite sized bullseye on the dartboard. The size of the dartboard is the distance between E1 and E2 (the two numbers in the envelopes). He throws a random dart at the dartboard and if he hits the bullsye he wins. The size of that bullseye is the "advantage" over random chance. But it doesn't matter how large you paint the bullseye, if it's a finite size then there's a zero probability that a random (finite sized) dart will hit the bullseye. The ratio of the area outside the bullseye to the ratio inside the bullseye is infinity.

JackFr4• 11 years ago

This was exactly my thinking, that P[A<R<B] = 0, thus no paradox.

fenomas13• 11 years ago

The puzzle doesn't specify how your opponent chooses their numbers. Both your analogies implicitly assume that they are somehow choosing from an infinite uniform distribution (is that even a thing?) but all the puzzle states is that there aren't any restrictions on how they choose.

So the idea here is that the author's strategy is guaranteed not to lose, and may possibly win depending on factors that are not specified.

JackFr4• 11 years ago

The authors strategy guarantees that you can't do worse than 50%, and you might do better.

Of course you that could sacrifice a goat and examine the entrails and guarantee that you won't do worse than 50% and might do better.

If that R, A, and B are elements of the real line with A < B, What is the probability that A < R < B? It looks to me like the probability would be (B-A)/Inf = 0.

dllthomas8• 11 years ago

"infinite uniform distribution (is that even a thing?)"

No, that's not even a thing.

dllthomas8• 11 years ago

"Can the author prove that case (3): one is less than R and one is greater than R occurs with greater than zero probability?"

I think it falls out of the way you pick R. If you pick from a distribution with a non-zero probability everywhere, then for any specific (non-equal) X and Y, you've got non-zero probability integrating between them.

level34• 11 years ago

The whole point of picking a value for R is that it essentially transforms the game from "guess whether A is smaller or larger than B" to "guess a number between A and B."

Regardless of how A and B are chosen, if your R is not between them, then you break even; if your R is between them, then you win. So your advantage is entirely based on your probability of picking between A and B. As long as that probability is nonzero, then you have an edge.

The way you guarantee having nonzero probability is by choosing with a distribution that is positive everywhere (e.g the normal distribution). No matter where the interval [A,B] is, you have a chance of choosing within it.

Depending on the opponent's distribution vs yours, that chance may be very small, but it's still strictly greater than 0.

hackaflocka2• 11 years ago

This is similar to another, well-known, paradox. Something about a game show, and there are 3 stalls, and one of them contains a car. The game show host opens up one of the empty stalls to show there's no car behind it. You have to guess which one of the other 2 has the car behind it. And there's a way to play it that makes your chances better than 50%.

Anyone got a link to this paradox?

Update: it's called the Monty Hall Problem: https://en.wikipedia.org/wiki/Monty_Hall_problem

idlewords5• 11 years ago

It's superficially similar, except that the Monty Hall problem is well-defined, while this one isn't (see my harping upthread about what it means to 'choose an arbitrary number').

larrymcp• 11 years ago

The Mythbusters guys did a segment on the Monty Hall Paradox.

http://www.dailymotion.com/video/x2mykzd

Cool...

hackaflocka2• 11 years ago

Thanks for the link.

dools• 11 years ago

I was incredulous that this was as simple as I first thought[1], but had my suspicions later confirmed when I read about it on lesswrong

[1] http://iaindooley.com/post/61292324101/the-two-envelopes-pro...

dllthomas8• 11 years ago

I don't think it's as simple as you thought. Or at least, the problem you identified is not a problem. The actual problem is still pretty simple.

[for those dropping into this thread without having followed the link, we seem to have restricted our discussion to the (x, 2x) problem, which is mentioned in the plover.com article but is not where it starts]

Probability is a means of dealing with uncertainty. When you open the envelope you were handed and see $10, what you've learned is that the other envelope contains either $5 or $20. This is not postulating existence of both of those envelopes - this is your uncertainty about which world you inhabit, one with two envelopes ($5, $10) or one with two envelopes ($10, $20). It's true that you only inhabit one of those worlds, but you don't know which and probability is how you get a handle on your lack of knowledge.

As I understand it, the problem is that a natural - but errant! - next step is to say, "I don't know how likely it is that the envelopes were stuffed with $5 and $10 vs $10 and $20, so I'm going to assume both are equally likely." Around $10, this is probably a good approximation. But if you're saying this before looking at the envelopes, then it amounts to saying "the probabilities are equal for any choice of value" (for all x, P(x)=P(2x)). I'm actually not sure what distribution should be chosen to reflect zero knowledge of a rational number, but it should be a distribution - the likelihood of all possible outcomes should sum to certainty (1). That is incompatible with "for all x, P(x)=P(2x)".

kazinator• 11 years ago

This seems like nonsense. Here is one reason why: let's examine this:

Before you see A, choose a random number R

This is underspecified. Pick a random number in what range?

Suppose we programming in a language which has arbitrary precision integers and floats, and we are given a requirement, "write a function which chooses a random number". What the heck do we implement?

I think this relies on having the same random number generation method as the adversary who prepares the envelope. But if that's the case, we can just reason about that directly.

If we know that the opponent is, say, using a function that generates a random IEEE 64 bit double, then by looking at the A value, we know the odds that this method will produce a higher or lower value.

logicallee4• 11 years ago

I have an analogy, it might be wrong or hard to follow. However, I believe it shows why the article's argument is pretty nonsensical.

Suppose there were two possible universes - God had a choice when creating the world - and we're living in one of them. We have no idea about His choice, or what other possible universe there might be. How could we learn anything about another universe? Obviously we can't.

Can we have a better than even chance of guessing whether we're living in the better or the worse of the two possible universes? Per the article, we can! Mimicking the protocol described in the article:

* Step 1: We choose a random number, setting this aside. I don't specify how we choose this.

* Step 2: Then we evaluate the universe we're living in, which we do have access to, via whatever fitness function we want, as to how good it is. We arrive at a numerical score. Edit: This corresponds to opening the envelope to see what number is inside. Note that we don't have any information about the number in the other envelope! (The other possible universe.) None whatsoever.

If the numerical score is higher than the random number we had guessed, congratulations, we're probably living in the better of the possible universes!

if the numerical score is lower than the random number we had chosen, odds are we're not living in the better possible universe!

But this method of gaining a bit of information is just so patently absurd on its face. Obviously we haven't actually learned anything at all.

I hope this little exercise shows how ridiculous the steps outlined are.

It is clear we cannot actually gain any insight whatsoever into the philosophical question proposed, through this method. we don't actually learn whether we're probably living in the better of two possible universes, where we have absolutely no idea as to what the two might differ in (what number the other universe might have.)

dllthomas8• 11 years ago

"Can we decide if we're living in the better or the worse of the two possible universes? Per the article, we can!"

No, per the article you'll have a marginally better chance than picking without assessing at all. I don't think your framing shows anything at all about whether that's sense or nonsense.

level34• 11 years ago

Your analogy is clouded by emotion, since it appeals to the notion that we shouldn't be able to pick some arbitrary number and then be able to compare the quality of universes. Comparison of universes is multifaceted, so it seems nonsensical, but it actually becomes very possible when you reduce the universes to a single number, and thus make it a question about a probability space.

Let's use your protocol. We arbitrarily choose a number R. Then we find out our universe's number A. So now our question is, what is the probability that B is further away from A than R (and in the same direction)?

This might seem intractable because we don't know anything about the way A and B were chosen. But in fact, we don't need to. We're not actually trying to calculate the probability; we just want to know whether it's greater than zero.

As initially posed, the problem is, "Out of all the possible distributions for A and B, and all the possible As and Bs for each distribution, is there a nonzero probability that B is further away from A than R (and in the same direction)?" Intuition might tell you no, since the interval [A,B] is always finite over a seemingly infinite range. But that doesn't account for the fact that "most" distributions are just as finite. And it's also easy to envision that there are an infinite number of distributions that will permit a B that meets that condition (especially given that there are just as many Bs on "that side" of R as there are on "this side"). Still, you may argue that we don't have an easy way to sum the probabilities over all the distributions.

So we solve the problem by re-framing it in simpler terms. Instead of fixing R while varying A and B, we transform the problem by fixing A and B and varying R (which is completely under our control). And it turns out, if our distribution of R is positive everywhere, then regardless of A and B, there's a nonzero probability of R falling between them. We still need to sum over all possible distributions of A and B, but we've already shown that every term of the sum is positive.

In the end, we might not know the exact value of that probability, but that's irrelevant to the problem.

fenomas13• 11 years ago

What the heck do we implement?

    return 4;

..or anything else you like ;)

The point of the paradox is that using any number gives you a non-losing (and possibly winning) strategy. (Modulo some assumptions that the opponent doesn't know your strategy, etc.)

monochromatic2• 11 years ago

This is underspecified. Pick a random number in what range?

It is underspecified, but it doesn't matter what range you use. I mean, yes, it does matter in that it affects your probability of success. But you can pick it however you like and still do better than breaking even. Pick a random number in [-10, 10], then next time in [-pi^78, -5], then next time [0, 109487468742]. It doesn't matter.

caf• 11 years ago

I think "do no worse than breaking even"?

nshepperd• 11 years ago

The solution works for any random number distribution that is nonzero over the entire real number line. A standard normal distribution works, for instance. (Edit: Regardless of the number generator used by the adversary.)

leephillips• 11 years ago

This might be a bit clearer when presented as here:

http://blog.xkcd.com/2010/02/09/math-puzzle/comment-page-1/

where using a particular strategy for choosing R lets the probabilities of winning be calculated explicitly.

jdmichal2• 11 years ago

I'm not entirely convinced that cases (1) and (2) have the 50% probability stated.

We have X, the number revealed to us; Y, the hidden number; and our random number, R. Let's assume we have case (2), so X > R and Y > R, but the relationship between X and Y is not defined. So, X and Y lie somewhere in the range (+∞, R). We then partition that range with X: (+∞, X) and (X, R). Y lies in one of these two ranges. By the rules defined, we state that we expect Y to be less than X. But the interval less than X is finite, while the interval above X is infinite. I doubt that this range distribution results in a 50% chance.

I think that by picking R, we are modifying the probability that Y is less than or greater than X in cases (1) and (2). However, since we cannot distinguish between those cases and case (3), all the winnings gained in (3) are actually lost to in cases (1) and (2).

EDIT: I guess what I'm saying is that X and Y are no longer independent in cases (1) and (2), but are conditioned by R. That conditioning means we can no longer claim a 50% probability for those cases as if we had never picked R.

alister• 11 years ago

You have an interesting thought and I was wondering the same thing.

OP says that the probability of winning in the 3 cases are:

(1) 50% win, (2) 50% win, (3) always win

If I understand correctly, you're saying that the probabilities might perhaps be:

(1) 50% win minus some probability of case 3 happening, (2) 50% win minus some probability of case 3 happening, (3) always win

Then the three cases even out to 50% and there is no winning strategy.

But wouldn't your argument break down where you write, "But the interval less than X is finite, while the interval above X is infinite."? Since we're dealing with reals, then both (+∞, X) and (X, R) have an equally large and infinite set of numbers (i.e., the latter is not a finite set)[1]. So, Y is as likely to be found in (+∞, X) as in (X, R).

I'm still wondering if there's a way to make your argument work.

[1] https://proofwiki.org/wiki/Closed_Interval_in_Reals_is_Uncou...

jdmichal2• 11 years ago

But wouldn't your argument break down where you write, "But the interval less than X is finite, while the interval above X is infinite."? Since we're dealing with reals, then both (+∞, X) and (X, R) have an equally large and infinite set of numbers (i.e., the latter is not a finite set)[1]. So, Y is as likely to be found in (+∞, X) as in (X, R).

Yes, of course. I realized this about 5 minutes ago in the shower and was hoping no one had called me out on it yet!

I think the real argument is actually a combination of this and landryraccoon's post, depending on the problem definition. [1] The problem is either defined in such a way that the (X, R) interval is finite, and therefore falls under my argument. -OR- the problem defines (X, R) to be infinite, and P(case 3) is zero.

[1] https://news.ycombinator.com/item?id=10647331

mjd5• 11 years ago

A more detailed (and formal) analysis is on math.se, here: http://math.stackexchange.com/questions/655972/help-rules-of...

All the people saying that the strategy described doesn't work are mistaken; the paradox is discussed in the literature in Thomas M. Cover “Pick the largest number” Open Problems in Communication and Computation Springer-Verlag, 1987, p152.

fenomas13• 11 years ago

Regarding the "money in envelopes" version in the second half of the post: When I first encountered this, I came up with the author's answer (about how the "always switch" strategy implicitly assumes they come from an infinite distribution).

But over the years I've come to believe that it confuses things to arbitrarily claim that the opponent is choosing their numbers from a distribution, and then talking about what kind of a distribution it was. I think it's much clearer to examine things in Bayesian terms, by noting that before opening an envelope the player expects it's 50% likely that they chose low, and after opening it they can update their expectations. (The math works out the same either way, it just seems weird to me to impose rules on the opponent that weren't part of the puzzle.)

(Also: the fact that people always seem to examine this puzzle by imagining what kind of distribution the opponent chooses from seems, to me, an artifact of just how accustomed we are to standard statistics, and how uncomfortable we are with probability puzzles that don't involve values being chosen from predefined distributions.)

dllthomas8• 11 years ago

It's not that the opponent is "choosing their numbers from a distribution", so much as that we need to model them that way, and that running probability calculations when violating probability axioms (of course) fails.

I think that's roughly as true whether we're talking frequentist or Bayesian.

fenomas13• 11 years ago

It's not that the opponent is "choosing their numbers from a distribution", so much as that we need to model them that way,

That's what I mean - the statistics we're mostly taught can only deal with distributions, so we wind up inventing them even when none is specified.

Which would be fine if it made the math easier, but it seems to me that it makes it worse. Consider a concrete question, like "if I open the envelope and find $10, how confident would I need to be that it's the low envelope before I switch?". In Bayesian terms that's easy to answer, but with the frequentist version one is left asking "how likely is it that my opponent used a distribution which when sampled once yielded $10, as opposed to a distribution which.." or some such thing.

I mean, the envelopes puzzle basically says, "you start out expecting two things to be equally likely, then you learn a piece of information, now how does that change your expectations?" It's as Bayesian a question as ever there was.

StefanKarpinski2• 11 years ago

I think the analysis of the strategy's chances of winning is faulty. We can assume that the adversary chooses A and B such that P(A < B) = ½, since otherwise the optimal strategy is to always guess A < B or B > A depending on if P(A < B) > ½ or P(A < B) < ½.

Now, analyze the game using the standard approach of breaking it down into simple, non-overlapping cases:

    R < A < B: lose
    A < R < B: win
    A < B < R: win

    R < B < A: win
    B < R < A: win
    B < A < R: lose

Thus the probability of losing is

    P(R < A < B) + P(B < A < R)
    = P(R < A ∧ A < B) + P(B < A ∧ A < R)
    = P(R < A)*P(A < B) + P(B < A)*P(A < R)
    = P(R < A)/2 + P(A < R)/2
    = 1/2

There is no paradox: no matter how you choose R, you have exactly a ½ chance of winning.

pzone2• 11 years ago

That sounds right to me. The first few sentences of the article, talking about "picking numbers at random" without fixing any sort of probability distributions for those numbers, or even labeling those distributions as P1 P2 and so on, raised enough red flags that I stopped reading.

Whether or not the the conclusion of this article is correct (and my intuition still screams "not a chance"), the argument is hand-wavey enough that it doesn't reply to the objection raised here.

pzone2• 11 years ago

Update: I read one of the comments below and now I'm convinced by the argument. Here's the intuition for what's happening. (I wish the article had spelled this out sooner)

As long as A does not equal B with some positive probability, and as long as you choose a separator R with full support, then there is some probability that R lands between A and B. When that happens, you always win the game. Otherwise, if picking A or B randomly doesn't hurt you, then R landing somewhere else not between A and B doesn't hurt you either. So you've gotten a strategy that, once in a while, helps you separate A and B, and doesn't hurt you otherwise.

level34• 11 years ago

One way to think about the game is adversarially. That is, we first have to publicly reveal our distribution for R, and then the opponent arbitrarily chooses A and B.

If our distribution is "always choose 0" or "uniformly choose an integer between 1 and 100", then the opponent can always pick A and B so that R will never fall between them.

But if we pick with a distribution that is positive everywhere (like the normal distribution), it now becomes impossible for the opponent to choose A and B in a way that reduces our chance to zero. She can make that chance arbitrarily small, but it will always be positive.

The envelope paradox (2006)

Related Stories