6 ms·

Another very counterintuitive (for me) problem: how do you do better that break even in the following game: 'A' chooses two distinct integers, writes them on s

by tomp 9y ago

Another very counterintuitive (for me) problem: how do you do better that break even in the following game: 'A' chooses two distinct integers, writes them on slips of paper and holds one out in each hand in a fist. You choose a hand and reveal a number. You must then guess whether the other number is higher or lower than the revealed one, winning $1 if you guess right and losing $1 otherwise.

mulur 9y ago
Hmm I'm not exactly good with maths (or puzzles for that matter) but here is a blind stab: By break even, I think you mean that the game is played multiple times, as long as necessary. If you are not following a martingale like strategy (edit: you can't anyways, the bets are fixed) and respond randomly (or with full faith that this is your lucky day, doesn't matter really), you are expected to break even with 50% chance. How can we improve and make better than 50%? 'A' chooses two distinct integers each time. They can choose among infinite number of integers. For the first guess, I can't do better than 50% chance but if I start to keep history of the numbers that were picked it feels to me like I can do better than chance if I assume A chooses their distinct integers uniformly random by expecting a uniform distribution. I don't have much ideas about how to judge uniformness in an unbounded set of integers though but maybe something like: if first hand is less than the average of all previous numbers, I'd say "other number is higher", otherwise I'd say "other number is lower". I feel like this would improve my chances to more than 50% in the very long term (at infinite plays perhaps?) but am not able to prove it. If A is not choosing their numbers randomly with a true RNG then I'd play many games at 50% chance then run their choices through a neural network to extract patterns then I'd do better than random for sure.
- sirclueless 9y ago
  You can do better than that. You can guarantee there is > 50% chance you win on the first guess.
  - Hoagy 9y ago
    Wow, that is very counterintuitive.. I suppose you could set any threshold x, and play so that if the first number is bigger than x you stick, otherwise you switch. This would be strictly better than random (break even) if x is within the range of numbers that A is picking from and the same as random if not. It depends on when you measure your chances: before A has picked a generator this gives you >50% chance but if A has already picked a range to draw from that doesn't contain x then you're back to 50/50. Still, I think this would count as guaranteeing >50%?
  - mulur 9y ago
    Oh that's interesting. Thank you for the clarification.
  - mulur 9y ago
    Ok, my solution is needlessly complicated because unbounded numbers between -Infinity and Infinity has a mean of 0, so if we just pick 0 and say "if hand1 < 0 then next is bigger, otherwise smaller" strategy already gives 75% accuracy long term. pyk's solution above works 66.6% even for the first try...
  - mundo 9y ago
    > You can guarantee there is > 50% chance you win on the first guess. You mean "greater than" and not "greater than or equal to"? The latter is easy; lots of naive strategies accomplish that. But the former implies that you can declare a strategy and the puzzle offerer cannot then pick a distribution that defeats it. It's hard to imagine how you could get >50% for example if the puzzler's strategy is to pick N and N+1 for very large N.
pyk 9y ago
After writing this one out, this reminds me of the Monty Hall problem. In this case my guess is that you use a prior -- assume the two unknown numbers are A & B, and then assume a random integer yourself C. From there, if A (the first revealed number) is less than C, then that narrows the remaining cases giving you a 2/3 chance. If A is greater than C, that also narrows the remaining cases and gives you a 2/3 chance as well. On a number line, the cases are below. If A > C then the six originally equally possible cases are narrowed to three cases: A-----B-----C (impossible) A-----C-----B (impossible) B-----A-----C (impossible) B-----C-----A B < A C-----A-----B B > A C-----B-----A B < A So you would guess B < A -- the first hand's number is higher with probability 2/3. If A < C then the six originally equally possible cases are also narrowed to three cases: A-----B-----C B > A A-----C-----B B > A B-----A-----C B < A B-----C-----A (impossible) C-----A-----B (impossible) C-----B-----A (impossible) So you would guess B > A -- the first hand's number is lower with probability 2/3.
- OscarCunningham 9y ago
  This works, but you don't get a probability of 2/3, because the cases aren't equally likely. There isn't a probability distribution for C such that for any A and B the probability of A<C<B is 1/3. We would have to have P(0<C<10)=1/3 and P(10<C<20)=1/3 and P(0<C<20)=1/3, which is impossible.
  - conorh 9y ago
    Why does this work with probability 2/3 then? https://jsfiddle.net/q4qbewp1/ https://jsfiddle.net/q4qbewp1/
    - OscarCunningham 9y ago
      Because of the particular distributions that you happen to have chosen. Alice doesn't have to pick uniformly at random. Since 0^p=0 and 1^p=1 we can experiment with different distributions by using "Math.pow(Math.random(),p)" in place of "Math.random()". For example: var prior = Math.pow(Math.random(),1); var hand1 = Math.pow(Math.random(),10); var hand2 = Math.pow(Math.random(),10); > Win probability: 0.5757182 and var prior = Math.pow(Math.random(),1); var hand1 = Math.pow(Math.random(),0.1); var hand2 = Math.pow(Math.random(),10); > Win probability: 0.9026432 But the win probability will always be >0.5 so long as the "prior" probability distribution has a nonzero probability of being between Alice's two numbers.
OscarCunningham 9y ago
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).
konschubert 9y ago
Is the range of integers limited? Does she choose them randomly? If the range isn't limited, hoe would we even define a normalized probability distribution?
- tomp 9y ago
  I posted a solution: https://news.ycombinator.com/item?id=17002492 https://news.ycombinator.com/item?id=17002492
- konschubert 9y ago
  *how
Semkas 9y ago
Assume that the range of integers is limited by the largest positive or negative number that can be written on the limited space of the paper. Whenever the largest positive or negative number comes up your answer will be certain. Turn a profit over a few billion years.
- tomp 9y ago
  I posted a solution: https://news.ycombinator.com/item?id=17002492 https://news.ycombinator.com/item?id=17002492
ttctciyf 9y ago
This is the same as discussed by John Baez and others at https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-googol/ https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-... right? (spoilers!)
jessriedel 9y ago
Folks who are interested in reading more about this problem should know the search term "two-envelopes problem". https://en.m.wikipedia.org/wiki/Two_envelopes_problem https://en.m.wikipedia.org/wiki/Two_envelopes_problem
ccvannorman 9y ago
This is actually funny. I would argue the solution is invalid, except that due to mortality it actually works. The problem lies in the assumption about how Alice thinks. The set of integers is countably infinite, so your probability to guess a specific number N is zero if the distribution is uniform (e.g. there isn't a higher likelihood of picking "smaller / closer to zero" numbers.) [1] But because it would take a lot of mortal time to describe arbitrarily large numbers, you MUST assume that because Alice is mortal, she'll pick a number she could describe in her lifetime. Therefore, the question is not valid. Alice does not truly have a domain over all the integers to choose from. She only has the ability to pick numbers she could write down on a slip of paper within her lifetime. Since the paper is limited in how much information it can contain anyway, it therefore cannot represent any arbitrary integer from the infinite set. So the question is re-written: Alice picks two integers from a finite pool.. [1] https://math.stackexchange.com/questions/30619/probability-of-picking-a-specific-value-from-a-countably-infinite-set https://math.stackexchange.com/questions/30619/probability-o...

by tomp 9y ago

mulur 9y ago

Hmm I'm not exactly good with maths (or puzzles for that matter) but here is a blind stab: By break even, I think you mean that the game is played multiple times, as long as necessary. If you are not following a martingale like strategy (edit: you can't anyways, the bets are fixed) and respond randomly (or with full faith that this is your lucky day, doesn't matter really), you are expected to break even with 50% chance. How can we improve and make better than 50%? 'A' chooses two distinct integers each time. They can choose among infinite number of integers. For the first guess, I can't do better than 50% chance but if I start to keep history of the numbers that were picked it feels to me like I can do better than chance if I assume A chooses their distinct integers uniformly random by expecting a uniform distribution. I don't have much ideas about how to judge uniformness in an unbounded set of integers though but maybe something like: if first hand is less than the average of all previous numbers, I'd say "other number is higher", otherwise I'd say "other number is lower". I feel like this would improve my chances to more than 50% in the very long term (at infinite plays perhaps?) but am not able to prove it. If A is not choosing their numbers randomly with a true RNG then I'd play many games at 50% chance then run their choices through a neural network to extract patterns then I'd do better than random for sure.

sirclueless 9y ago
You can do better than that. You can guarantee there is > 50% chance you win on the first guess.
- Hoagy 9y ago
  Wow, that is very counterintuitive.. I suppose you could set any threshold x, and play so that if the first number is bigger than x you stick, otherwise you switch. This would be strictly better than random (break even) if x is within the range of numbers that A is picking from and the same as random if not. It depends on when you measure your chances: before A has picked a generator this gives you >50% chance but if A has already picked a range to draw from that doesn't contain x then you're back to 50/50. Still, I think this would count as guaranteeing >50%?
- mulur 9y ago
  Oh that's interesting. Thank you for the clarification.
- mulur 9y ago
  Ok, my solution is needlessly complicated because unbounded numbers between -Infinity and Infinity has a mean of 0, so if we just pick 0 and say "if hand1 < 0 then next is bigger, otherwise smaller" strategy already gives 75% accuracy long term. pyk's solution above works 66.6% even for the first try...
- mundo 9y ago
  > You can guarantee there is > 50% chance you win on the first guess. You mean "greater than" and not "greater than or equal to"? The latter is easy; lots of naive strategies accomplish that. But the former implies that you can declare a strategy and the puzzle offerer cannot then pick a distribution that defeats it. It's hard to imagine how you could get >50% for example if the puzzler's strategy is to pick N and N+1 for very large N.

pyk 9y ago

After writing this one out, this reminds me of the Monty Hall problem. In this case my guess is that you use a prior -- assume the two unknown numbers are A & B, and then assume a random integer yourself C. From there, if A (the first revealed number) is less than C, then that narrows the remaining cases giving you a 2/3 chance. If A is greater than C, that also narrows the remaining cases and gives you a 2/3 chance as well. On a number line, the cases are below. If A > C then the six originally equally possible cases are narrowed to three cases: A-----B-----C (impossible) A-----C-----B (impossible) B-----A-----C (impossible) B-----C-----A B < A C-----A-----B B > A C-----B-----A B < A So you would guess B < A -- the first hand's number is higher with probability 2/3. If A < C then the six originally equally possible cases are also narrowed to three cases: A-----B-----C B > A A-----C-----B B > A B-----A-----C B < A B-----C-----A (impossible) C-----A-----B (impossible) C-----B-----A (impossible) So you would guess B > A -- the first hand's number is lower with probability 2/3.

OscarCunningham 9y ago
This works, but you don't get a probability of 2/3, because the cases aren't equally likely. There isn't a probability distribution for C such that for any A and B the probability of A<C<B is 1/3. We would have to have P(0<C<10)=1/3 and P(10<C<20)=1/3 and P(0<C<20)=1/3, which is impossible.
- conorh 9y ago
  Why does this work with probability 2/3 then? https://jsfiddle.net/q4qbewp1/ https://jsfiddle.net/q4qbewp1/
  - OscarCunningham 9y ago
    Because of the particular distributions that you happen to have chosen. Alice doesn't have to pick uniformly at random. Since 0^p=0 and 1^p=1 we can experiment with different distributions by using "Math.pow(Math.random(),p)" in place of "Math.random()". For example: var prior = Math.pow(Math.random(),1); var hand1 = Math.pow(Math.random(),10); var hand2 = Math.pow(Math.random(),10); > Win probability: 0.5757182 and var prior = Math.pow(Math.random(),1); var hand1 = Math.pow(Math.random(),0.1); var hand2 = Math.pow(Math.random(),10); > Win probability: 0.9026432 But the win probability will always be >0.5 so long as the "prior" probability distribution has a nonzero probability of being between Alice's two numbers.

OscarCunningham 9y ago

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).

konschubert 9y ago

Is the range of integers limited? Does she choose them randomly? If the range isn't limited, hoe would we even define a normalized probability distribution?

tomp 9y ago
I posted a solution: https://news.ycombinator.com/item?id=17002492 https://news.ycombinator.com/item?id=17002492
konschubert 9y ago
*how

Semkas 9y ago

Assume that the range of integers is limited by the largest positive or negative number that can be written on the limited space of the paper. Whenever the largest positive or negative number comes up your answer will be certain. Turn a profit over a few billion years.

tomp 9y ago
I posted a solution: https://news.ycombinator.com/item?id=17002492 https://news.ycombinator.com/item?id=17002492

ttctciyf 9y ago

This is the same as discussed by John Baez and others at https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-googol/ https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-... right? (spoilers!)

jessriedel 9y ago

Folks who are interested in reading more about this problem should know the search term "two-envelopes problem". https://en.m.wikipedia.org/wiki/Two_envelopes_problem https://en.m.wikipedia.org/wiki/Two_envelopes_problem

ccvannorman 9y ago

This is actually funny. I would argue the solution is invalid, except that due to mortality it actually works. The problem lies in the assumption about how Alice thinks. The set of integers is countably infinite, so your probability to guess a specific number N is zero if the distribution is uniform (e.g. there isn't a higher likelihood of picking "smaller / closer to zero" numbers.) [1] But because it would take a lot of mortal time to describe arbitrarily large numbers, you MUST assume that because Alice is mortal, she'll pick a number she could describe in her lifetime. Therefore, the question is not valid. Alice does not truly have a domain over all the integers to choose from. She only has the ability to pick numbers she could write down on a slip of paper within her lifetime. Since the paper is limited in how much information it can contain anyway, it therefore cannot represent any arbitrary integer from the infinite set. So the question is re-written: Alice picks two integers from a finite pool.. [1] https://math.stackexchange.com/questions/30619/probability-of-picking-a-specific-value-from-a-countably-infinite-set https://math.stackexchange.com/questions/30619/probability-o...