Response to XKCD blog (WARNING: this is super nerdy)

The following is a response to a post on the XKCD blog.

The puzzle described is as follows:

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?

XKCD claims there is such a strategy, and you can read it here. Basically what I'm explaining below is why this strategy doesn't really work, although it's tempting to say it does. To summarize: this strategy allows a dumb computer to keep getting the right answer more than 50% of the time if I don't change Alice's two numbers. But this doesn't really describe reality, in which I have to view the numbers Alice has given me as random variables.

Okay, here's my response.

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.