This cool puzzle (and solution) comes from my friend Mike.
Alice secretly picks two different real numbers by an unknown process and puts them in two (abstract) envelopes. Bob chooses one of the two envelopes randomly (with a fair coin toss), and shows you the number in that envelope. You must now guess whether the number in the other, closed envelope is larger or smaller than the one you’ve seen.
Is there a strategy which gives you a better than 50% chance of guessing correctly, no matter what procedure Alice used to pick her numbers?
I initially thought there wasn’t, or that the problem was paradoxically defined, but it turns out that it’s perfectly valid and the answer is “Yes.” See my first comment for an example of one such winning strategy.
This puzzle is similar to, but not the same as, the two envelopes paradox. For more time-devouring reading, see Wikipedia’s List of Paradoxes.
xkcd 
i’m not a math major, so i don’t exactly know what your talking about when you say “real numbers”, so i’m going to think that they are whole numbers like 1, 4, and 5. but i would say that it is always safer to say that the next number will have a higher value because no matter what you do there is always going to be a higher value, of course the opposite is true if your including negatives because it’s infinity plus whatever number you have.
though judging from your conversation i would say “real numbers” are some end number achieved from a formula based on extremely obscure variables possibly having to do with probability.
LikeLike
Good puzzle, and answer.
I have a complaint though.
What does it mean to pick ‘random real numbers’?
Assume for simplicity Alice only picks positive numbers. If A and B have about a million digits p(A) and p(B) will both be close to 1. Now suppose they have about a billion digits, p(A) and p(B) will be even closer to 1. As you keep increasing the size of A and B, p(A) and p(B) get even closer to 1, until in the limit, when you can pick any real number, p(A) and p(B) are both 1. In this case the strategy gives only a 50% chance of success.
I think the given solution only works as long as you are using the loose, intuitive definition of ‘random real number’, where numbers are all finite and small, as in xkcd’s examples of 1, pi, 10 and 11. With this definition it is possible to do a simulation, as xkcd suggests.
I don’t think the given solution (or any solution) works if you really allow any random numbers.
LikeLike
Real numbers are all the non-imaginary ones . ..
That’s a bit unhelpful, so the long version:
Natural numbers are 1, 2, 3, 4, 5 . . . and upwards.
Integers include the natural numbers, and 0, and the negative of the natural numbers.
Rational numbers take the form of p/q where p and q are both integers. They can be any decimal value, or any repeating decimal value.
They include all integers, as well.
Irrational numbers are numbers with a fraction representation, and are infinitely non-repeating, like Pi, the square root of 2, or e.
Real numbers are any numbers that are either rational, or irrational.
(By contrast, imaginary numbers are non-zero multiples of the squareroot of -1, known as ‘i’ and complex numbers are numbers that contain imaginary numbers and real numbers)
LikeLike
I would strap Bob onto an electric chair and then ask him nicely.
LikeLike
Waldo: Real numbers are all rational and irrational numbers (i.e., non-imaginary numbers).
In short, not just 1, 4, and 5, but also 2/9ths, pi, e, etc. Anything with an i component (imaginary and complex numbers) is not part of the real numbers set.
LikeLike
@waldo real numbers are typically defined as the set of all numbers from -infinity to +infinity exclusive. Under real numbers are steps of classification. Rational numbers include positives, negatives 0, and finite and infinitely decimals, however if the decimal has an infinite number of digits it must have a pattern to be considered rational. Integers are positives, negatives and zero with no tolerance for decimals. Whole numbers are zero and positives with no decimals, and natural numbers are positives with no decimals. The set of real numbers is sometimes referred to as all numbers, however this is a dangerous misconception as the square root of -1 is a number but it is not real, it is considered imaginary.
LikeLike
Dang, Protected stole mine… You could also ask Alice, because she was the one to pull them out.
Assuming there are equal amounts of positive numbers as negative numbers any non-zero number for the first would allow a slightly higher chance by saying lower for positive numbers and higher for negative numbers. Of course thats assuming, which is evil. Instead I would go on a rant on the page that taught Bob and Alice this riddle until someone actually knows the right answer… Good Luck.
LikeLike
too much weight is given to the interval [-20,20] “almost surely” the two numbers she picks will not be in this interval. Does it make sense if the first number you see is -25, that with probability extremely close to 1 the next number will be greater than -25? No, it’s still pretty much 50/50.
This would be the continuous equivalent of using any arbitrary probability mass function for natural numbers, say the Poisson. Almost every natural number is “large”, but with a distribution like this, almost every natural number is between 1 and 100.
LikeLike
I have what I think is another way of seeing that the solution is not valid:
It doesn’t change anything if you change the order of the game to:
1) Pick first number
2) Say if you’re going to switch
3) Pick second number
When you look at it like this there is no way of getting a good strategy, as clearly there is a 50% chance of the second number being bigger than the first in Step 3.
I think that this problem (and the non-existence of a solution) is very similar to the Envelopes Paradox.
LikeLike
Anywa.y.. Do I get some money If I answer correctly?.. Otherwise I’d simply say “the other number is larger than your mom”…
Anyway.. the problem is quite a thing.. and the answer… thanks man. Now i’ll be doing maths the whole week to proove you wrong >_>
LikeLike
I don’t think this is true. Imagine Alice just picks a random integer and its successor.
The strategy outlined above only makes sense if there’s a prior (see Bayes). If you do have a logistic prior, centered at zero, then it makes good sense.
I could be wrong. Someone should see if Andrew Gelman will pick it up on his blog (http://www.stat.columbia.edu/~gelman/blog/) 😛
LikeLike
@waldo:
Real numbers are defined as including the following:
-natural numbers (this includes whole numbers starting at 1 and going up to infinity)
-whole numbers (same as natural numbers, but now we are also including 0.)
-integers (same as above, but now we are also including negative whole numbers)
then we have rationals, which include all of the above, plus any fraction, such as 1/5, or any terminating/repeating decimal.
terminating decimal: a decimal that obviously terminates, example :0.5
a repeating decimal is a decimal that infinitely repeats a certain pattern, example: .314314314….
it does NOT include non-repeating decimals, such AS pi (this is considered to be an irrational number).
irrational numbers: complex decimals that do not terminate AND do not repeat a sequence(such as pi)
All of these are considered to be “real” numbers.
LikeLike
I’ve thought about this one a long time now, and I think I get what’s going on, and why this is so counter-intuitive. The actual result here is that, given A < B, I can write a computer program that picks one of these values to retrieve at random and then determines whether the one it didn’t pick was higher or lower, such that this program has more than a 50% chance of success. The fact that I can use any old monotone increasing function and still get above 50% no matter what A and B are is kind of neat, but in the end it’s really not a big deal.
We need to ask in what sense we’re boosting the odds above 50%. What we actually have is this: given a fixed A and B, if we iterate this program over and over again, the computer will get it right more than 50% of the time. But if you think about it practically, this is a sad little program. Any human, after the first run-through of this game, would know the answer 100% of the time, so long as A and B never changed.
We need to remember that the idea of probability is this: given enough trials, I should be able to identify the probability that an event occurs by taking the ratio of number of times that event occurred to number of trials I ran. Since in real life Alice would be allowed to come up with new numbers for each trial, the numbers she picks should also be viewed as random variables, not as fixed constants.
Consider the following program:
1) Pick X_0 and X_1 such that P(X_0 < X_1) = P(X_1 > X_0) = 1/2
2) Pick B in {0,1} with probability 1/2
3) Let X = X_B
4) Pick T in (0,1) uniformly
5) If T is less than p(X), return “lower”; if T is greater than p(X), return “higher”
The numbers 0 and 1 essentially represent the abstract envelopes. Assuming X_0, X_1, B, and T are all independent, I believe one can show that in this case the probability of this program returning the correct answer is exactly 50%, no matter what p(x) is. And that, I think, mimics real life much better than the analysis given by xkcd. We really have to think of Alice’s numbers as randomly generated, because we don’t just get to use the same numbers over and over again.
As for the point about how there is no uniform distribution on the real line: this is correct, but we can still demand that the random variable X_0 – X_1 be such that P(X_0 – X_1 < 0) = P(X_0 – X_1 < 0) = 1/2. This seems fair; although Alice might have a different distribution in mind, in which case picking an envelope in an unbiased manner and then using xkcd’s strategy is not necessarily to your advantage.
So essentially what I’m saying is that the result xkcd gives is counter-intuitive precisely because it’s wrong. That is, it doesn’t accurately represent a real-life situation in which you have to make a decision based on the information given. In real life, if given a choice between saying Alice has the larger number or saying Alice has the smaller number, just flip a coin. There really is no way to get better than a 50% shot.
LikeLike
Almost all of you have made my brain hurt. I’ve worked through all of the posts and have got it all figured out. I offer my epiphany for your further considerations…
Here we go, mind the step…
1. An envelope has a greater than 50% chance of being delivered to the wrong address.
2. The larger the number of the street address, the greater the chance of incorrect delivery.
3. An asymptote is something a donkey carries.
4. When someone says larger, they mean bigger as in, like, MASSIVE. (in a totally positive way. Peace man!)
5. MPL said that Randon != uniform which is wrong. I went to a costume store once and picked out a uniform at random. Uniform = random; therefore random = uniform. QED. (I think this called using the commutor law which is why I was able to figure this out on the train this morning.)
6. Alice needs to get out more.
7. Rikard talked about 0 being in the middle. This is definitely true. Also, the more numbers you have on either side of the 0, the bigger the zero has to be. If you go way out to infinity on either side then you need to have an infinitely big zero in the middle. This is simple physics because otherwise you won’t be able fit the axle through in order to balance your equations.
8 To Waldo.. I hate to break it to you, kid, but there are no such things as ‘real’ numbers. It’s not a nice thing to say to mathematicians in the same way that it’s not nice to tell toddlers that Santa isn’t real. They need to believe in the falsehood so that they can make sense of their distorted world view. Numbers, like Santa, are a human construct overlayed on reality to help less developed minds avoid having to cope with the complete nonsensical nature of the universe.
9. Maggie likes kittens. (Me too!)
10. XKCD said that there is no way to choose an integer at random. This is also wrong. Proof follows… 23098547. Get over it and move on.
The correct answer to this problem lies in the answer to the following question:
Are all infinities equal?
If the answer is YES then the probability is 50% no matter what you guess as there will be an infinity of possible real numbers on either side of the viewed number.
If the answer is NO then the probability will be greater than 50% in the direction of 0. eg: if the viewed number is positive then you have all the infinities of numbers on the negative side of zero PLUS the infinity of numbers between the chosen number and zero. ie: if the viewed number if positive then you should say that the unviewed number is smaller. If the viewed number is negative then you say the unviewed number is bigger/larger/TOTALLY MASSIVE (peace man!)
I hope this helps the debate.
Love
PEJ
LikeLike
Apart from just the logistic distribution, p(x) = 1 / (1-e^-x), any similar distribution like p(x-10) or p(x+45) can also be used.
Suppose I choose to use p(x-A), where A is the first number chosen.
Since x = A here p(x-A) = p(A-A) = p(0) = 0.5. Thus the strategy given in the solution becomes:
1) Pick a number
2) Flip a coin, and based on that say if you think the other number is higher or lower.
Do you still think the solution given gives a better than 50% chance of being correct?
LikeLike
what happens if the random number is the same as P(x)?
LikeLike
What happens if your random number is exactly P(x). does this trick still work if you just choose another one?
LikeLike
nice reference to calvin and hobbes in monday’s comic. that’s the best comic strip in the history of comic strips.
LikeLike
Oi, Randall, leavin’ this comment here hoping it’ll be noticed:
CLOSE THE TITLE TAG!
To answer the question (it’s been said already), the simplest way is smaller for a positive number and larger for a negative number.
LikeLike
I believe that the strategy is simply to choose any number x in advance, and if the first envelope has a value larger than x then guess that the second envelope is smaller, and vice versa. This can’t be worse than 50-50 (e.g. it becomes 50-50 for x = infinity or -infinity , and is better than random if Alice has any distribution that includes values on both sides of x).
LikeLike
Today’s comic:
HONOUR!
It’s honour. I know you’re from the United States, but proper English is just so much nicer.
LikeLike
Can someone translate into layman’s terms how it makes sense that guessing higher/lower on an infinite set can ever be bigger than 50%?
Seems kind of awkward..
LikeLike
Hi!
I’m afraid I’m off topic, but your website requires a missing -tag. That’s why I cannot enjoy your latest comic 😉
Best regards
LikeLike
Hey,
it’s me again, your comments do not accept html-tags, I see…
I meant the /title-tag.
Sorry I’m off topic again!
LikeLike
I’m siding with bradluen on this.
The problem clearly states that Alice picks the two numbers by some unknown method. What if she arbitrarily chooses the two numbers as n and n+1, or as n and n-1, where n is decided by the roll of a 100 sided die? (Note, that Bob doesn’t know by what method the numbers are chosen.)
There is no way Bob could tell which is which simply by looking at the first number what would have any higher probability than the initial coin toss that decided which envelope they went in.
LikeLike
Also, from Aaron Meurer
“If you don’t believe me, here is my proof that 0 is not a real number: Let x be a real number. Then, because the probability that x = 0 is exactly 0 (see link in original post), then x != 0. Because x was arbitrary, no real number = 0. Therefore, 0 is not a real number.”
Seriously?? You’re basically defining it that way. Just swap out all the 0’s for 1’s, and it makes just as much sense, which is little to none.
LikeLike
My initial thought was “Assume the hidden number has the opposite sign.”
(I’m ignoring zero at the moment, though I suspect you could arbitrarily choose to treat zero as positive)
So, if you see positive, guess that the other number is lower, and vice versa. The possibilities for the signs are
++
+-
-+
—
Half of these will give you a win.
The other cases (++, –) aren’t guaranteed losses– if the first number is positive, you’ll still win if the hidden number happens to be smaller.
So, your probability of winning would be slightly more than 1/2– 1/2 for the cases of mismatched signs, plus the times you get lucky with the matched signs (which feels like it should be half of each of those, but I’m skeptical).
Given that the question of “positive or negative?” reduces to >0 or <0, it feels like the same argument could work for any cutoff point, ie “Assume the hidden number is on the other side of 100.”
Which makes me think there’s a flaw up there.
I’ve been treating it as though she chooses the 2 numbers randomly. If we use positive/negative, she could saboutage us by always choosing 2 numbers with the same sign. Even then, though, are chances are no worse than 1/2.
LikeLike
What if you generalize the problem to having n envelopes, and you have to guess if the number you are being shown is above or below the arithmetic or geometric mean (or some other normalized symmetric function of n variables). It seems like the given solution should still work if the numbers are split 50-50 above and below the mean, but otherwise I’m not so sure that it still works.
LikeLike
Real Numbers are all Numbers which are rational (expressible by a fraction) and irrational (not expressible by a fraction)
Rational = { 1, 1/2, 24.15 }
Irrational = { Pi, e }
Whole numbers are a subset of Rational Numbers = { 1,2,3,4 }
A larger set of numbers would be Complex Numbers which contain an imaginary component
Complex = { 1, 3, 4+i, 3.2+i, Pi + e(i)}
Where i is the square root of negative 1
LikeLike
I get the puzzle, and I have an answer. But I think there’s a little mistake in your explanation:
http://www.wolframalpha.com/input/?i=1%2F%281%2Be^-x%29 <– firstly, I don't think that's monotonous.
Anyway; there's an easier way to explain your more then 50 percent chance. There is a choice of numbers uniformly taken from -inf – +inf, right?
Now let's divide this space into two equal fields. -inf – 0, and 0 – +inf. 50% is in the first field, 50% is in the other. Now, the question is whether the secret number is higher or lower then the public number. if the public number is higher then zero, choosing lower will give you more then 50 percent chance because you have the whole first field and a little extra from the second. If the number is negative, choose higher instead. you get the second field plus a little from the first one.
LikeLike
In a simpler way: choose a random real number, and then assume the number in the other envelope is this one. Assuming the number you choose is bigger or smaller than both the ones inside the envelopes, you have 50% chance of winning. Assuming it’s in the middle, you win.
The trick is: turn the
andom real number into some expression with
andom real number from a to b so you can measure your winning cut without something like delta/inf.
Is this it?
LikeLike
Correct me if I am wrong but the logistic function is not required.
An simpler method would be to pick a random real number. Then compare that number with the real number in the first envelope. If your number is greater than the number in the envelope then guess that the number in the second envelope is also greater than the number in the first. Otherwise guess that it is less.
The logistic function just maps the all real numbers to a number between 0 and 1. This is nice for math proofs and also because most “pseudo” random number generators actually generate a number between 0 and 1. But in the abstractness of the problem it should not be a necessary step. Also any mapping of the real numbers to (0,1) that is one-to-one should also work, not just the logistic function.
LikeLike
@Protected: Bob screams. Bob cries. Bob tries to tell you that he’s doesn’t know. ‘Ask Alice!’ Bob pleads. You ignore him. Bob cries.
LikeLike
@Protected: Bob screams. Bob cries. Bob tries to tell you that he doesn’t know. ‘Ask Alice!’ Bob pleads. You ignore him. Bob cries.
LikeLike
The problem only said that Alice, picks two different real numbers – it doesn’t specify that the difference between those numbers is not infinitesimal.
Suppose her method is to pick one random number another who’s difference from the first is infinitesimal…
for instance define the procedure as:
N[1]= random number from -inf to +inf
N[2] = lim N[1]+1/x as x->+inf
…
LikeLike
Susan, you are correct but I found it a bit hard to follow you so I’m rephrasing what Matt’s mistake is…
This step:
P(t = p(x)) P(x = min(a,b))
Should instead read:
P(t = p(min(a,b))) P(x = min(a,b))
It then reduces to:
(P(t = p(min(a,b)))) / 2
which is greater than 1/2 if a=/=b
LikeLike
Argh! What’s wrong with the html? Try again…
This step:
P(t less than p(x)) P (x = min(a,b)) + P(t greater or equal to p(x)) P(x = max(a,b))
Should instead read:
P(t less than p(min(a,b))) P(x = min(a,b)) + P(t greater or equal to p(max(a,b))) P(x = max(a,b))
With P(x = min(a,b)) = P(x = max(a,b)) = 1/2
LikeLike
Argh! The html! Trying again…
This step:
P(t .lt. p(x)) P(x = min(a,b)) + P(t .ge. p(x)) P(x = max(a,b))
Should instead read:
P(t .lt. p(min(a,b))) P(x = min(a,b)) + P(t .ge. p(max(a,b))) P(x = max(a,b))))
LikeLike
ok, i didn`t knew where to say so…..
I DIT IT
http://www.facebook.com/group.php?gid=309263632879&ref=mf
LikeLike
waldo – Real numbers are all the numbers a non-mathematician might think of, basically (not including complex numbers, which are numbers involving the square root of -1).
The set of real numbers includes the numbers you mentioned (which all happen to be natural numbers), their negatives, 0 (we are up to integers), fractions (or rational numbers), and irrational numbers (the numbers filling the gaps between rational numbers). Pi is an irrational number, for example. Pi is well known, but there is a staggeringly large amount of irrational numbers. Look up countably vs. uncountably infinite.
I think the reason you think there is some formula to generate real numbers is due to the whole debate above over whether or not you can really randomly pick a random number, and even if you can include all the real numbers from negative infinity to positive infinity in your pool of numbers to pick from, randomly or not.
Now my two cents worth. Assuming you really can pick any real number randomly, the probability of them being close enough together to get anything better than 50/50 is 0. In other words, I’d bet that even with xkcd’s solution, the probabilities asymptotically approach 0.50. For example, you could express the probability of guessing correctly as a function of D, the difference between the two numbers. Now, what is the expected value of D? I would argue that it is infinity!
Now, I’m not a math major either, but I would further bet that starting with this expected value of D, you could prove that ANY strategy will be no better than guessing. 50/50. Even Steven.
LikeLike
Well.. unless the number is zero this makes sense (I hope) —
If it’s a positive number say smaller. If it’s a negative number say larger. The odds of being right are higher than 50%.
LikeLike
@Protected:
The problem only states that Bob chooses between the two envelopes, not whether he knows what’s in them. I think it’s reasonable that Bob is used to represent an impartial selection process that chooses between two unknowns with no bias.
You should strap Alice to the chair instead.
LikeLike
Not a math major, but here’s what I would say. Before you choose either envelope, you have a 50/50 chance of picking the higher or lower one. Obviously. Assuming that real numbers go from 0 to infinity in positive and negative directions, I would say the second envelope is lower if the first one is positive, and higher if the first one was negative. Reason? The odds are infinity minus or plus the difference between zero and the first envelope.
I think that’s what Matthias said.
LikeLike
What a subtle problem! I find Matt Hickford’s explanation completely lucid, but I cannot yet articulate why the conditional probability formulation shown by Randall is unjustified. The answer to Susam Pal’s question is that x IS in fact the same in both terms, since you are using only the value revealed by Bob to generate your guess, and you do not yet know whether the value shown by Bob is greater or smaller. I suppose the fallacy occurs when you use conditional probability assuming this knowledge, but I cannot explain WHY this is a fallacy–it seems correct because the sum of probabilities for the complementary assumptions is still unity. So why is that approach wrong, Matt?
LikeLike
I like kittens too.
LikeLike
@waldo: Real numbers include anything you might consider normally a number. That is, positive and negative numbers, including fractions and decimals and roots. So what don’t they include you might ask? Things like the square root of negative one, which is an imaginary number.
So take integers…
…, -3, -2, -1, 0, 1, 2, 3, …
add all the rational numbers (numbers you can write as a fraction),
and then add the irrational numbers (things like square roots, pi, e, the golden ratio), and you’ve got the real numbers.
LikeLike
@Susam:
Matt isn’t saying that x = max(a,b) or that x = min(a,b), he’s saying “p(x = max(a,b))”, as in, the probability that x is the larger of the two numbers. Then he assumes that this probability is exactly 50%.
@Matt:
I don’t think you’re justified in making that assumption. The assumption that xkcd is making (which I think is the correct one) is that, the higher the number you pull out of the envelope, the lower is the probability that the other number is higher yet. That would seem to be true no matter what procedure is used to pick the numbers.
if envelope a < envelope b, and x (the number you pick) is either a or b, then the probability that x = b (though impossible to calculate, without knowing Alice's procedure) always increases with the value of x. That seems to be the crux of this whole argument.
Besides, as xkcd already said:
if a p(switching envelopes, if you guessed “b”)
Both probabilities may be greater than 50%, or they may both be in the 10^-50 range. But that doesn’t matter. So long as the above statement is true (which is is) your chances of guessing correctly should be above 50%.
@waldo:
A real number just means any number in existence. Integers, yes, but also fractions or irrational (never-ending) numbers like pi = 3.1415926535897932384…. Only imaginary numbers are excluded.
LikeLike
@waldo: a real number means that the number is not imaginary (recall that i^2 =-1 is the imaginary unit, a complex number is any number of the form a + b*i. if b=0, the number is real.) It can be any rational or irrational number you like, just so long as the number equals it’s complex conjugate.
LikeLike
Picking any number by a random process and deciding based on whether it’s lower or not works, it’s just that if you use that logarithm formula you can calculate the exact probability of success. If you just say ‘higher’ if the first number is below 0 and ‘lower’ if not, you will win 50% of the time both numbers are negative, 50% when both are positive, and 100% when one is negative and one is positive, thus your chances of winning are greater than 50%.
LikeLike