A small twist on the classic probability puzzle:
You are given two boxes with a number inside each box, each of which ranges from [A, B]. 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?
While the regular variant has no restriction on the range of the random number, in this case you are given that it will fall within the range from [A, B].
If this is the case, then it is possible to have a uniform distribution.
Lets take 2 cases:
-
You are given the PDF from which the numbers were generated on the range [A, B].
-
You are not given any information about the distribution from which the numbers were generated.
In the first case, the solution is simple: since we are given the distribution, we can just compute the probability that the other box (z) has a number larger than the one we sampled (y)$P(z>y,z ≈ \text{Dist})$ where $≈$ stands for distributed.
In the second case however, we are not given the distribution. Is the best solution then to choose your own PDF and generate a random real from [A, B] as is the accepted solution for the puzzle when there is no range restriction?
Or can you use the information that the range of values is restricted to get to an even better solution?
Best Answer
The original problem: Two numbers $X,Y$ are chosen according to some distribution on $\mathbb{R}$ and put into envelopes. You are allowed to open one envelope and see $X$, and then decide whether to keep $X$ or discard it and take $Y$, hidden in the other envelope. Your goal is to choose the larger number.
A strategy that gives you probability $\frac{1}{2} + \varepsilon$ of choosing the larger number is to come up with your own distribution whose support is all of $\mathbb{R}$ and sample it to get $Z$. If $Z > X$, discard $X$; otherwise, keep $X$. If $Z$ is less than both $X$ and $Y$, or if $Z$ is greater than both $X$ and $Y$, you will choose the correct number with probability $\frac{1}{2}$. If $X < Z < Y$ or $Y < Z < X$, you will always choose the correct number. The probability of $Z$ being between $X$ and $Y$ is $\varepsilon > 0$, so you will win this game with probability $\frac{1}{2} + \varepsilon$.
The strategy above relies on the fact that no matter how $X,Y$ are distributed, the probability that $Z$ lies between them is greater than $0$. If we are restricted to $[A,B]$, then choosing $Z$ uniformly on $[A,B]$ ensures this unless $X,Y$ are always equal to some fixed constant (in which case the problem is degenerate anyway — it is implied that $P(X = Y) = 0$). The original strategy translates to the new situation without any problems.
Note that we don't actually do very well in either the original situation or the revised one: an adversary can just choose $X,Y$ distributed uniformly on $[\alpha,\alpha+\delta]$ for some $\alpha$ and a tiny $\delta$ and force our advantage $\varepsilon$ to be as small as he wants.