Suppose you are playing a game with Alice. She uses some probability distribution to pick two distinct real numbers and writes them in two envelopes. You then choose either of the envelope and opens the number inside the envelope. Is there a strategy that guarantees you a strictly larger than 50% probability to guess correctly whether the chosen real number is the greater or the lesser, for any probability distribution that Alice uses?

This is my take on the problem; feel free to comment, discuss, or argue with me! As long as the discussion is kept civil.

The answer is yes.

Here we will construct a constructive algorithm and prove that it satisfies the requirements.

First, construct a strictly increasing function . Also, generate a random number between , after Alice has set up her numbers. Suppose you uncover the number , then guess “greater” when and “lesser” otherwise.

In less formal terms, this means the higher the real number, the greater the probability that you choose it to be “greater”.

Proof: Suppose that the numbers Alice has are , and without loss of generality assume that . Then the probability that you guess correctly is .

The probability of choosing either or is . The probability of guessing “lesser” given is . The probability of guessing “greater” given is . So the overall probability is . Since and is strictly increasing, it follows that , and hence the probability is greater than .

The following objections are the most commonly found after reading:

Why can’t we use a strategy such as “pick greater if the number is more than zero, otherwise lesser”?
The problem is that your strategy must work for all probability distribution that Alice uses. Suppose that she uses a probability distribution that only takes positive values (just for concreteness, and appear with equal probability , and the rest will never be chosen). Your strategy only works half of the time, if you’re lucky to get the greater number.

Why can’t we just pick a random real number?
Why can’t we? We picked a random real number there! The only problem is that it’s difficult to pick a random real number. It’s much easier to pick a real number in . In fact, I will elaborate:

Suppose that we have computed and we want to pick . Express in binary, and begin with a string of characters . Flip a coin; if it turns out heads, then write to the right of all digits we have written, otherwise . This generates a real number in expressed in binary. At the moment that our number cannot match (a match can only occur in the following situations: if we have written digits, either all the digits match, or is a dyadic fraction and our number plus will be equal to (aka our number will be continued by a string of s)), stop the process and compare them. Since there is a probability of ending up with , and in fact the expected value of coin flips we need is , this will almost always return a result in finite time.

The above gives a constructive algorithm on generating the number. In the case you want to pick a random real number with the above algorithm, you must extend the coin flips in both ways. There is a probability of of ending with not s to the left of your number, and such numbers are not real numbers (or I can’t see a good way to transform it to real numbers), so you will have a problem to generate truly random real numbers.

Alright, that’s all from me. I mostly want to put the above algorithm to generate a random real number between and comparing it with another real number.