Math Puzzle

[jemidiah]

A friend of mine showed me an interesting math puzzle on xkcd (http://blog.xkcd.com/2010/02/09/math-puzzle/).

1. Alice picks two real numbers and puts them in (abstract) envelopes. No information is given as to how she chooses them.
2. Bob picks one of the envelopes by tossing a fair coin.
3. Alice shows Bob the number in the envelope he chose.
4. Bob is forced at gun point to say if the other number in the other envelope is "higher" or "lower" than the number he's already seen.

The question is, does Bob have a strategy which would allow him to guess if the unseen number is higher or lower with better odds than 50-50?


The xkcd post says, "yes" and gives the following strategy.

1. After Bob has seen the number in the envelope, he calculates p(x) = 1/(1+e^-x)), where x is the number he saw.
2. Bob randomly chooses a real number t from 0 to 1, uniformly.
3. If t is lower than the value calculated in 1, Bob says "lower"; if t is higher than the value calculated in 1, Bob says "higher". Thus, Bob says "lower" with probability p(x), and "higher" with probability 1-p(x), since p(x) is bounded between 0 and 1.

The post then computes the probability of guessing correctly:

So for any pair of numbers, if you call the smaller one A and the larger one B, you have a (slightly) better chance of guessing “lower” if you saw B than if you saw A. Your overall chances of guessing correctly — given that there is a 50% chance you’re seeing A and a 50% chance you’re seeing B — are:

N = 0.5 * (1-p(A)) + 0.5 * p(B)

Since we're saying A < B, we can say that N > 0.5, because we chose p(x) cleverly. Since p(x) is always increasing, p(A) < p(B). Thus 1-p(A)+p(B) > 1, so N = 0.5 * (1-p(A)+p(B)) > 0.5 * 1 = 1/2.

The result is very unintuitive, though, and the OP says that he initially thought there wouldn't be a workable strategy. So, my question is, do you buy this, or do you think there's a hole?

[Milk]

I'm not great a maths but I enjoy it, I don't get this.

P(x) approaches 1 too quickly and no information is given on how Alice chooses her numbers. Am I understanding correctly; Bob sees the number 4, he then calculates a p(x) of 0.982?

[jemidiah]

Yes, you've calculated p(4) correctly. The thing is, negative x's can be chosen as well as positive x's. For instance, p(-4) ~= 0.018, so for negative values of x Bob will generally say "higher", and for positive values of x he will generally say "lower". On the whole, he'll say "lower" about as often as "higher" (note: this last sentence is very much lacking in rigor).

[Milk]

I think get it now. Bob might as well forget about the bell curve and the coin toss altogether and just assume that the other number is of opposite sign.


I don't fancy Bob's chances either way.


Edit: I don't like Alice's numbers having a mean of 0, it does not seem quite right.

[jemidiah]

To be technical, it's not a bell curve. If you graph it, it's more of a snake that doesn't slither. Why would he assume the unseen number is of the opposite sign?

[Milk]

Sorry the function smelled kind of Gaussian, I did not actually graph it. Edit: I see now, it's like a tan curve, doh! obvious now I think about it.

He might as well assume the other number is of opposite sign because the strategy pretty much does that anyway, it just throws a bit of chance in to mix with the coin toss.

[jemidiah]

To be clear, there's a coin toss (which doesn't depend upon Bob's strategy) choosing which envelope Bob picks, and for the listed strategy there's a uniform random number generation. I'm not sure what you're referring to with the "bit of chance" mixed in with the coin toss.

The key part of the argument is the determination of N, and showing that N > 1/2. Since N gives the probability of winning with Bob's strange strategy, that means he has a > 50% chance of winning, which is unintuitive, and why I posted the puzzle :).

[Milk]

:blush: I was a little tipsy last night, by coin toss I was thinking about the part where Bob randomly determines the other real number between 0 and 1. Which is obviously nothing like a coin toss :blush:

I'm still not sure that Bob is any better off employing the above strategy over the strategy which assumes the other number will be slightly more likely to be of opposite sign.

Am I right in thinking this is very much about Bob improving his apparent 50%50% odds by a very very small amount?

Thank you for bearing with me.

[jemidiah]

For "most" choices Alice can make, the N value is indeed very close to 1/2 (but slightly over). The trouble with a strategy where Bob guesses that the other number has a sign opposite to the one he saw is that Alice could decide that she only likes positive numbers, following Bob's predictions and actually making him guess wrong more often than right, putting his probability of winning at < 50%. They key is, a strategy has to work no matter what Alice feels like doing.

[gmiller]

Hi Dude,
thanks for sharing math puzzle at blog.xkcd. I like math puzzle and I enjoyed them.

[opus]

Although i don't really get the math provided, it seems very clear to me that a strategy of chosing the opposite sign will give 50+% chance. Although the real numbers are unlimited going higher and lower, you have for any number A a probabilty of (unlimited plus a)/(2 *unlimited) if you choose a number with the opposite sign and "only" (unlimited -A)/(2*unlimited) in the other case.

[jemidiah]

If Bob always decided to guess "lower" if he sees a positive number and "higher" if he sees a negative number in the first envelope, he should get a probability of winning of at or higher than 50%. However, Alice can ensure Bob's probability of winning is exactly 50% and not greater than 50%, which is worse than the above strategy which purports to give a strictly greater than 50% chance of winning. Suppose she always puts a 1 and a 2 in the envelope. No matter which envelope Bob sees, he'll guess "lower" since they're both positive. He sees 1 with probability 1/2 (due to the coin flip), in which case he always loses. He sees 2 with probability 1/2, in which case he always wins. So, his probability of winning is exactly 50% in this case--not higher, exactly equal.

[opus]

That is correct, however it is changing the setting. First of all your strategy is for Alice, not for Bob. And secondly in your strategy Bob has to use a fixed strategy. I call that cheating!

[NickThissen]

I must say I don't understand the reasoning behind this, but if it is correct then it is quite a remarkable result. Intuitively I think everyone would say it would be 50%.

The strategy of saying 'higher' if the number is negative and vice versa doesn't make much sense to me though. For that to work, I would think that the numbers chosen by Alice would be completely random, between minus infinity and infinity. In real life, ask any person to think of any random number, I'm sure more than 90% would think of a positive number. Since the question explicitly says no information is given about how the numbers are chosen, we cannot assume that the numbers are chosen completely at random, so I would say that Alice choosing two positive numbers would be more likely.

[opus]

.... and she is a female, both numbers are probably using only two digits. (the actual whereabout of the poster of this is not known ;-))

[jemidiah]

That is correct, however it is changing the setting. First of all your strategy is for Alice, not for Bob. And secondly in your strategy Bob has to use a fixed strategy. I call that cheating!

Alice is unrestricted in how she chooses the numbers. I just gave a particular example of a strategy she may use. Again, the trick is that the solution in the OP for Bob's strategy makes him win *no matter how Alice chooses* with probability strictly greater than 50%. If Alice can choose in one particular way and reduce Bob's chance of winning to exactly 50%, Bob's strategy fails to solve the problem.

I just fixed Bob's strategy to use something like what you mentioned about negatives. Feel free to make his strategy as complex as you like :).

[jemidiah]

It might be nice to give an example. Alice must choose two numbers. While the problem statement doesn't explicitly say it, she must choose two different numbers--if she can choose the same number twice, Bob can't win. Let's say she chooses ln(2) ~= 0.6931 and ln(3) ~= 1.0986, where ln is the natural logarithm (I chose these to make the numbers later pretty). Using Bob's strange "calculate 1/(1+e^-x)" strategy, let's find his odds of winning.

Since Bob flips a coin to choose which envelope he sees, he has an equal, 50/50 chance of seeing either number. Say he sees ln(2). He then calculates 1/(1+e^-ln2). Using rules of logarithms and exponents, this is 1/(1+(2)^-1) = 1/(1+1/2) = 1/(3/2) = 2/3. Thus, he guesses "lower" with probability 2/3 and "higher" with probability 1-2/3 = 1/3. Since ln(2) < ln(3), he must say "higher" to win, so he wins 1/3rd of the time that he sees ln(2). He's got some ground to make up.

If he sees ln(3), he calculates 1/(1+e^-ln3) = 1/(1+1/3) = 1/(4/3) = 3/4, giving him a 3/4 chance to say "lower" and a 1/4 chance to say "higher". Since ln(2) < ln(3), he must say "lower" to win, so he wins 3/4ths of the time that he sees ln(3), which is quite good.

Since he sees ln(2) half the time and ln(3) half the time, his overall probability of winning is

0.5*1/3 + 0.5*3/4 = 0.5*(1/3 + 3/4) = 0.5*(4/12+9/12) = 0.5*(13/12) > 0.5.

That is, his chances of winning if Alice picked these two numbers are indeed better than 50-50. The above calculation for N substitutes arbitrary numbers A and B in for ln(2) and ln(3), but the result is unchanged.

[opus]

Would you believe that any number combination could result in a 100% chance to win?
Try 20 and -20.

[Milk]

Although Bob had a valid strategy he still unfortunately took a bullet.

Eric finds himself in the same situation.

Eric has a very similar strategy, the only difference being he uses a different generalized error function(??) p(x) = 1/(1+e^(42-x))) which assumes the mean to be 42 instead of 0. Now Eric is not great at maths but reasons that Alice's system is slightly more likely to have a bias in favor of positive numbers over negative and Eric also happens to like the number 42.

Does Eric have a valid strategy?

What did Bob do to derive his function?

[jemidiah]

Would you believe that any number combination could result in a 100% chance to win?
Try 20 and -20.

Using Bob's strategy you mean? If Alice chooses 20 and -20, Bob's chance of winning, while quite large, isn't quite 100%, it's like 99.999999%. A similar variation is what happens when Alice chooses two very large numbers. Bob's chance of winning, while greater than 50%, is incredibly close to 50%.

Eric has a very similar strategy, the only difference being he uses a different generalized error function(??) p(x) = 1/(1+e^(42-x))) which assumes the mean to be 42 instead of 0. Now Eric is not great at maths but reasons that Alice's system is slightly more likely to have a bias in favor of positive numbers over negative and Eric also happens to like the number 42.

Does Eric have a valid strategy?

What did Bob do to derive his function?

While Eric's reasoning isn't very good, the strategy still holds. The given function (the logistic function, by the way; it looks sorta similar to the error function, but the resemblance is only skin deep, so to speak) is not unique. In fact, there are only a few properties of importance:

1. The function must stay between 0 and 1 for all x.
2. The function must always increase.

The first condition is required so that Bob actually uses probabilities to say "higher" or "lower" (i.e. he can't have a chance of -1 to say "higher", or of 2 to say "lower"). The second condition is the one that ensures our guesses are good. In particular, say we have some function f satisfying the above two. Then, we know that 0 <= f(x) <= 1 for any real number x. We also know for any two real numbers x and y with x smaller than y, f(x) < f(y), since the function always increases.

Now, let's say Alice has chosen two numbers, A and B, where we arrange the labels in such a way that A is the smaller of the two numbers. Bob has a 50% chance of seeing A, in which case he calculates f(A) and guesses "lower" with probability f(A); he must guess "higher" to win in this case, so he wins with probability 1-f(A). If sees B, he instead calculates f(B) and guesses (correctly, this time) "lower" with probability f(B). Overall, his odds of winning this round are

0.5 * (1-f(A)) + 0.5 * f(B) = 0.5 * (1 - f(A) + f(B))

Since f(A) < f(B), f(B) - f(A) > 0, so Bob's probability of winning is higher than 50%. You could even use a function which "starts" at, say, 0.6 at -infinity and goes up to 0.8 at +infinity, and the above holds. It's weird, but you could sandwich Bob's guesses arbitrarily: make him always guess "lower" with probability between 0.9999998 and 0.9999999. So long as the function always increases, he's still got a winning strategy.

Since Eric's function satisfies the above two properties, it works just as well as Bob's.