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.

Math Art

This picture represents a good deal of what I accomplished my senior year of college. I didn't make this picture; that credit belongs to my former Professor, Jacob Siehler, who is quite amazing at using computers to represent mathematical data.

Basically this picture represents a result of my senior thesis. Here's more or less what I did:

Take a positive integer m. Make a table with m columns and infinitely many rows. Label the columns 0, 1, ... , up through m - 1. Now place a ball in the 0 column of some row, say row x. Then define a sequence of rotation remainders as follows:

• When the ball is in row x, you move it x spaces to the right, and if there aren't that many spaces left in the row, just wrap around to the next row (just like reading a page left to right, top to bottom)
• After each move, write down the column position the ball is in

This sequence of column positions is called the sequence of rotation remainders, which is a term I made up, and it's what I titled my thesis. Surely I could have picked a more exciting and/or cute name for it, but what can you do...

So you might ask how the above picture represents this sequence at all. In fact, each row of pixels in the picture represents an integer (1, 2, 3, 4, 5, ...) and the pixels in a given row represent the numbers in the rotation remainder sequence corresponding to x. In this picture, m = 63.

Isn't it pretty? I promise there's a lot more complicated stuff behind it, too. I'm sure you'd be very impressed.

Do math like a jellyfish

It occurred to me this afternoon as I sat down to blog that my blog can basically be distilled down to a few recurring themes:

1. Pro-life issues
2. Miscellaneous political issues
3. Science and religion
4. Nerdy math stuff

Aside from the random things I find on the Internet and just post to say, "That's cool!" I think this really sums up my blog. I didn't necessarily mean for this to happen (my blog is still what my title says it is) but I guess these are things I think about a lot.

Anyway this afternoon I was thinking about topic 4. Nerdy math stuff and I decided my blog could use a little diversion from the more serious (read: relevant) topics normally discussed.

So I started reading this book called Is God a Mathematician? which is about the question, "Does math describe something that actually exists, or is it all just made up in our minds?" In other words, do circles and lines and numbers actually exist in some Platonic universe, or are they just a convenient fiction?

Personally, my intuition says that yes, there is some Platonic universe in which all these concepts actually exist. I guess. I mean, there's nothing to force an intelligent creature to come up with the concepts of "1, 2, 3, 4, ..." and so on, but if they did, whatever theorems about those concepts they came up with, they would match up with ours. There's an actual logical structure to the universe that exists, whether we try to imagine our way around it or not.

But there was one motivating example that I found striking. It comes in the book as a quote from Sir Michael Atiyah, whom I had not heard of before. Here's his idea:

"[L]et us imagine that intelligence had resided, not in mankind, but in some vast solitary and isolated jelly-fish, buried deep in the depths of the Pacific Ocean. It would have no experience of individual objects, only with the surrounding water. Motion, temperature and pressure would provide its basic sensory data. In such a pure continuum the discrete would not arise and there would be nothing to count."

As a math grad student who is interested in analysis (for all of you non-math majors out there, think Calculus... on steroids) I am very much interested in the study of continuous things. So it strikes me as a good thought experiment to try to develop some sort of mathematics starting with the continuum, rather than with discrete objects.

This is hard. We human beings, perhaps thanks to God's blessing, started doing math by counting things. So all of our theorems from back in the day (before we invented weird things like Calculus) have to do with finite numbers, like 1, 2, 3, 4, and so on. What Atiyah is saying is, okay, now imagine there's nothing to count. You can't count one cow, two cows, three cows because there are no cows. It's really hard for us to imagine, because we're trained from the time we're little to count things.

So when we did finally start to study continuous things, we were able through a series of brilliant strokes to describe continuous things in terms of discrete things. (Or if you are currently unable to do this, that is why you never got Calculus. Sorry.) That is, if you want to understand a nice curve, just chop it up into little tiny pieces and "take the limit" as the number of pieces you chop goes to infinity. It's a brilliant strategy for moving out from the finite numbers you can count to the continuum.

I wonder if it's possible to work the other way around, or simply to bypass discrete math altogether, by starting with the continuum. What if we could do math like a jellyfish? What kind of mathematics would we come up with if all we had to experience was a set of continuous phenomena? Personally I can't quite imagine it at this point, but I'm going to try and think about it to see what I come up with.

This is what we mathematicians think about as we're walking home from lunch...

Yeah...