# Better than random

You are given two boxes with a number inside each box. The two numbers are different but you have no idea what they are. You pick one box to open; read the number inside; and then guess if the number in the other box is larger or smaller. You win if you guess correctly, and lose otherwise. Is there anyway that you can win the game with more than 50% chances no matter what the two numbers are?

-
Two-envelope paradox? –  The Chaz 2.0 Aug 13 '11 at 13:16
This is usually called The two envelopes problem and explained at length here: en.wikipedia.org/wiki/Two_envelopes_problem –  Did Aug 13 '11 at 13:17
@Didier: No, in the two-envelope problem, you have to decide whether to switch before seeing the number inside. If you get to see the number first, there is actually a strategy to get more than 50%. –  joriki Aug 13 '11 at 13:22
Actually no, this isn't the two envelopes problem, you actually can come up with a solution that gives (slightly) better than 50% chance of winning. Let me try to remember the solution and I will post it. –  FelixCQ Aug 13 '11 at 13:22
So the old answers will be trotted out once again. –  André Nicolas Aug 13 '11 at 13:25

## migrated from stackoverflow.comAug 13 '11 at 13:08

This question came from our site for professional and enthusiast programmers.

As it has been pointed out, the wikipedia page contains more than enough information. Here my answer anyway:

Let $X$ be a r.v. with a distribution of your choice. The only important thing is that it gives positive weight to each (measurable) subset of the reals. For example, let $X$ be a standard normal variable.

Let the two numbers be $a$ and $b$, with $a < b$. Compare a realisation of $X$ (independent of your choice of $a$ or $b$) with the value of the first number you see. If $X$ is bigger, switch, otherwise keep the number.

The probability of winning can be computed as follows:

• If you choose $a$ (with 1/2 chance), then you win if you switch, ie if $X > a$. This has prob. $P(X>a)$.
• Similarly if you choose $b$ (with 1/2 chance), you win if you don't switch, ie if $X \leq b$. This has prob. $P(X\leq b)$.
• So the overall probability of winning is $\frac{1}{2} + P(a < X \leq b)$, which is slightly larger than 1/2 based on our assumptions on $X$.
-

There's a detailed discussion about this on MO: http://mathoverflow.net/questions/9037. There's also a question on math.SE on the Card doubling paradox, but this is about expectation values for doubled amounts, not about the probability of guessing correctly. And as Didier pointed out in a comment, there's a section in the Wikipedia article on the two envelopes problem that deals with this as an extension of that.

-

Note: I have never heard this before, I'm only reasoning through it, so don't take my answer as the answer.

This problem is defined by its ambiguity. Can ANY number be in either box, from negative infinity to infinity, with equal distribution? It doesn't say anything about it. From 0 to infinity? Only integers?

If it's negative infinity to positive infinity (integers or not) you can do better than 50% only in a trivial sense; If you see -5.6 billion in the first one there are infinite numbers in either direction, so you have a 50% chance either way. So, no, you can't do better than 50% given the equal-distribution-negative-infinity-to-positive-infinity-assumption.

If there is a known discrete range, than it's obviously easy to get better than 50%. But with any infinite range, you can't do better than 50%.

Note: I am really guessing here that this problem was formed with this thought: If the range is 0 to infinity, then whatever finite number I get in the first box has a finite number of numbers smaller than it, and infinite larger; therefore, I should always pick larger and I am correct some number approaching (but not exactly equal to) 100%. This is an absurd conclusion since it implies that no matter which box I pick first, it will always have the smallest number, when the fact is this will only happen 50% of the time.

Not being a mathematician, my guess is that the unstated assumption that leads to this contradiction is what the comment below points out: The entire idea of a uniform distribution over an infinite set is impossible.

So what does this say about the question? Well, just that it doesn't really make sense with an infinite range, and is horribly simple with a finite range.

-
There's no such thing as a uniform distribution on an infinite interval. Assume the probability to find the number in an interval of length $1$ is $p$. By additivity, the probability to find the number in an interval of length $l$ is $lp$. Since you can choose $l$ arbitrarily large and the probability has to remain below $1$, it follows that $p=0$, but that implies that $p=0$ over any interval. –  joriki Aug 13 '11 at 13:20
Thank you, Theo. I'm really curious if my reasoning is wrong. –  Jeremy Aug 13 '11 at 13:36
@Jeremy: There's no assumption in the question that the numbers are integers, so there are not finitely many numbers even if you restrict to an interval of finite length. –  joriki Aug 13 '11 at 13:39
@joriki That's true. My last sentence really should be "horribly simple with a finite number of values." –  Jeremy Aug 13 '11 at 13:41
I was referring also to the sentence "If the range is 0 to infinity, then whatever finite number I get in the first box has a finite number of numbers smaller than it". –  joriki Aug 13 '11 at 13:45
Obviously, if the random number is greater than or less than both of the numbers the chances are still 50% but if the random numer is between the numbers then the player can select the appropriate box. This gives a probability of $P= .5+$ probability that the lower number < random number < higher number, which is greater than .5.