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.
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).
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.
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).
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.
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.
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.
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.
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.
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.
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.
> 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.
> Or in other words if your range for random numbers is similar to the opponents range.
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.
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)
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.
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.
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.
> sacrifice a goat and examine the entrails and guarantee that you won't do worse than 50% and might do better.
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.
I don't think I make any assumptions about A,B other than that they're on the real line. Regardless, as the puzzle stands, there is no way to show that P[A < R < B] > 0. Since you can't show that, you can't claim that the strategy ever yields performance > 50%.
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.
You're moving the goalposts from what the article claims.
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.
"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.
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.
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%.
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').
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)".
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.
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.)
"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.
(edited) In my analogy, assessing the universe numerically = opening the envelope to see what number is inside. I think it's a pretty close analogy, and obviously leads to an absurd, nonsensical result: that we can learn something about whether we 'probably' (>50%) are in the better universe, without knowing anything about the value of the other one.
I still don't see why your analogy does anything but introduce additional complication. To me, the result appears no more nonsensical than in the original formulation - where it appears correct. So long as X and Y are chosen in advance - and independently - of my guessing, if I draw my reference R from any continuous distribution, there is some nonzero chance that it will fall between X and Y, letting me distinguish them in that case.
you have no idea what possible values X and Y can have. It's like an alternative universe, or guessing a number first and then finding a function to numerically evaluate the universe whose range you don't know in advance. I find it nonsensical that this can yield any information.
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.
You don't seem to have a problem with the protocol itself, by the way. What do you say regarding what all the people in this thread state that you can't chose a random number to begin with? (there is no way to pick an integer uniformly at random)?
They are correct that you can't pick the integer uniformly at random over the real line. But you can pick it randomly with a different distribution (e.g. the normal distribution) that meets the criteria of being positive everywhere.
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.)
> 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.
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.)
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.
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.
> 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.
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.
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.)
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.
> 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.
The question of how you change your expectations, though, boils down to asking "how do I think the person chose?"
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.
> boils down to asking "how do I think the person chose?"
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?
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.
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.
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.
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.
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.
81 comments
[ 4.0 ms ] story [ 132 ms ] threadIsn'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...
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.
So if A is positive, always guess B < A. If A is negative, guess B > A.
Does this not work?
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.
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...
[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)".
> 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.
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.
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.
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.
[1] https://news.ycombinator.com/item?id=10647331
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?
Now, analyze the game using the standard approach of breaking it down into simple, non-overlapping cases:
Thus the probability of losing is There is no paradox: no matter how you choose R, you have exactly a ½ chance of winning.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.