The envelope paradox (2006)
blog.plover.com
blog.plover.com
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.
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.
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.
Huh? Sacrificing a goat (i.e. choosing randomly) will not do better than break even.
> If that R, A, and B are elements of the real line...
This makes assumptions about A and B that aren't in the puzzle. The fact that they're unknown doesn't imply that they're chosen from an infinite uniform distribution. It just means we have no information about them.
As the puzzle and strategy are stated, the methods for choosing A/B/R are all left unspecified. If we don't know how they're chosen, it stands to reason that we can't rule out the possibility of R falling between A and B, hence there's a nonzero chance of it happening. If you want a rigorous way to show this even for any given opponent strategy, the player can choose R from an unbounded distribution - which is nonzero everywhere, and therefore nonzero between A and B, for any choices of A!=B.
E.g. pick a number uniformly at random between 0 and 1. It might be rational, but the probability of that is 0.
The opponent's strategy is unknown and unspecified, per the puzzle. The point of the article is that there is a strategy that never does worse than chance, and may do better, depending on the opponent's choice of numbers. Sure, the opponent can make your advantage arbitrarily small - the article says that directly. But the notion that they are trying to do so is not part of the puzzle, and finding a strategy that prevents them from doing so is not what the author claims to have done.
No, that's not even a thing.
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.
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.
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
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
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.
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.
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.
Isn't it true that there's no uniform distribution over the reals? That seems to be what the whole apparent paradox hinges on.
I can't math real good, but this is the part that smells fishy to me.
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).
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.
I wrote it up in more detail here: http://math.stackexchange.com/questions/655972/help-rules-of...
[1] http://iaindooley.com/post/61292324101/the-two-envelopes-pro...
[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)".
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.
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.
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.
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.
There's no such animal as "the opponent's range" here. The problem doesn't specify that the opponent chooses their numbers from a range, or anything else - all that's given is that there are two numbers and we know nothing about them. And if that's the case then it follows that any random number we choose might be between them, in which case our strategy beats chance. Note that nobody's claiming our choice is likely to be between the opponent's choices, just that the possibility hasn't ruled out. None of this makes any assumptions about their numbers.
If you're hung up on the possibility that the opponent chooses numbers so as to counter this strategy, the author points out elsewhere that if you pick a number from an unbounded range (like a normal distribution) then you'll have a nonzero (though vanishingly small) chance of falling between any two numbers the opponent chooses.
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.
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...
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.
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.
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.
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.)
I think that's roughly as true whether we're talking frequentist or Bayesian.
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.
Interestingly, I think that given any particular choice of maximum entropy distribution, the recommendations boil down to "there is a value above which you should stick and below which you should switch." Since I don't think - from the question alone - there is any particular reason to favor a specific distribution, I think it amounts to a free choice of that number. If you have some idea of, say, the bankroll of the game runners (or, at worst, the total amount of money in circulation) you should be able to do better, of course.
I agree, but the operative word is "think". We can't talk about how the opponent chose, only about the player's expectations of how they chose. And talking about how evidence affects expectations is the problem Bayes exists to solve, is my reasoning.
For your second point, that sounds right but assuming a well-formed high-entropy distribution seems like a very arbitrary thing to do. The player might very naturally, say, consider round numbers more or less likely, or at any rate believe that $50 is a more likely value than $50.01, etc, right?
And actually, this point highlights why I think this should be considered as a Bayesian problem. In frequentist terms, one talks about the opponent choosing numbers from some distribution, then the player choosing a strategy based on their expectations about the distribution, then they open their envelope and apply the strategy. If nothing else this approach greatly obscures the most important feature of the puzzle, which is that the player gains new information when they open their envelope. More, it seems somewhat bonkers when considered - if the player chooses a switch value of $10, then opens their envelope and finds $50,000, should they really just apply the strategy they chose based on expectations they now know to have been wildly incorrect? Effectively the player winds up deciding whether to switch based on the fact that they thought $10 was more likely than $20, when one would expect them to reconsider their expectations that they now know to have been wildly off-base.
In contrast, the Bayesian version is straightforward, and we can completely describe the player's strategy without making any assumptions on how it's formed. Specifically, suppose the player starts off with some expectation P(T) that that the total value of both envelopes would be T. Then they open their envelope, find a value of x, and and update their expectations. Then, their strategy depends solely on the ratio between P(1.5x) and P(3x). And we can say all this without even considering whether P is continuous/discrete/etc, or what factors it's based on. All we assume is that it's defined at the two points that are relevant to a given instance of the puzzle - i.e. that the player can form some expectation of how likely one value is compared to twice as much.
I fear I can't describe this very well, but does that make any sense?
Anyone got a link to this paradox?
Update: it's called the Monty Hall Problem: https://en.wikipedia.org/wiki/Monty_Hall_problem
http://www.dailymotion.com/video/x2mykzd
Cool...
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)> 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.
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.)
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.
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.
return 4;
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.)
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.