[cortesoft]

Does this hold true if Player 1 is adversarial?

If I was the Player 1 in this case, and was trying to prevent Player 2 from guessing with a greater than 50% probability, I would use this method:

Pick a random 100 digit number N (using a random number generator to pick 100 digits in order).

Flip a coin. Heads, the second number is N - 1. Tails, it is N + 1.

I would imagine you could slightly beat 50%, but the percentage would approach 50% as you added more digits to your initial number. It would probably be close to unmeasurable at 100 digits (i.e. you couldn't tell if you were doing better than 50% or not).

[nimih]

The result holds even if Player 1 knows Player 2's strategy and attempts to foil it, although as you correctly observe, the paper only claims >50%, and Player 1 can minimize that margin by picking the two numbers to be right next to each other (and trying to choose them such that they occur in a low-density area of Player 2's distribution f(t) ).

[cortesoft]

Yeah, as I was working it out in my head, I was realizing that it would approach 50% but never hit it, since no matter the distribution you choose, the higher number will always be greater on average than the smaller (by definition). You can approach an equal average as you choose a larger and larger range, but never hit it.... which I guess is what the paper is proving.

Practically, though, you could get close enough to 50% that it would be immeasurable by sampling.