Only A Little

Time for the solution to the Two Numbers problem. I suppose I could just state the solution right away, but I like to do something of a derivation first.

First of all, consider the results of the following strategy for Bob:
If the number you see is greater than zero, guess it is larger, if the number is less than zero, guess it is smaller

Easy enough to implement, if both numbers that Alice wrote down are positive, then you are still 50/50. If they are both negative then you are again 50/50, but if one number was positive and one was negative, then you are guaranteed to win.

Alright, thats all well and good, naturally if Alice knows you are doing this, then she won't ever write down a positive and negative number together of course, so this is not actually guaranteed to give you a better than 50% chance of winning the game. Now, instead of greater than/less than zero, why not use a random number K. Perform the following strategy:
Select a nonzero probability distribution over the reals f(z). After Alice writes down the numbers, select a number K using f(z). If the number you see is greater than K guess it is the larger one, if the number you see is smaller than K then guess it is the smaller one.

By nonzero probability distribution I mean that f(z)>0 always and ∫f(z)dz = 1 when integrated over all the reals. Basically, the strategy is to assume that the unseen number is near K.

Suppose Alice writes down x and y with y>x, then if x>K or K>y you are simply 50/50, but if y>K>x you win the game 100%. The chance of you winning is therefore
∫f(z)dz+(1-∫f(z)dz)1/2
=1/2+1/2∫f(z)dz

Where the integral is between x and y (giving the chance K lands between x and y). Since f(z)>0 always, this is greater than 1/2 in all cases and is a valid solution. Naturally, if Alice knows f(z), she can make that integral as small as she likes, but she cannot make it non positive.

One can make a slightly more general (but not actually any better) solution as well. Consider that Bob looks at the number before choosing K. Then the chance that K will be less than x (and thus guess x is larger) is ∫f(z)dz integrated from -∞ to x. Let p(x) be that number (the probability that we say x is larger). Clearly we have p(x) positive, increasing, and 0 at -∞ and 1 at +∞.

Let Alice choose number x and y with y>x. Now the chance Bob wins given some function p(x) is 1/2 (the chance he is given y) times p(y) (the chance he says y is larger) plus 1/2 (the chance he is given x) times 1-p(x) (the chance he says x is smaller). thus giving
1/2 p(y)+1/2(1-p(x))
=1/2+1/2(p(y)-p(x))

Not surprising given that p is the integral of f from before.

Anyway, the only thing that we need to demand of p(x) is that is be strictly increasing and bounded between 0 and 1. It does not matter that it goes to 0 at -∞ or 1 at +∞ (though, I guess it might as well). So the strategy of saying the number you see, x, is greater with probability p(x) is more general than the strategy of picking K from f(x) (though not any better, even if it is more general). Again, given p(x) Alice has the power to make p(y)-p(x) as small as she wants, but she can never stop it from being positive.

No comments: