Wednesday, April 21, 2010

On the unspeakable coolness of numbers

This is an interesting little question, stolen shamelessly from xkcd, as many interesting things often are.

I choose two real numbers, A and B, using some process which I do not share with you. I tell you one of the numbers, chosen by means of a fair coin toss. Your task is to guess whether the other number is higher or lower than the one I have shared with you.

The question, of course is whether or not there is a strategy that is going to give you a better chance of being correct than borrowing my coin and flipping it. Is there?

Highlight for hint:

Since the set of reals is uncountably infinite, it follows that a finite process cannot choose a real number with equal probability (since you can't biject between a finite domain and an infinite codomain). This is a rather long way of saying that both A and B are likely to be closer to one, than, say Graham's Number.

Highlight for answer:

Given that the number you have been given is x, calculate p(x)=1/(1+e^-x). Now pick a random number from U(0,1). If this number is lower than p(x), guess that the unseen number is lower than the number you are given, and vice versa.

Highlight for explanation:

Consider p(x). It tends to zero on the left and 1 on the right and is monotonic in between. Sound familiar? It is, of course, a cumulative distribution function. Consider two distinct real numbers m,n with m<n, so that p(m)<p(n). Now we were shown one of m or n at random: what is the probability that we selected the lower one? This is just P(lower)=0.5*(1-p(m))+0.5*p(n), since we pick each with 50% probability. Working through, this gives P(lower)=0.5+0.5(p(n)-p(m)). And since p(m)<p(n), we have P(lower)>0.5. Pretty cool, huh?

No comments:

Post a Comment