There is a related puzzle which I've also heard called the Two Envelopes Problem. The premise is that you are handed two envelopes. Inside each envelope is a piece of paper with a number written on it. I have written down these numbers by sampling from some probability distribution, but you don't know what it is. All you know is that the two numbers are different. You get to pick one envelope and then look at the paper inside. You then need to guess whether or not the number in the other envelope is larger or smaller than the one you are looking at. Can you guess with better than 50% chance?
Is there actually some way to guess with better than 50% chance?
I'm pretty sure this could be reduced to the secretary problem where there's a pool of 2 candidates, which yields an optimal hire with probability 50%.
Maybe you play word games and say, "I guess the other number is not higher," or "I guess the other number is not lower." Since the number you observed was produced once, there is some non-zero probability that it was produced twice, in which case the other number is neither nigher nor lower.
The reduction is leaky in that it requires you to assume that there is nothing to learn from looking at the first number.
Here's a hint that is not a full solution. If you knew that the numbers in both envelopes were independently sampled from the same Gaussian (but not necessarily which Gaussian), then there is a simple strategy that wins more than 50% of the time: pick an envelope to peek at uniformly at random and guess that it is the larger one if and only if it shows a positive number.
Why does this work? If both numbers are positive, your strategy is equivalent to "pick a random envelope" and you're left with a uniformly random choice of envelope. If both numbers are negative, you're also left with a uniformly random choice of envelope. But if one is positive and the other is negative, you win 100% of the time.
What are the odds of the third case? Well every Gaussian has at least some mass on positive numbers and some mass on negative numbers. So there is some nonzero chance, even if you don't know what it is. So while the strategy might not always do better than a coin toss, some positive percent of the time you win every time. And so you get a distinct advantage over random guessing.
The problem is now how would one transfer such an approach to the original problem without the Gaussian assumption. Somehow the two problems are less different than they initially seem.
I didn't even think of the possibility of negative numbers. I can't ever imagine playing this x, 2x envelope game if there was any chance at all that the numbers would be negative. Like you open an envelope and it says I owe them either one million or two million dollars. Yeah, screw that game.
But couldn't you make the same argument for guessing that it's higher iff the number is greater than 42? Therefore, if the number is 9, both strategies tell you to do different things, yet in each case, your probability of winning is >½. There must be a hole in the logic somewhere…
> But couldn't you make the same argument for guessing that it's higher iff the number is greater than 42?
Yep.
> Therefore, if the number is 9, both strategies tell you to do different things, yet in each case, your probability of winning is >½. There must be a hole in the logic somewhere…
For any nonnegative value C, the probability of Gaussian draw x being larger than (iid) Gaussian draw y is strictly bigger than 1/2 when conditioned solely on x > C.
The particular choice of C might change which specific draws of x and y the strategy succeeds with, but as you noticed for every C a thresholding strategy of the above form does give you some pointwise nonzero advantage over random guessing.
A very general solution, which works regardless of how the numbers in the envelope are picked:
Choose a monotonically increasing function f with values between 0 and 1. Choose one of the envelopes at random. Then look at the number x in the envelope. Then, with probability f(x) say that you have the larger envelope.
I'm inclined to agree with you here. The solutions suggested here seem to depend on heuristics that depend on the type of distribution.
A tangential question: real numbers are uncountably infinite. Are probability distributions over the real numbers likewise uncountably infinite, or do they form a higher infinity?
First, a point of terminology: uncountably infinite refers to any infinite cardinality other than countably infinite, so if the number of probability distributions is at least the cardinality of the real numbers, then it's already uncountable.
As for what uncountable cardinality they form, it's the same as the real numbers [0]. Roughly, a probability distribution is determined by the countable collection of real numbers P(X <= q) with q rational. That means the cardinality is no more than R^Q, which is isomorphic to R. (the cardinality is at least R due to, say, uniform distributions on [0, x] for x real).
If we take any finite interval [0,a], there's a unique uninformed prior of the uniform distribution, and we get a (a-b)/a probability of gaining by switching under that distribution. If we drag a to infinity, we get with probability 1 that switching is better. Numbers are big yo
So, my ONLY guess as to how there can be a strategy is that, if the number you see is positive, you keep it, and if the number you see is negative, you switch. My reasoning is this:
1. If the number you pick is positive, then there are technically (although arbitrarily small) more negative numbers that can be chosen for the other envelope. So you have a slightly larger than 50% chance of winning.
2. The inverse is true if you chose negative, however.
That said - I think this would generally imply you should always switch, which is why I'm not convinced I'm right. Consider a purely positive set, for example. If my number shows up as "12" - then I know there are infinitely more numbers larger than it, but only 11 numbers lower than it. But this starts to feel like the original two envelopes paradox.
--
tldr; I'm not sure of the answer, although I think if I saw the answer I would have an "Aha!" moment.
