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 
Also see http://mathoverflow.net/questions/9037/
LikeLike
Just a quick proof for the fact that a step function gives you better than 50% chance with hopefully more basic maths 🙂
I’m going to choose the function: “say higher for negative numbers, lower otherwise”. (But you can pick your favourite number to step on if you like; proof holds for any number.)
Alice could pick the following types of pairs:
A. Two non-negative numbers
B. Two positive numbers
C. One non-negative, one negative
Say there’s probability p it’s C. Clearly p > 0.
It’s clear that if it turns out to be A or B, you’ve got a 50% chance of making the right call. But if it’s C you have a 100% chance of picking the right one.
So your chances of being right are 0.5 * (1-p) + 0.5 * p, which is > 0.5.
LikeLike
Err, last line should obviously be that your chances are:
0.5 * (1-p) + 1 * p, which is > 0.5
LikeLike
But of course that proof only holds if you don’t read the question correctly 😉
LikeLike
Making any assumptions about the probability density of the space Alice will select from is silly. OK, cleverly, you discovered that there is a function which could plausibly be used as a density function with the right sort of properties. But are there not other functions with different distributions which are equally valid?
LikeLike
I did a small script to test this theory and I was astonished to find out that the percentage of times in which it guessed correctly was a more or less constant 55% during my tests.
I realise that I didn’t use true random numbers, but its proof enough to me that this method works.
Thank you for getting my neurons firing =P
LikeLike
Why not just ask Alice? It says you have to guess, but it doesn’t say that you have to do so in isolation….
LikeLike
Ha ha ha!!! Are you kidding me!
What a load of bollocks.
The problem reduces to…
Alice: “TEN!!!”
Bob: “Eh?”
Alice: “Am I thinking of a number bigger or smaller than ten?”
Bob: “What, out of all possible numbers???”
Alice: “Yes”
Bob: “Err….”
Obviously – I mean, quite BLATANTLY – there is no way to increase you chances above 1/2. It doesn’t matter how many times Bob runs ’10’ through his Magic Xkcd Probabality Bollocks-o-matic (TM).
I mean this is just so, so dumb.
“N = 0.5 * (1-p(A)) + 0.5 * p(B)”
Oh man. That hurts. That really hurts.
The calculation should be…
“N = 0.5 * (1-p(x)) + 0.5 * p(x)”
which comes to…. (drumroll)
0.5!!!
TO THE STOCK MARKET MEN!! TO THE STOCK MARKET!!!!
LikeLike
Hi. There are similar ‘paradoxes’ to this in analysis, but the presentation above is incorrect. The problem and strategy described are well-defined, but the conclusion fallacious. The crux is the [unjustified] application of conditional probability:
> N = 0.5 * (1-p(A)) + 0.5 * p(B)
Yes, N is strictly greater than one half. But it is not the probability that we guess correctly. In fact (writing t for the uniform [0,1] random variable):
P(guess correctly) = P(guess the other number is greater) P(Bob opened the smaller number) + P(guess the other number is smaller) P(Bob opened the greater number) = P(t = p(x) ) P( x = min(a,b) ) = (1-P(x))*1/2 + P(x)*1/2 = 1/2
[x is a random variable taking the value a or b each with probability one half. a,b are not random variables but fixed by Alice.]
It would be cool to see a proof that NO strategy can be correct with probability more than one half.
LikeLike
Some inequalities and the text between them in my post above were swallowed as HTML. Hopefully this will appear correctly:
P(guess correctly) = P(guess the other number is greater) P(Bob opened the smaller number) + P(guess the other number is smaller) P(Bob opened the greater number) = P(t is less than p(x) ) P(x = max(a,b) ) + P (t is greater or equal to p(x) ) P( x = min(a,b) ) = (1-P(x))*1/2 + P(x)*1/2 = 1/2
LikeLike
Arguments ad hominen attacking Alice (such as whether her choice of a,b has a distribution) are irrelevant to the problem. a,b are a pair of distinct real numbers. Probability theory begins where Bob observes x, a sample from a random variable taking values a and b each with probability one half.
The logistic function itself is unimportant. The only properties used in xkcd’s argument were its limits and that it is strictly increasing. A similar continuous function – such as arctan(x) / pi + 1/2 would suffice. They are distribution functions that may define random variables, but this is irrelevant too.
LikeLike
I choose .9 repeating and 1 as my two numbers.
How does your probability stack up now?
Enjoy.
LikeLike
Alice, knowing that Bob thinks this way, can pick, for her two numbers, g and g + 1/g, where g is a googleplex. Or, better, g and g + p/g, where p is chosen by coin flip to be +1 or -1. This reduces any gain from the use of a monotonically increasing function to a value so small that it’s 50/50 for all practical purposes.
LikeLike
The assumption is that Alice is not actively attacking your guessing system.
LikeLike
@Matt: I don’t believe your criticism of the posted strategy is correct. You’re computing the conditional probabilities that we will guess higher or lower than the revealed number based on the value of that number, but computing the unconditional probability that Bob picked the higher or lower envelope without considering the revealed value.
We don’t know what method Alice used to pick her numbers, but whatever method she used must generate some actual, concrete distribution of results. Therefore, the posterior probability that Bob opened the envelope with the greater/lesser number is not 50% after we know what the actual number is. For example, if Alice happens to decide she’s going to pick random integers in the interval [0, 100], then when Bob opens an envelope containing the number zero, there is NOT a 50% chance that he picked the higher envelope.
The point is that the given solution yields greater than a 50% chance of being correct for any PARTICULAR method Alice might be using to pick her numbers (even though we don’t know what that is). I invite you to try to find a counterexample (acknowledging that your inability to find one can’t prove its nonexistence).
LikeLike
The answer’s obvious: ask Eve. I bet she saw what Alice was writing.
LikeLike
Michael: I mean that there doesn’t have to be anything special about the zero point in the solution. If you don’t want to use the zero-centred p(x), then you can use p(x-12) or something.
Matt: Agree with your last post, but I justify the conditional prob this way:
P(guess correctly) = P(open the smaller number then switch) + P(open the larger number then don’t switch)
= P(open the smaller number)P(switch given you opened the smaller number) + P(open the larger number)P(don’t switch given you opened the larger number)
If we use xkcd’s strategy and assume a < b I get xkcd's expression for N.
LikeLike
In response to Matt, it appears you’re arguing in your first two posts that the method won’t work, i.e. that you will always be right 50% of the time? If you just pick any two numbers you’ll always get a better chance of winning if you follow this strategy, (or any appropriately modified strategy with the same properties). Also, I would say that in your 2nd post you can’t use an x that always takes on a different value and combine it. I.e. .5*P(x_A) + .5*(1-P(x_B)) = .5, since the P(x_A = x_B) = 0.
LikeLike
OK.
P(guess correctly) = P(pick A and say “bigger”) + P(pick B and say “smaller”)
=P(pick A)*P(say “bigger” given that we picked A) + P(pick B)*P(say “smaller” given that we picked B)
=.5(1-p(A)) + .5p(B) > .5
LikeLike
@ bradluen
No,
P( correct ) = P( got bigger ) * P( said “bigger” ) + P( got smaller ) * P( said “smaller” )
This is…
0.5 * ( 1 – p(x) ) + 0.5 * p(x)
which is (suprisingly)
0.5
The problem reduces to Alice asking “Am I thinking of a number bigger or smaller than 100?” (or whatever number you get). Obviously if you don’t know how she is picking her numbers, you can’t give yourself an edge here. In fact, however you think she is picking her numbers, it could in fact be the exact opposite of that (reflected around 100)!
LikeLike
The plane on the treadmill does not take off!
LikeLike
Odd that I’ve never heard of this game or similar being offered in a casino – clearly in a situation where the house is the guesser.
LikeLike
Cute problem – (cute as kittens in fact!)
And it leads to an interesting follow-up:
For a given distribution of the envelope numbers how can we find the *optimal* choice(s) of the p(x) function?
LikeLike
I have an issue with the proposed solution, in the step: Choose a random real number between 0 and 1. It is established that there is no uniform probability distribution on the reals. Therefore, there is no such distribution on the interval (0,1). Does not the guess lower/higher part of the strategy rely on such a distribution?
My thought is (and of course I may be wrong) that you can calculate the function p(x), and it has the desired properties for comparison with a random number from a suitable distribution, but that there exists no appropriate distribution from which to select a random number for comparison. Might anyone have something to support/refute this idea?
LikeLike
@Rikard: I thought the same thing but the trick is that your method has to work with >50% probability *given any strategy.* Holding on to positive numbers definitely doesn’t succeed if Alice’s strategy is to choose two positive numbers – it will be 50/50. Perhaps it would work if Alice had to choose a strategy randomly from the space of all possible strategies but I don’t know if that statement even has any meaning.
LikeLike
Matt,
In your expression: P(t is less than p(x)) P(x = max(a,b)) + P(t is greater or equal to p(x)) P( x = min(a,b)), x is not same in both the terms.
In the first term x = max(a, b) and in the next term x = min(a, b). But in the next step you are assuming them to be the same and cancelling them to get 1/2.
Your next step is:
(1-P(x))*1/2 + P(x)*1/2 = 1/2
However, the next step should be:
p(max(a, b) * (1/2) + (1 – p(min(a, b)) * (1/2) = (1 + max(a, b) – min(a, b)) / 2.
I am also confused about why you are using the upper case P(x) instead of the lower case p(x) in your last step.
LikeLike
Seems to me that everyone is overthinking the strategy, but I could be wrong.
Is there anything wrong with thinking that half of the non-zero real numbers are 0?
In which case, if the first number is >0, there is at least a 50% chance of the other number being negative, + the chance that it is positive, but less than the first number. (Which would make the probability more than 50% to guess “lower”)
If the first number is negative, the chance that the other number is higher is 50% + the chance that the second number is negative, but still larger than the first number, (so, more than 50%).
The problem I see with that analysis is that it doesn’t really account for infinity, just an arbitrary limit somewhere, and that’s not the same thing.
(You could equivalently say that half of the integers are above 1, and half below 1, since both sets are countably infinite)
LikeLike
Very interesting. But what happens when a mathematician encounters an artist?
LikeLike
I agree with Susam (and xkcd) and disagree with Matt, I believe (against my first impression) that the original solution is right.
(But I agree with Matt in his other observations: The logistic function itself is unimportant and the Arguments ad hominen attacking Alice (such as whether her choice of a,b has a distribution) are irrelevant to the problem)
Alice picks two numbers, let’s call A the smaller and B the larger.
Then the conditional probabilities are straightforward
P(Bob guess right | Bob picked A) = 1 – p(A)
P(Bob guess right | Bob picked B) = p(B)
P(Bob guess right) = 0.5 * (1- p (A)) + 0.5 * ( P(B) ) > 0.5
LikeLike
Here’s my stab at a more clear explanation of what’s going on. We start by assuming that there are two unknown numbers 0 < p(x) < p(y) < 1. (From here on, I’ll just write x for p(x) and y for p(y)). We have no other information about x and y. We choose a number t uniformly at random from (0,1). So we have three possible cases:
(1): t < x < y This has probability x of occurring
(2): x < t < y This has probability y-x of occurring
(3): x < y < t This has probability 1 – y of occurring
We are shown a number ‘z’ which is ‘x’ with probability 1/2 and ‘y’ with probability 1/2. We guess that the other number is lower than z if t < z and guess that the other number is greater than z if t > z.
In case (1), we will always guess ‘greater’, and so we will be right 50% of the time.
In case (3), we will always guess ‘lower’, and so we will be right 50% of the time.
In case (2), we will always guess correctly. Since case (2) has a non-zero chance of occurring, our chances are greater than 50%. Precisely, the probability of being correct is
(x-y)*(1) + (1 – (x-y))*(.5).
LikeLike
Arg. In case (1) we always guess ‘lower’ and in case (3) we always guess ‘greater’.
LikeLike
One way to look at the question is to ask whether the number Bob sees reveals any information about the other number.
Randall’s argument is that since there is no selection process that assigns equal probability to all numbers, any number one selects contains some information. This is essentially a Bayesian argument, as it assumes a prior probability distribution on Alice’s numbers. Bob’s probability of guessing correctly is a function of the entropy of Alice’s process, and its similarity to the likelihood function he assumes (the logistic function in Randall’s example).
Matt claims that the numbers in the envelopes are pre-existing fixed numbers. In this case no matter what number Bob sees, there are an infinite number of larger and smaller numbers, so he has gained no information by seeing it. Thus no strategy that Bob employs will be better than guessing. This is a Frequentist perspective, because the parameters of the problem are treated as numbers instead of random variables.
Either approach, taken to it’s appropriate conclusion, gives the same result. Although there is no process that samples the reals equally, there are an infinite number of possible processes on which Bob’s strategy performs arbitrarily badly. In the best possible case (Alice’s choices follow a logistic distribution, as Bob assumes), Bob will be right 67% of the time on average. If Alice chooses a distribution that is strongly centered away from 0, however, Bob’s strategy quickly becomes indistinguishable from random guessing. Consider Norm(1000,1). Bob’s expected probability of being correct in this situation is practically indistinguishable from 0.5. As the mean moves farther away, it can be made arbitrarily close. Since the problem statement says “no matter what procedure Alice uses”, we should marginalize over all possible sampling processes. Even if we restrict ourselves to Gaussians, I claim Bob’s probability of being correct will converge to 0.5 almost surely. My argument is heuristic, and I haven’t computed any of these expectations analytically, but I think it’s sound.
Thus no matter what perspective one takes, the answer must be no, and I have been nerd sniped.
LikeLike
This is fascinating, but my math skills are horrendous (what am I doing here again? lol). Can somebody please explain to me what this all means in English? Is it just that you have a better than 50% change of guessing correctly, no matter what you guess, or is there some sort of guessing strategy? I don’t get it.
LikeLike
Easy. Just get Alice to write the same on both pieces of paper! ha ha ha.
LikeLike
Aaron Meurer wrote:
>> Then, because the probability that x = 0 is exactly 0 (see link in original >> post), then x != 0.
That is assuming that x is not zero, and when doing that you are assuming that 0 is not a real number in the first place. It is self-reflective; you can’t prove that 0 is a real number by assuming it is a non-real number. Therefore 0 is undefined. Either that, or it’s real…hehehe
LikeLike
This solution would work, if Alice generated A and B using procedure: take two random a and b from uniform on (0,1), then A= ln(a/(1-a)), B=….
But instead of this she can use A= ln(a/(1-a) +15, or A = atn(2*a/pi) or any other way transform (0,1) to (-Inf, Inf). If you do not fix priors, solution is indefinite.
LikeLike
Correct me if I am wrong but… Let’s say the 2 numbers are rather random. Let’s call them A and B. So for each one of them there’s a 50% chance that it’ll be negative and 50% chance for positive (+ a very small chance for a 0). So we have:
A B
+ +
– –
+ –
– +
As far as I can tell each one of those outcomes is equaly probable. So now let’s say:
“I claim the other number is lower IF the one I got is positive” and
“I claim the other number is higher IF the one I got is negative”.
In 1st two cases I have a ~50% of winning… but in the other two it’s a 100% – so in total I have 75% FTW. Am I correct?
LikeLike
@:
I made an extreamly simplistic code in C and it seems to agree with me:
#include “conio.h”
#include “stdio.h”
#include “stdlib.h”
int main()
{
int win =0;
int x=10000;
for(int i=0; i0 && a>b)win++; else if(a<0 && a0 && b>a)win++; else if(b<0 && b<a)win++;}
}
printf("the ratio is: %i/%i", win,x);
getch();
return 0;
}
LikeLike
Bah, it go damaged – please delete this and previous comment, I’ll upload it somewhere
LikeLike
I’ve made a simple C code to check this and it seems to agree with me:
http://snipt.org/vrn
(yeah rand is inperfect and those are int, not float – but it should work non the less)
LikeLike
Ok, I’ve noticed that for some functions (like: random positives only) my method gives no more than 50%. Disregard it in such case ;p
LikeLike
“Choose a random real number between 0 and 1.” — isn’t that impossible, by the same argument?
LikeLike
Ok, I’m not a mathematician, but this just seems silly to me.
Intuitively: we start off with two arbitrary real numbers, having no relation to each other, other than the fact they’re not equal (I’m assuming there’s no psychological component to this puzzle). Whatever number you see in the envelope, there exist just as many real numbers that are lower as there exist that are higher, so it seems to me like equal chances.
With the strategy as it stands, if both numbers are 0, you’ll guess the other one is lower. But as Michael said, 0 is an arbitrary turning point in this particular strategy, since 0 is not special in the problem. There are an infinite number of equally (in)valid strategies like that one, but with different turning points (bradluen). It should at least be a hint that each of those strategies will yield different `probabilities of guessing correctly’.
I’d love to be proven wrong. Is there a proof?
LikeLike
This basically just says if x is positive, guess lower; if x is non-positive, guess higher or perhaps choose a random real number and if it is less than x guess lower. This works because half of the real numbers are positive and half are non-positive.
LikeLike
Where does the problem begin? Does it begin when the two numbers are picked, or when the first number is seen?
The solution seems to hinge on the former, and the latter seems to produce a probability of 1/2.
I believe that the issue here is proving that the two are different.
On a sidenote, here’s a problem that this discussion makes me think of: If Alice can choose which envelope to show you, can she make your chance of winning no higher than 50%?
LikeLike
Can someone spot the bug here: http://i47.tinypic.com/sl05co.jpg
When I simulate 3 strategies, I get the following results:
The strategy using p(x)= 1/1+e^-x = about 50 percent
If A is positive guess *less than* else guess *greater than* = about 75 percent
Choose another random number, if it is < A, guess *less than* else guess *greater than* = about 67 percent
LikeLike
There was a bug in the strategy 1 simulation I posted earlier. In the new simulation (http://i49.tinypic.com/2d2ejol.jpg) the p(x)= 1/1+e^-x strategy appears to be in lockstep with the strategy: If A is positive guess *less than* else guess *greater than*
LikeLike
This is nonsense what you’re saying. This logarytmic things might sound cool but it isn’t clever. If you see positive number you can say the other is smaller, if you see negative – it’s bigger. And i have probablity of winning if number shown is x: inf+Abs[x]/inf-Abs[x].
LikeLike