7 ms·

This reminds me of a fascinating problem (not sure if there's a name for it): You play the following game (say for many rounds). Someone puts different values

This reminds me of a fascinating problem (not sure if there's a name for it): You play the following game (say for many rounds). Someone puts different values in two envelopes (they can pick the values arbitrarily, even maliciously, each round). You want to pick the higher valued envelope. You pick an envelope, they show you the value of the other. You can hold your value or you can switch. It also works if the game is they show you your own value and you can choose to hold or switch. Actually, now that I think about it, you can even make the game such that you pick an envelope and tell them which envelope to show you, then you can hold or switch. More interesting :) The questions is: is there a strategy where you get the higher value strictly more than 50% of the time? The surprising answer is, yes, there is such a strategy. It's really neat, and I've tried to find other places to apply the reasoning, but have not found another interesting place. And yes, this problem and strategy are mathematically correct, not cheating, not "out of the box" stuff. Good luck :)

metacritic12 4y ago
Generate a random number T from the arctan distribution. If the number in the other envelope is greater than T, switch. For envelopes with two different numbers n, m, the above is guaranteed to give you the higher one strictly more than 50% of the time.
- zeroonetwothree 4y ago
  To expand on this, you can use any distribution that has nonzero density over every interval.
- ChrisLomont 4y ago
  Yep - any distribution that is nonzero over the set of choices works, so over the reals, anything that is everywhere nonzero works. For example, exp^{-x^2} with normalization factor is a simple choice.
  - emerongi 4y ago
    Is there a complete explanation for this somewhere? Asking for a friend, I obviously fully comprehend what you're talking about here.
    - ChrisLomont 4y ago
      Yeah, the solution is somewhat tricky. Here is the idea (this is somewhat sloppy, but gives the idea - if you're mathematically advanced all this can be made precise): Suppose you have a way to pick a random number yourself, that has nonzero chance to pick any number. Suppose the person putting things in envelopes picks X < Y as their numbers. You too pick a random number, say T. Open an envelope. If that envelope is less than T, then switch. You will get the larger number more than half the time. Here is why it works. You pick X or Y envelope with 50/50 odds. 3 cases: 1) Suppose you picked a T < X. If you opened X, then T < X, you don't switch, so you lose. If you opened Y, T < Y, you don't switch, you win. So if T < X you win half the time. 2) Suppose you picked a T with Y < T. Then no matter what you pick, T is not < your envelope, you will not switch, and again you win half the time. Nothing gained so far. But, if you happened to pick X < T < Y, which happens with some nonzero chance, then analyze: if you open X, X < T, switch, you win. If you open Y, T < Y, you don't switch, you win. This case gives you more than 50/50 odds. The technical details is it's minorly tricky to pick a real number out of an infinite set at random, with any number being a possible outcome. But the probability distributions above do the trick - basically any function you can draw that is everywhere positive, with the tails squeezing to zero fast enough (but never reaching it) will work.
jstanley 4y ago
FWIW, I think all 3 versions of your game are completely equivalent. In all 3 versions you first get to decide which envelope you look inside, and then you get to decide which envelope you open.
- ChrisLomont 4y ago
  Yes, I agree they are equivalent, which is why I was able to see the same solution allows all three games. The last one gives the puzzle solver more things to fiddle with, even though it does not matter, perhaps making the puzzle more difficult or interesting.

metacritic12 4y ago

Generate a random number T from the arctan distribution. If the number in the other envelope is greater than T, switch. For envelopes with two different numbers n, m, the above is guaranteed to give you the higher one strictly more than 50% of the time.

zeroonetwothree 4y ago
To expand on this, you can use any distribution that has nonzero density over every interval.
ChrisLomont 4y ago
Yep - any distribution that is nonzero over the set of choices works, so over the reals, anything that is everywhere nonzero works. For example, exp^{-x^2} with normalization factor is a simple choice.
- emerongi 4y ago
  Is there a complete explanation for this somewhere? Asking for a friend, I obviously fully comprehend what you're talking about here.
  - ChrisLomont 4y ago
    Yeah, the solution is somewhat tricky. Here is the idea (this is somewhat sloppy, but gives the idea - if you're mathematically advanced all this can be made precise): Suppose you have a way to pick a random number yourself, that has nonzero chance to pick any number. Suppose the person putting things in envelopes picks X < Y as their numbers. You too pick a random number, say T. Open an envelope. If that envelope is less than T, then switch. You will get the larger number more than half the time. Here is why it works. You pick X or Y envelope with 50/50 odds. 3 cases: 1) Suppose you picked a T < X. If you opened X, then T < X, you don't switch, so you lose. If you opened Y, T < Y, you don't switch, you win. So if T < X you win half the time. 2) Suppose you picked a T with Y < T. Then no matter what you pick, T is not < your envelope, you will not switch, and again you win half the time. Nothing gained so far. But, if you happened to pick X < T < Y, which happens with some nonzero chance, then analyze: if you open X, X < T, switch, you win. If you open Y, T < Y, you don't switch, you win. This case gives you more than 50/50 odds. The technical details is it's minorly tricky to pick a real number out of an infinite set at random, with any number being a possible outcome. But the probability distributions above do the trick - basically any function you can draw that is everywhere positive, with the tails squeezing to zero fast enough (but never reaching it) will work.

jstanley 4y ago

FWIW, I think all 3 versions of your game are completely equivalent. In all 3 versions you first get to decide which envelope you look inside, and then you get to decide which envelope you open.

ChrisLomont 4y ago
Yes, I agree they are equivalent, which is why I was able to see the same solution allows all three games. The last one gives the puzzle solver more things to fiddle with, even though it does not matter, perhaps making the puzzle more difficult or interesting.