from Hacker News

A Counterintuitive Probability Game

by EvanWard97 on 10/3/19, 1:01 AM with 65 comments

• by dsukhin on 10/3/19, 2:57 AM

  This is a super facinating observation. At first it does seem very counterintuitive but after a little examination, the resulting probabilities make a lot of sense.

  For sake of easy math, pick C, your threshold, to be fixed at 0, which is halfway between -inf and inf.

  Now there are 4 scenarios. The numbers player 1 chooses, A and B, can be both above or both below C with probability 1/4 each. In both those cases, you have a 50/50 chance of being correct on which number is larger depending on which number you chose to see.

  Then, with the other 1/2 of the times, one number will be above and the other will always be below C. In those cases, the selected strategy will have you always choose the correct highest number.

  All together you are right 1/2 + 2 * 1/4 * 1/2 = 3/4 = 75% of the time. Simple probability but totally counterintuitive from the onset.

  Now what if C!=0 or numbers are not being selected uniformly by your opponent? You can replace the 1/2's with (p) and (1-p) in the right spots without making any distributional assumptions and it seems (without doing the math out fully) that things cancel nicely and show that you always have a strictly greater than 1/2 chance of guessing right no matter what. Exercise left for the reader :P

• by greenbay20 on 10/4/19, 12:47 AM

  Note that the paper claims that no matter how player A chooses the two numbers to write down, you can always guarantee >50% chance in guessing which one is the higher one after only looking at one of the numbers. The reason this seems counter-intuitive is that the only information you're given is one of the numbers. You are not told anything about how the first player picked her numbers. Now, the reason why OP's code does not seem counter-intuitive to most is that it shows a quite different result. The OP assumed a specific distribution (which is a strong assumption, one the paper does not make) and found a strategy that yields > 50%.

• by nabdab on 10/3/19, 9:53 PM

  I’m really struggling to see how this is counter intuitive? You pick one of the numbers, and if it’s positive you say “this is likely the largest” and if negative “this is likely the smallest”. Since there’s a 50/50 chance for each sign, and all positive numbers are larger than all negative numbers. That already gives you the minimum 1/2 probability they are asking for. But you’ve got an improvement because not only does the other number have to match the sign for you to lose, it also has to be larger in magnitude, and that happens in half the cases where they have the same sign, so that gives you 1/4 extra. You end up being correct 75% of the time. The thing with a random number in between is just an odd way of reducing your probability of winning by adding randomness to the split, what that’s supposed to show I’m really confused by.

  It feels like the “puzzlement” you are supposed to feel that you can beat 50% comes from people ignoring the fact that you can look at the number before making your call.

• by gentaro on 10/3/19, 8:54 AM

  I may be missing something here, but I'm not sure this is quite right.

  The paper attached describes a scenario where the player A chooses a number between -infinite to infinite. The simulation uses ranges -1000000 to 1000000, it's not a surprise that the strategy works in this case.

  I think if the ranges were truly -infinite to infinite, this strategy would fall apart. No matter where you set C, there are infinite values above and below it.

• by laegooose on 10/4/19, 6:38 PM

  Strictly speaking, the _probability_ that Player 2 did correct choice is not defined unless the random distribution used by Player 1 is defined.

  Consider a paradox: Player 1 picks a random number X, writes it on a slip of paper, and 2X on another slip, and puts them randomly in front of Player 2 as "left" and "right". Player 2 wins amount of money written on a slip he chose.

  Let's say he is about to pick left one (but didn't see it yet). Let's say left has number Y. The right one has either Y/2 or 2Y, with 50/50 probability. Which means right one is more profitable to pick, because it has 1.25Y on average!

• by bko on 10/3/19, 10:29 AM

  From the paper, the only conditions of the first player (the person picking the initial two random numbers) is that they are distinct. They don't have to be random and (as the implementation has) bound by the same range as the second player. If you use a different bound range for the two players, you get about 50/50 odds.

  The part I changed is scaling down the first players range by a factor of 100

  a=random.randint(-R//100,R//100)

  b=random.randint(-R//100,R//100)

• by markisus on 10/4/19, 7:28 PM

  I think I drew a picture that could explain the effect. In the picture, player 2's lower number is A, and their higher number is B.

  https://imgur.com/a/DKCtH81/

  Red is the region where you lose, and Green is the region where you win.

• by lonelappde on 10/5/19, 12:07 AM

  The "solution" relies on the fact that positive numbers arbitrarily close to 0 are still technically positive. If you assume that the range of numbers is finite, the solution is much more intuitive. If you assume that the range of numbers is actually infinite, and don't use a misleading python program, a win ratio of "0.5 + unknowably arbitrarily small episilon" is the least impressive "strictly greater than 0.5" you can imagine.

  You can't win real money gambling in this game if you actually have infinite range of numbers.

• by zxcmx on 10/5/19, 10:38 AM

  This still makes no sense to me. Picking a random number C adds no information, so I can't see how it can influence the accuracy of your decision. Just from a naive information theoretic point of view.

  If it's possible to get some epsilon of advantage by choosing a C once, then... can you do it more? Can you combine or average more of them? Is 1 optimal? Why?

  I fee like there's some shenanigans here regarding assumptions about the distribution of A, B and C but I can't really put my finger on it.

• by KwisatzHaderack on 10/4/19, 5:27 AM

  Very interesting, thanks for sharing.

  If C is chosen from the exact same distribution as A and B, I wonder if the strategy works even better than if C were any other random distribution. My intuition says yes.

• by kgwgk on 10/4/19, 7:05 PM

  > the benefit of using the entire Real number line as the possible range for C is to ensure that you at least sometimes

  This may be a probability zero event unless you make some additional assumptions about how the numbers are selected. The whole real line is quite big and the probability of two finite intervals overlapping is null.

  > choose a value in between the ranges the other player is selecting numbers from

• by deckar01 on 10/3/19, 1:41 PM

  If you have ever played a card game where you have to guess if the next card is going to be higher or lower than another card, this should not be a surprising result. You should always assume the next card will be the average of all possible cards. What makes these kinds of games fun is having to recalculate the average card in you head based on the cards that you can see.

• by tomas789 on 10/3/19, 5:53 AM

  I’m struggling with choosing a random number t from (-inf, inf) where P(t) > 0.

• by godelski on 10/4/19, 6:52 PM

  From reading the comments, it seems the counter-intuitive part is that a bound like (-inf, inf) is different than a bound like [0,10].

• by Ragib_Zaman on 10/5/19, 3:39 PM

  Great problem OP.

  1 - As some people have already clarified for other commenters, it indeed makes no difference how Player 1 picks their numbers. They can pick them from some distribution of their own, or in an adversarial manner. The probability of winning by following the strategy in the paper is still strictly greater than 1/2.

  2 - In fact, even if Player 1 can read Player 2's mind and knows their strategy and even the exact distribution they will sample from (but can't see into the future to see the sample from the distribution), the probability is still strictly greater than 1/2.

  3 - Since it isn't actually included in the paper or any of the comments, for the sake of completeness I'll write down the computation.

  Let P(E) denote the probability of an event E, and W be the event that Player 2 wins by following the strategy suggested in the paper. Let a, b be the smaller, larger number respectively. A is the event that Player 2 picked a, B is the event that Player 2 picked b. Then summing over disjoint events,

  P(W) = P(A and W) + P(B and W) = P(W | A)P(A) + P(W | B)P(B)

  We have P(A) = P(B) = 1/2. Now let x be the result of Player 2 sampling from their distribution. Given that they picked A, they win if and only if a <= x, so P(W | A) = P(a <= x). Given that they picked B, they win if and only if x < b, so P(W | B) = P(x < b). Therefore,

  P(W) = (1/2) [P(a <= x) + P(x < b)] = (1/2) [1 + P( x in [a,b) )]

  4 - If I were to show this problem to someone else, I may try to emphasize the potentially adversarial nature of Player 1 and the odds seemingly being stacked against Player 2 by phrasing it like this (although this may be _over_ exaggerated):

  * Player 1 gets to write down any two distinct real numbers on two pieces of paper, and then flips a coin. Player 2 gets to see the number on the left if the coin lands on Heads, the number on the right if the coin lands on Tails. After seeing the number, Player 2 must declare whether they are seeing the smaller or larger number. If Player 2 guesses correctly, they win $1 from Player 1. Otherwise, Player 2 pays $1 to Player 1.

  Further, now knowing the rules of the game, both players can choose any particular strategy of playing the game. However, whatever Player 2 chooses as their strategy, they must inform Player 1 of their strategy and not deviate from it when the game is played. Player 1 is allowed to adjust their strategy after hearing Player 2s strategy. Would you prefer to be Player 1 or Player 2? *

  I think worded like that, many peoples first guess might even be Player 1. Then their next answer would be that it doesn't matter, and then they're in for a treat when they see that they should choose to be Player 2!