4 ms·

This problem frustrates me, I'm not quite convinced that it's well defined as written. My first instinct is to say "Based on your knowledge of Alice, assign a

This problem frustrates me, I'm not quite convinced that it's well defined as written. My first instinct is to say "Based on your knowledge of Alice, assign a probability distribution over the pairs of integers she might pick. Then when one is revealed you should condition on that fact. Then just pick whichever of higher or lower is most likely." The problem setter will object that we have no way of assigning a probability distribution to Alice's actions. But if that's true, what does it mean to "do better than break even"? Apparently it doesn't mean "win with probability >50%", because there is no probability of winning.

tomp 9y ago
I agree that it’s not entirely strictly specified - in particular, there’s no random (uniform) distribution over integers. I guess you could get around this by specifying in in a way you did, or “parametrized” over some parameter, or say “for any distribution” (and mandate a single turn of the game)... Anyways, this is also highly unintuitive for me, so I’m far from certain that the solution below is correct; having said that, I’m unable to find a flaw in it. If you can, I’d be interested in hearing it. SPOILER / SOLUTION: Pick a number - say 0 for the sake of it. After Alice reveals the first number, assume that the other number is on the opposite side of 0 (i.e. if Alice reveals a negative number, assume the other number is positive and say “higher”, and vice versa). If your number is within the interval of Alice’s numbers, you win; otherwise, you still have a 50% chance of winning.
- OscarCunningham 9y ago
  I think the "orthodox" answer is that your method wouldn't work, because if Alice picks 10 and 20 and opens 10 first then you have a 0% chance of winning. Instead (they say) you should pick your number at random, so that it has at least some probability of being any given integer. For example you could pick the number n with probability 2^|n|/3. That way no matter which two numbers Alice picks there's always some probability your number will be between them. Now personally I think this is silly. You know nothing about what Alice is going to do, so your own choice of number can't possibly matter. You might as well always pick zero rather than randomizing. The reason the orthodoxy disagree is because the problem they're answering is something like "Find a strategy such that if you knew which numbers Alice had picked, but hadn't yet chosen your own random numbers, then you would always anticipate a >50% chance of winning." This resembles the definition of a 95% confidence interval: "A procedure for generating intervals from data, such that if you knew the true value of the parameter, but not the data, you would assign a 95% probability that the true value lies in the interval". Of course Bayesians turn it around and define a credence interval where you know the data but not the true value (which I think is better, because this actually is your state of knowledge).
  - tomp 9y ago
    > if Alice picks 10 and 20 and opens 10 first then you have a 0% chance of winning. No because you pick the hand (i.e. it’s essentually random), so you still have 50% chance of first revealing 20 and gettingit right.
    - OscarCunningham 9y ago
      Good point. So our methods are similar, but yours puts the randomness in the choice of hand rather than the choice of integer. But in the (10,20) case your method gets exactly 50% and not more than 50%.
      - deleted 9y ago
        [deleted]
      - sirclueless 8y ago
        This is why your choice of threshold matters. Your strategy should be to choose a threshold randomly from any distribution that is non-zero everywhere (such as a normal distribution), then choose a hand uniformly at random. Choosing zero as a threshold deterministically does not work for all choices that Alice can make because, as you say, for some choices such as (10,20) it gives you exactly 50% chance to win. But as long as there is always a non-zero chance that you chose a threshold between Alice's numbers, then there is a > 50% chance that you win the game.
  - Avshalom 9y ago
    It's important to remember that Alice is a perfect random number generator. She certainly isn't going limit her numbers to what can be comfortably written on the paper for instance. Which is fun because while there are hundreds of puzzles that require people to be able memorize perfect hash functions on the fly or remember the state of a FSM 1000 states ago or be capable of implementing the necessary function required by the axiom of choice for a given situation... this is the first puzzle I can think of that requires some one to be able to, with perfect randomness select two integers (-∞,∞)
- danbruc 9y ago
  Does not work according to [1], see followup puzzle 2 and its solution. At least if my interpretation of your proposed solution is correct, i.e. that you fix your threshold number in advance. Not sure if a delayed random choice would help. [1] https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-googol/ https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-...
  - tomp 9y ago
    Hmmm... If Ininterpret their proof (i.e. “Puzzle 2”) correctly, they prove that there’s no deterministic solution that yields probability > 50% for any two numbers... the idea of the solution I posted (which is deterministic) is that you have >= 50% for all numbers, and > 50% for some numbers.

tomp 9y ago

I agree that it’s not entirely strictly specified - in particular, there’s no random (uniform) distribution over integers. I guess you could get around this by specifying in in a way you did, or “parametrized” over some parameter, or say “for any distribution” (and mandate a single turn of the game)... Anyways, this is also highly unintuitive for me, so I’m far from certain that the solution below is correct; having said that, I’m unable to find a flaw in it. If you can, I’d be interested in hearing it. SPOILER / SOLUTION: Pick a number - say 0 for the sake of it. After Alice reveals the first number, assume that the other number is on the opposite side of 0 (i.e. if Alice reveals a negative number, assume the other number is positive and say “higher”, and vice versa). If your number is within the interval of Alice’s numbers, you win; otherwise, you still have a 50% chance of winning.

OscarCunningham 9y ago
I think the "orthodox" answer is that your method wouldn't work, because if Alice picks 10 and 20 and opens 10 first then you have a 0% chance of winning. Instead (they say) you should pick your number at random, so that it has at least some probability of being any given integer. For example you could pick the number n with probability 2^|n|/3. That way no matter which two numbers Alice picks there's always some probability your number will be between them. Now personally I think this is silly. You know nothing about what Alice is going to do, so your own choice of number can't possibly matter. You might as well always pick zero rather than randomizing. The reason the orthodoxy disagree is because the problem they're answering is something like "Find a strategy such that if you knew which numbers Alice had picked, but hadn't yet chosen your own random numbers, then you would always anticipate a >50% chance of winning." This resembles the definition of a 95% confidence interval: "A procedure for generating intervals from data, such that if you knew the true value of the parameter, but not the data, you would assign a 95% probability that the true value lies in the interval". Of course Bayesians turn it around and define a credence interval where you know the data but not the true value (which I think is better, because this actually is your state of knowledge).
- tomp 9y ago
  > if Alice picks 10 and 20 and opens 10 first then you have a 0% chance of winning. No because you pick the hand (i.e. it’s essentually random), so you still have 50% chance of first revealing 20 and gettingit right.
  - OscarCunningham 9y ago
    Good point. So our methods are similar, but yours puts the randomness in the choice of hand rather than the choice of integer. But in the (10,20) case your method gets exactly 50% and not more than 50%.
    - deleted 9y ago
      [deleted]
    - sirclueless 8y ago
      This is why your choice of threshold matters. Your strategy should be to choose a threshold randomly from any distribution that is non-zero everywhere (such as a normal distribution), then choose a hand uniformly at random. Choosing zero as a threshold deterministically does not work for all choices that Alice can make because, as you say, for some choices such as (10,20) it gives you exactly 50% chance to win. But as long as there is always a non-zero chance that you chose a threshold between Alice's numbers, then there is a > 50% chance that you win the game.
- Avshalom 9y ago
  It's important to remember that Alice is a perfect random number generator. She certainly isn't going limit her numbers to what can be comfortably written on the paper for instance. Which is fun because while there are hundreds of puzzles that require people to be able memorize perfect hash functions on the fly or remember the state of a FSM 1000 states ago or be capable of implementing the necessary function required by the axiom of choice for a given situation... this is the first puzzle I can think of that requires some one to be able to, with perfect randomness select two integers (-∞,∞)
danbruc 9y ago
Does not work according to [1], see followup puzzle 2 and its solution. At least if my interpretation of your proposed solution is correct, i.e. that you fix your threshold number in advance. Not sure if a delayed random choice would help. [1] https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-googol/ https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-...
- tomp 9y ago
  Hmmm... If Ininterpret their proof (i.e. “Puzzle 2”) correctly, they prove that there’s no deterministic solution that yields probability > 50% for any two numbers... the idea of the solution I posted (which is deterministic) is that you have >= 50% for all numbers, and > 50% for some numbers.