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 
Actually, there is a flaw with my previous comment, you do need to pick a different number every time because Alice could use some other method to choose numbers, like, say, always choosing positive integers between 1 and 100, and then the probability would be exactly 50%. I guess I didn’t read that part carefully (or assumed that you only play the game one time).
LikeLike
There is definitely something going on here. I haven’t spent a whole lot of time on it but I think I agree with Matt that we aren’t looking at the right probability, or something. One thing that might be useful is to do some statistics. Make a program to run this test. Just make sure to test it using a variety of different random number generators.
LikeLike
Why can’t I use p1(x)=1/(1+e^(-1*x+345.817))? How is one more valid than the next? For small values of x (-10<x<10), p(x) appears to give useful results but they assume that the set of numbers Alice selected from is uniform and close to 0; she could arbitrarily have chosen the mass of Venus and Earth in grams or tan(x) where x is chosen randomly from -pi/2 to +pi/2? p(x) works because of the assumption that Alice being a normal person sees the universe of numbers being small and centered near 0…
LikeLike
This works because you have a better-than 50% chance – but you don’t *know* how much better. Since the value of the second number is unknown, in the same way the amount above 50% this algorithm gives you is unknown. The puzzle is cool because you don’t think to answer it by producing an method which gives you a chance that is better, but by how much you don’t know: you try to figure out how to make sure you give yourself a better than fifty chance – such as by guessing the choosing method rather than assuming that it is likely that the difference between the numbers is like that of 1 and 3.14… – a situation in which your method would give a significant benefit.
I’d imagine the solution is arrived by induction – assuming a more limited set of numbers or some limited constraint such as they must be different by x or y, and creating a method which gives a distinctly good value on them. Then if it is properly thought up, it will generalize to the real numbers, but it will include situations where the advantage is effectively zero.
So you game the system by not gaming the system – or something like that.
LikeLike
@waldo
Actually, those are natural numbers. Real numbers are all numbers that don’t contain (wait for it) an imaginary component. What’s an imaginary number? Well, you may or may not know that negative numbers have no square root. If you don’t, this is because a negative number times a negative number is positive, and a positive number times a positive number is positive. Therefore, the square root of a negative number is not negative but is also not positive. This leaves only 0, but 0*0 is not negative. Thus, the square root of, say, -1 does not exist.
Unless we invent a number to fit there. Let’s call it i, for imaginary. We define i as a number such that i*i=-1. Since we can’t express i in terms of real, or normal, numbers, we just use i. Thus, if we add i to 3, we get the number 3+i. A number of the form a+bi is called a complex number. Complex numbers turn out to be useful for a whole lot of things, such as electrical engineering. So, uh, yeah.
LikeLike
I agree with @waldo. If the number is positive, there will always be more numbers available “less than” that number, if negative then the converse holds.
LikeLike
I agree with @waldo. If the number is positive, there will always be more numbers available “less than” that number, if negative then the converse holds. OK, waitaminute, that only works with countable infinities, we’re talking R – real number system here aren’t we? My bad. Where’s Kantor when we need him?
LikeLike
If the shown number is positive, guess the other number is smaller.
If the shown number is negative, guess the other number is larger.
I don’t understand why you guys are even using any formulas.
LikeLike
They’ve designed the puzzle quite cleverly so you can’t do this. Bob doesn’t know what’s in the other envelope, only Alice does. But Alice doesn’t know which number Bob showed you. Everyone only has one piece of the puzzle so you can’t use… agressive techniques.
LikeLike
I just read the puzzle and all of your comments without having any idea what I was reading. The only thing I understood was that Maggie likes kittens.
And for the record, I can relate to Maggie.
LikeLike
Randall your solution sounds nice, but it’s wrong. Your assumption is that the distributions will be approximated by that logarithmic function. For the most part it will produce results higher then 50%. But the trick to that for any Guess Strategies, it’s impossible to produce a distribution strategy that drops below 50% if you can’t control which envelope to hand them. The problem gets very interesting if Alice controls the envelopes, I wonder if there is a Nash equilibrium.
The only way to raise your chances above 50% is to get close to approximation of the distribution function. Your function zooms quickly out for numbers near zero, making it good for distributions centered around 0. Suppose my distribution is the only two numbers are 99972 and 99973. Heck suppose its a uniform distribution of a random real between 0 and 1. Either way your strategy doesn’t beat 50%.
LikeLike
Aaron, do you honestly think that “lim x–>0+ of 1/x = +oo” is a “game theory paradox”? Do you honestly think that anyone in math sees this fact in that light?
You are clearly out of your depth, please stop using fancy words to describe elementary things.
LikeLike
I noticed in your gravity well ‘toon, that you missed a remarkably strong and highly localized gravity well. It seems the female breast, especially in pairs, seems to bend light so severely that one’s gaze is irresistibly drawn downward to the point that it is rare for most males to identify the eye color of an attractive woman.
It might be a significant scientific contribution to detect the limits of that event horizon.
just a thought.
LikeLike
Interesting math puzzle. Here is a possible follow up to the puzzle, which I have been thinking about:
How might the strategy be adjusted if we are given information about how Alice is choosing the real numbers?
For example, what is the optimum strategy if we know Alice used a Gaussian distribution to pick the two numbers? Some other distribution?
Or, how might other pieces of information about Alice’s decision making process be used to improve our strategy.
LikeLike
I’m confused. The whole point of the two envelopes problem is that switching has no benefit but can appear to if you misapply probability theory.
LikeLike
The answer is: yes, because Alice used envelopes with windows.
LikeLike
So ignoring all the lame math and problems with choosing a random number between minus infinity and infinity, you’re saying that if Bob shows me the number -inf, I would always be correct in switching, and if Bob shows the number +inf, I would always be incorrect in switching. There’s some probability distribution between the two extremes. Kinda like how in cards, if you draw a low card and want something higher, you’re better off drawing the next card from the deck. As far as mental masturbation goes, your problem’s better than nothing I guess.
LikeLike
Well… No matter the choice, you end up with a random number.
I suppose, being rich in random numbers, that I would keep the first envelope no matter its contents.
Oh my abstract envelope has a 2 and yours a 3,614,236.203321209? Big deal. I have six 3,614,236.203321209’s, and at least one 217,890,381.61999324059203.
Or am I missing the decimal point?
LikeLike
I would strap Bob onto a chair and take both envelopes…
LikeLike
@Susam: I think P(x = max(a,b) ) = P( x = min(a,b) ) = 1/2. The reason is because a and b are not random but are chosen by Alice, then Bob chooses randomly between these two numbers with a coin toss. Bob has an equal chance of choosing the envelope w/ the higher number as choosing the envelope w/ the lower number.
@Matt: I’m not sure, but doesn’t your formula prove that no guessing scheme can beat 50% if the envelopes are chosen randomly? Regardless of your guessing scheme, you have some p chance of guessing the other envelope is higher and (1-p) chance of guessing the other envelope is lower. If P(x = max(a,b) ) = P( x = min(a,b) ) = 1/2, then you still end up with a (1-p) * .5 + p * .5 = 1/2 chance of guessing correctly.
LikeLike
Because every positive real number has a corresponding negative real number, then there are an equal number of real numbers on either side of 0. Therefore, if the number in the first envelope is positive, then there are more real numbers greater than that number than there are real numbers less than that number. If the number in the first envelope is negative, then the opposite is true.
If the first number is positive, guess that the second will be lower. If the first number is negative, guess that the second will be higher.
LikeLike
Actually, the argument is correct, but could be made more precise:
If we take A and B as given with A<B, then X (the observed value) is a random number sampled uniformly from the set {A,B}. Given a value of X, we choose an independent number T uniform on (0,1) and guess that X=B (i.e., we're seeing the larger value) if T= p(X).
Conditional on the event {X=B}, the value of p(X) is p(B), and conditional on the event {X=A}, the value of p(X) is p(A), so the combined probability that we’re right is:
P((Guess X=A and X=A) or (Guess X=B and X=B))
= P(Guess X=A | X=A)*P(X=A) + P(Guess X=B | X=B)*P(X=B)
= (1-p(A))*.5 + p(B)*.5 = .5 + .5*(p(B)-p(A)) > .5, no matter what A and B are.
The nice thing about this approach is that Alice can’t “game the system” by choosing her numbers, even if she knows what our strategy is. (Of course, she can just pick numbers that are so large and close together that the probability isn’t measurably different from .5, but that’s another story).
LikeLike
What all you guys smoking ?
For a uniform distribution of real numbers
Pr(x) = 1 / 2 inf
Int ( 1 / 2 inf , -inf, +inf ) = inf / 2 inf + inf / 2 inf = 1
So we have our uniform distribution.
Now
Pr ( y > x ) = Int ( 1 / 2inf, x, +inf)
= inf / 2 inf + x / 2 inf
= 1/2 + 10
= 0.5
Pr ( y < x ) = Int ( 1 / 2inf, -inf, x)
= x / 2 inf + inf / 2 inf
= 0 + 1 / 2
= 0.5
I think you are left with the electric chair.
LikeLike
Since there is no such random sample of all real numbers, there is no way to simulate the game itself. So it is logical to assume that the domain is finite (not really all real numbers but just the ones which shall be written and put into a regular envelope) hence your chance will be better than 50% according to the original calculations.
Since Bob chooses the envelopes randomly, on can assume that Alice’s method of selection is random too.
LikeLike
Question:
Why doesn’t this, much simpler technique work?
If Bob shows you a number greater than or equal to zero, it is more likely to be the larger number. If Bob shows you a number less than zero, it is more likely to be the larger number.
Rationale: Let a be the number Bob showed you. Let x be the number of real numbers with values greater than a. Let y be the number of values less than a but greater than zero.
Assume a is positive.
There are the same number of real numbers with values greater than a as there are with values less than -a. There are also the same number of values less than a and greater than zero as greater than -a and less than zero.
The probability that a random number not equal to x is greater than x is x/2x+2y+1 for all values of x greater than zero. The probability that a number is less than x is x+2y+1/2x+2y+1. Since x and y are positive and non-zero for any real number, x+2y+1>x, and therefore if x is greater than zero, the probability of the other number being less than x is greater than 50%.
It’s trivial to prove the other half: that if x is less than zero, there is a greater probability of a random number being greater than x.
In plain English: For any positive value, there are the same number of real numbers below that value as there are above value, plus the twice the number of real numbers that exist between that value and zero (plus one value for zero). The reverse is true for negative numbers.
Yes, I know that by the rules of cardinality, there are the same number of real numbers above any given real number as below it, regardless of whether that number is above or below zero, but my method just seems to make so much sense!
LikeLike
Munroe: Read the above comments, and read them well. Do you think maybe you’re aiming a bit high with the trite paradoxes?
LikeLike
For the first time in my life, I’m finding myself in disagreement with you, Randall. It just feels too fishy to me.
Using this method, let x be the number in the first envelope. Let A be the event in which the larger number is chosen and B be the event in which the envelopes are switched. I think it’s probably safe to say that events A and B are independent and that P(A)=1/2.
I’ll use “~” for event complements and “*” for event intersections. Then (and I’m very sorry if you don’t speak probability)
N = P(Get the larger number)
= P(See larger and don’t switch) + P(See smaller and switch)
= P(A*~B) + P(~A*B)
= P(A)P(~B) + P(~A)P(B) as A and B are independent
= (1/2)[1-p(x)] + (1/2)p(x)
= 1/2 – (1/2)p(x) + (1/2)p(x)
= 1/2
Note that the value of p(x) simply drops out of the equation, so there is no function that could make this work. As far as evidence with a Monte Carlo method, I agree with Aaron and Michael that the finite bounds and/or symmetry around zero that cannot be avoided on a computer completely change the problem. That said, please tell me if I’ve made an error in any of the above. It is 6:00 in the morning, after all.
LikeLike
“all the young girls love Alice…tender young Alice they say”
LikeLike
xkcd blag, 10/11/2006 –
“I always hated those ‘lateral thinking’ puzzles — the ones where they said “oh HO, I never told you that the doctor’s mother was a midget and this was all happening a space station! Don’t you feel dumb now?‘”
xkcd blag puzzle, 2/9/2010 –
“Choose a random real number between 0 and 1.”
xkcd blag puzzle solution –
“An important thing to keep in mind here is that there’s no such thing as a random sample of all the numbers.”
LikeLike
waldo: A real number is any number that’s not imaginary or complex (those with an i). Real numbers are comprised of rational numbers and irrational numbers, e.g. 3/4 and pi. A rational number is any number that can be represented as a fraction of two integers (whole numbers, both positive and negative) m/n. An irrational number is any number that can’t.
So Alice could choose 3 and 3.00000000000000000000000000000000000100000000000000000001010101010101011010000001101101010110…
LikeLike
Well I think this is just nifty. No complaints.
LikeLike
the envelopes are most likely the same size. why does every one care about the numbers? it asks which envelope was bigger!
LikeLike
Funnily enough I came across this puzzle recently in the paper Games People Don’t Play, which traces the puzzle to a short chapter in a book on communication & computation from 1986. They also describe a variant which does not have a winning strategy.
LikeLike
plain said: as we are talking about real numbers we can go till double.positiveinfinity that make the chance the other number is bigger higher than the chance the other number is lower… simply by the mass of possibilities…
LikeLike
I don’t see how this solution works and I wish the author would follow up in response to the objections that have been raised so far.
What exactly is the game being played here?
Let us say that the game is played exactly once. Then Alice chooses two numbers A, and B. Bob is shown A and has to guess whether B is larger or smaller. Can he do it with probability greater than 50%?
NO. Of course not! What is Alice’s decision space? It is the set of all functions {A, B} -> R.
You are asking Bob’s strategy to be effective against any arbitrary function Alice chooses. In order to get the expectation value of Bob’s strategy you would have to do some sort of integral over this space of functions and to be honest you are really pushing it if you expect such a space to have a sensible uniform probability measure.
If the game is played iteratively than Alice chooses a sequence of such functions arbitrarily. She doesn’t even have to do it randomly! Arbitrary is a lot more general than randomly. Good luck even defining the problem properly.
The proposed solution is looking at the wrong space. Look at it this way: What proportion of Alice’s possible strategies make Bob win with probability less than 50%? It doesn’t even make sense.
LikeLike
Ignore my last comment. I misread the problem as letting Alice choose the number she gives to Bob. If Bob gets the numbers randomly then this strategy does work.
But if Alice chooses the number Bob receives, then there is no way for Bob to do better than break even.
The key is that Alice doesn’t control the information Bob gets.
LikeLike
Good thing you stated that the numbers were real. Otherwise Alice could have given him an empty envelope: Bob: “There is nothing in the envelope.” Alice: “Yeah there is! It’s just Imaginary.”
LikeLike
This problem is actually really easy if you rephrase it.
Generate A and B and then find D=B-A
The new problem is given A, find the sign of the difference D.
But if we say that there is an equal chance for any real number, then the new problem is the same as generating A and D randomly and trying to figure out the sign of D from A. (easy concept, invertible transformation between D and B gives a shifted probability distribution but I assume that shifting the distribution does not change it!)
These are independent trials, so A has no impact on D…therefore it is a 50/50 chance for D to have a positive sign/negative sign.
The best way to understand the problem is that there is no average of all real numbers, any number works as an average because there are just as many on either side of every real number .
You can’t describe it using a finite length as in the XKCD solution because both lengths are equal and infinite, regardless of the point you are at. Their solution implicitly gives a longer length and a shorter length on either side, which has no real meaning in terms of probability. This length shifting changes the guessing strategy, but it cannot affect the probability of guessing the right answer, which is always 50%.
The only way to get better than 50% is if the difference is somehow dependent on the first number, and for this you must have some central tendency for the original numbers.
P.S. Math Majors Rock
LikeLike
By the way, this works for integers too.
LikeLike
The same idea works for integers too.
LikeLike
Imagine an infinite line with zero at the midpoint.
If the first envelope contains a number to the right of zero I guess the other number is smaller than the number in the envelope. There are more real numbers to the left of the number than the right (the line is “bigger” in that direction).
If the first envelope contains a number to the left of zero I guess the other number is greater than the number in the envelope. There are more real numbers to the right of the number than the left.
LikeLike
sorry, it looks like part of my comment was accidentally deleted before I posted it… instead of
if a p(switching envelopes, if you guessed “b”)
I meant to say
if a > b, then p(switching envelopes, if you guessed a) < p(switching if you guessed b)
is this comment too argumentative? is that why it wasn't posted directly?
LikeLike
I think Matt’s right here, although I don’t understand the specifics. Simplify the original problem, though, and forget the girl and the envelopes. You’re picking two random numbers, and evaluating the probability of guessing correctly that the first is higher than the second, or vice versa. It’s trivial. These ‘proofs’ are like the proofs of 1=0 – the errors can be made very subtle, but somewhere along the line you must have made a mistake if you’ve proven something that is obviously false.
LikeLike
@Waldo:
A real number is any point on the number line. Doesn’t have to be a fractional number, or a whole number, as long as when you see it you can draw me a number line and mark it on there, it’s a real number.
As for the solution, the way of explaining it is overcomplicated. Look at it this way:
Instead of using that function, pick a random real number (corresponds with your random number between 0 and 1, but doesn’t use that function)
If the number you saw is smaller than the number you chose, say ‘Higher’, and if it’s higher, say ‘Lower’.
If both numbers are higher than the one you chose, you have a 50-50 chance of winning. If they’re both lower, you have a 50-50 chance of winning. If they straddle your number, which happens with positive probability, you’re guaranteed to win. Therefore this strategy has a greater than 50-50 chance to win.
LikeLike
I am not a math major. However, I may have a proof that this doesn’t work in the integers. I would assume that this would map to the reals but it’s much trickier to do.
Proof is as follows:
Consider A, B both integers in the bounded set (-N, N). A is the number in the envelope you chose, B is the number in the other envelope. We’ll also say that A is not equal to B.
Given the above it’s pretty trivial to calculate the probability that B is greater or less than A:
P_less = (A + N – 1) / (2N – 2)
P_greater = (N – A – 1) / (2N – 2)
(Note P_less + P_greater = 1)
Now simply take the limit of both equations as N->infinity. You will find P_less = P_greater = 1/2.
Therefore, given two numbers from any unbounded set (I expect the reals to apply) then the probability of one number being greater then the other number must be exactly 1/2.
—
The only way the strategy works is if the set is somehow bounded. I would say that this or a similar assumption was made based on the statement “there’s no such thing as a random sample of all the numbers”. However, I find this hard to buy seeing the solution must be independent of the procedure used to choose the numbers.
The non-existence of a theoretically perfect random number generator is hardly proof of this strategy. In fact the more unbounded (or close to perfect) the random number generator is the closer you will get to a 50% chance of winning. Even with modest bounds the probability of winning is extremely close to 50%: consider that p(10) is 0.99995 and p(30) already has thirteen 9’s meaning that any positive number with more than 2 digits almost guarantees that you choose ‘less than’.
LikeLike
If Alice knows that you are going to use the p(x)=1/(1+e^-x) function, can she select numbers that will always reverse the favorable probability?
LikeLike
…wow… I was kinda holding on at the end of the post… but after reading the comments…
i think math nerds need to follow a simple rule by Thoreau
Simplify, simplify (haha… pun, kinda… but)
i understand that theres math lingo, and then theres using explict when clear will do
LikeLike
This is a fascinating trick, but does not seem to work. I’ve run a series of simulations using some real data fitting the criteria. I downloaded daily exchange rate movements, as they are basically random and with approximately 50% chance of being positive and 50% chance of being negative. I used more than 2700 data points with the daily open price as Alice’s “known” number and and the same day’s close price as Alice’s “unknown” number. I run this simulations 100 times, each time with different random numbers compared to p(x), and the final distribution of correct “guesses” was 46%. Maybe it would be over 50% if I run 10^6 simulations, but I highly doubt so, given the already high number of the data points. I’m pretty sure this simulation setup is consistent with the directions. So, if you guys are still around, I wonder what you think about the result.
LikeLike
This must be Randall’s way of fighting overpopulation: throw in an issue and let people kill each other over it.
LikeLike
@Waldo: http://lmgtfy.com/?q=real+numbers&l=1
LikeLike