Two real numbers

Initially found from xkcd’s blog, then got a link to MathOverflow.

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 f : \mathbb{R} \to (0, 1). Also, generate a random number r between [0,1], after Alice has set up her numbers. Suppose you uncover the number a, then guess “greater” when r < f(a) 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 a,b, and without loss of generality assume that a < b. Then the probability that you guess correctly is (\text{probability of choosing } a)(\text{probability of guessing "lesser" given } a) + (\text{probability of choosing } b)(\text{probability of guessing "greater" given } b).

The probability of choosing either a or b is \frac{1}{2}. The probability of guessing “lesser” given a is 1-f(a). The probability of guessing “greater” given b is f(b). So the overall probability is \frac{1}{2} (1-f(a)) + \frac{1}{2} f(b) = \frac{1}{2} + \frac{1}{2}(f(b)-f(a)). Since b > a and f is strictly increasing, it follows that f(b) > f(a), and hence the probability is greater than \frac{1}{2}.

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, 1 and 2 appear with equal probability \frac{1}{2}, 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 [0,1]. In fact, I will elaborate:

Suppose that we have computed f(a) and we want to pick r. Express f(a) in binary, and begin with a string of characters (0.). Flip a coin; if it turns out heads, then write 0 to the right of all digits we have written, otherwise 1. This generates a real number in [0,1] expressed in binary. At the moment that our number cannot match f(a) (a match can only occur in the following situations: if we have written n digits, either all the digits match, or [0,1] is a dyadic fraction and our number plus 2^{-n} will be equal to f(a) (aka our number will be continued by a string of 1s)), stop the process and compare them. Since there is a probability 0 of ending up with f(a), and in fact the expected value of coin flips we need is 2, 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 1 of ending with not 0s 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 [0,1] and comparing it with another real number.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s