10 ms·

The envelope paradox (2006)

43 points by olalonde 11y ago

throwaway_bob 11y ago
when he says "probability", what space does he mean? This analysis does not seem very careful.
idlewords 11y 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.
- sidedishes 11y 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.
  - idlewords 11y 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.
    - sidedishes 11y ago
      Right, though I don't think uniform is the necessary condition here. We only need a positive chance of picking an R so that f(A) and f(B) are on different sides of R, which isn't as much of a problem if we're picking R from (-1, 1).
      - idlewords 11y ago
        There's also the question of how the first two numbers were chosen; in other words, what it means that 'the numbers are completely arbitrary'. I can't math real good, but this is the part that smells fishy to me.
    - aidenn0 11y ago
      So long as you have a non-zero chance of your number "R" being between A and B, you have an advantage.
- dllthomas 11y 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 11y ago
  True. If somebody asks you to choose a random number, you have to ask: From what distribution?
  - mjd 11y ago
    Any distribution suffices, as long as it is everywhere positive.
- monochromatic 11y 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.
- fenomas 11y 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).
  - JackFr 11y 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.
    - fenomas 11y ago
      Whether a solution is actually advantageous depends on whether your chosen number lies between your opponents choices, which are not defined. The author notes that if you select from an unbounded distribution, you can in principle have a nonzero (though in practice very small) advantage regardless of the opponent's choice.
  - mjd 11y 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.
    - deleted 11y ago
      [deleted]
    - fenomas 11y ago
      Ah, I see what you mean - I meant that any old number will suffice for having a non-losing strategy, assuming that the opponent's strategy is unknown and undefined.
- mjd 11y 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-a-game-whose-details-i-dont-remember/656426#656426 http://math.stackexchange.com/questions/655972/help-rules-of...
ars 11y 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.
- marvy 11y 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.
  - ars 11y 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.
    - mjd 11y ago
      No. The first player can pick any numbers whatever, and the second player should pick a real number from a distribution that is everywhere positive, so the "range" is from minus infinity to plus infinity.
- fenomas 11y 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.
dstyrb 11y 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)
- idlewords 11y ago
  You're picking a number over the unit interval, not an 'arbitrary number'.
  - dstyrb 11y ago
    how can I generalize? edit: Oh I see that's what the whole discussion here is about -_-
- deleted 11y ago
  [deleted]
jdmichal 11y 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 11y 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_Uncountable https://proofwiki.org/wiki/Closed_Interval_in_Reals_is_Uncou...
  - jdmichal 11y 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 https://news.ycombinator.com/item?id=10647331
landryraccoon 11y 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.
- JackFr 11y ago
  This was exactly my thinking, that P[A<R<B] = 0, thus no paradox.
- fenomas 11y 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.
  - JackFr 11y 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.
hackaflocka 11y 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 https://en.wikipedia.org/wiki/Monty_Hall_problem
- idlewords 11y 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 11y ago
  The Mythbusters guys did a segment on the Monty Hall Paradox. http://www.dailymotion.com/video/x2mykzd http://www.dailymotion.com/video/x2mykzd Cool...
  - hackaflocka 11y ago
    Thanks for the link.
dools 11y 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-problem-the-most-boring-paradox http://iaindooley.com/post/61292324101/the-two-envelopes-pro...
- dllthomas 11y 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)".
deleted 11y ago
[deleted]
kazinator 11y 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.
- logicallee 11y 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.)
leephillips 11y ago
This might be a bit clearer when presented as here: http://blog.xkcd.com/2010/02/09/math-puzzle/comment-page-1/ 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.
mjd 11y ago
A more detailed (and formal) analysis is on math.se, here: http://math.stackexchange.com/questions/655972/help-rules-of-a-game-whose-details-i-dont-remember/656426#656426 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.
fenomas 11y 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.)
- dllthomas 11y 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.
  - fenomas 11y 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.
StefanKarpinski 11y 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.
- pzone 11y 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.
  - pzone 11y 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.
    - StefanKarpinski 11y ago
      Yeah, I'm not convinced anymore either. Specifically, I think that the assumption that R < A and A < B are independent events is incorrect, which means that P(R < A < B) = P(R < A)*P(A < B) is not necessarily true. I'll have to think on it more and maybe email Mark about it.

43 points by olalonde 11y ago

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

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

sidedishes 11y 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.
- idlewords 11y 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.
  - sidedishes 11y ago
    Right, though I don't think uniform is the necessary condition here. We only need a positive chance of picking an R so that f(A) and f(B) are on different sides of R, which isn't as much of a problem if we're picking R from (-1, 1).
    - idlewords 11y ago
      There's also the question of how the first two numbers were chosen; in other words, what it means that 'the numbers are completely arbitrary'. I can't math real good, but this is the part that smells fishy to me.
  - aidenn0 11y ago
    So long as you have a non-zero chance of your number "R" being between A and B, you have an advantage.
dllthomas 11y 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 11y ago
True. If somebody asks you to choose a random number, you have to ask: From what distribution?
- mjd 11y ago
  Any distribution suffices, as long as it is everywhere positive.
monochromatic 11y 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.
fenomas 11y 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).
- JackFr 11y 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.
  - fenomas 11y ago
    Whether a solution is actually advantageous depends on whether your chosen number lies between your opponents choices, which are not defined. The author notes that if you select from an unbounded distribution, you can in principle have a nonzero (though in practice very small) advantage regardless of the opponent's choice.
- mjd 11y 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.
  - deleted 11y ago
    [deleted]
  - fenomas 11y ago
    Ah, I see what you mean - I meant that any old number will suffice for having a non-losing strategy, assuming that the opponent's strategy is unknown and undefined.
mjd 11y 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-a-game-whose-details-i-dont-remember/656426#656426 http://math.stackexchange.com/questions/655972/help-rules-of...

ars 11y 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.

marvy 11y 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.
- ars 11y 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.
  - mjd 11y ago
    No. The first player can pick any numbers whatever, and the second player should pick a real number from a distribution that is everywhere positive, so the "range" is from minus infinity to plus infinity.
fenomas 11y 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.

dstyrb 11y 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)

idlewords 11y ago
You're picking a number over the unit interval, not an 'arbitrary number'.
- dstyrb 11y ago
  how can I generalize? edit: Oh I see that's what the whole discussion here is about -_-
deleted 11y ago
[deleted]

jdmichal 11y 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 11y 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_Uncountable https://proofwiki.org/wiki/Closed_Interval_in_Reals_is_Uncou...
- jdmichal 11y 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 https://news.ycombinator.com/item?id=10647331

landryraccoon 11y 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.

JackFr 11y ago
This was exactly my thinking, that P[A<R<B] = 0, thus no paradox.
fenomas 11y 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.
- JackFr 11y 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.

hackaflocka 11y 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 https://en.wikipedia.org/wiki/Monty_Hall_problem

idlewords 11y 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 11y ago
The Mythbusters guys did a segment on the Monty Hall Paradox. http://www.dailymotion.com/video/x2mykzd http://www.dailymotion.com/video/x2mykzd Cool...
- hackaflocka 11y ago
  Thanks for the link.

dools 11y 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-problem-the-most-boring-paradox http://iaindooley.com/post/61292324101/the-two-envelopes-pro...

dllthomas 11y 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)".

deleted 11y ago

[deleted]

kazinator 11y 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.

logicallee 11y 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.)

leephillips 11y ago

This might be a bit clearer when presented as here: http://blog.xkcd.com/2010/02/09/math-puzzle/comment-page-1/ 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.

mjd 11y ago

A more detailed (and formal) analysis is on math.se, here: http://math.stackexchange.com/questions/655972/help-rules-of-a-game-whose-details-i-dont-remember/656426#656426 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.

fenomas 11y 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.)

dllthomas 11y 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.
- fenomas 11y 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.

StefanKarpinski 11y 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.

pzone 11y 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.
- pzone 11y 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.
  - StefanKarpinski 11y ago
    Yeah, I'm not convinced anymore either. Specifically, I think that the assumption that R < A and A < B are independent events is incorrect, which means that P(R < A < B) = P(R < A)*P(A < B) is not necessarily true. I'll have to think on it more and maybe email Mark about it.