Hacker News Reader

> 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

Well, frankly, you're merely restating the problem :-)

Intuitively, if my f(t) is extremely heavily weighted in the interval (-100, -90), and my splitting value is usually in this range, and if Player 1 only picks positive values (randomly or otherwise), then ...

Never mind - I get it now :-)

To complete the thought, then almost every time I'll have a 50% chance of being right. But since f(t)>0 everywhere, every once in a while, even if it happens once in a billion years, I will pick a splitting value in between A and B, and this will bump the overall probability to be over 50% just slightly. Furthermore this doesn't matter whether player 1 is even utilizing randomness - it will work if he is always picking 10 and 20.

So you were on the right track, but you do not replace 1/2 with p and 1-p. Assuming Player 2 randomly picks one slip of paper (stated in problem), he will be right 50% of the time when the splitting value is not between the two numbers (almost always in my scenario). On the rare occasions your splitting number is in between the two, you will be right 100% of the time.

I prefer this explanation as the 75% one has a lot of assumptions (uniform randomness, splitting at 0, etc), and there are quite a few comments asserting 75% when in reality it can be any probability over 50%. I can relax these constraints to drastically reduce the probability to 50 + epsilon, but epsilon > 0 always.

The thing that continues to bother me: How does one get a splitting value? In classical probability, if you have a continuous distribution (which f(t) is), then using it to pick a point is impossible/meaningless. If I try to come up with an "approximation" scheme that discretizes f(t), then I can always come up with a strategy for Player A to defeat that scheme.

> If I try to come up with an "approximation" scheme that discretizes f(t), then I can always come up with a strategy for Player A to defeat that scheme.

Player A does not know what your scheme is, and you are free to change it - in fact, you can change it for each round, and thus defeat any attempt by A to deduce it. In other words, don't have a scheme, forget about f(t), and just pick a number. Any number you pick is, ipso facto, from any number of distributions that are nonzero everywhere (and also, as it happens, from any number that are not), regardless of whether or not you have any of them in mind.

The distribution f(t) does not appear in the explanation of the outcome, and I think it's true to say that the only reason f(t) is mentioned at all is that if you do instead choose from a distribution from which some ranges of numbers are excluded, then the puzzle-poser can no longer say that your odds are strictly greater than 50-50, as player A might always pick from an excluded range (for example, if player B stubbornly insists on only picking positive numbers, and player A is determined on only playing negative numbers.) Without the requirement for f(t) to be nonzero everywhere, I think then either one would have to drop the 'strictly' claim, which makes the result look far less paradoxical (B can sometimes do better than 50-50), or one would have to put some constraints on how A chooses the number-pairs (and, furthermore, those constraints would be dependent on which particular distribution B was using.)

> In other words, don't have a scheme, forget about f(t), and just pick a number. Any number you pick is, ipso facto, from any number of distributions that are nonzero everywhere (and, likewise, from any number that are not), regardless of whether or not you have any of them in mind.

I'm not sure I agree or understand.

While it's trivially true that all numbers out there are part of some f(t) that is nonzero everywhere, that knowledge isn't helping me.

As an example, if I always pick the same number, then the scheme doesn't work. Perhaps where we disagree is:

> Player A does not know what your scheme is

The beauty of the solution is that you can tell Player A your scheme and still guarantee > 50%. My solution doesn't preclude A from knowing your scheme. So definitely picking the same splitting point over and over will not work.

I take it you probably meant "pick a number, but change the number". Yes, but how? As someone pointed out, using a random number generator on any given machine will not work as player A can always pick two numbers that are close enough to each other that there is no number on the machine in between them.

My concern is that this problem will end up being similar to the well ordering principle, where it's been proven that you can come up with a well ordering on the reals, but it's also been proven that you can never show it to me.

>and I think it's true to say that the only reason f(t) is mentioned at all is that if you do instead choose from a distribution from which some ranges of numbers are excluded, then the puzzle-poser can no longer say that your odds are strictly greater than 50-50

This isn't a minor point. It's trivial to come up with a 50% scheme. This is an interesting solution in that it guarantees > 50% no matter what Player A does.

I think I misunderstood your issue here - I misread 'scheme' as an algorithm for picking splitting numbers.

> Using a random number generator on any given machine will not work as player A can always pick two numbers that are close enough to each other that there is no number on the machine in between them.

On reflection, I am not sure that the method presented in this article can guarantee > 50% in any case where the domain is discretized. Note that the original article does not say what to do if the first number revealed is equal to B's splitting number. If A always chooses adjacent numbers, there are never any 'tiebreaker' splitting numbers - i.e. those that are strictly between A's numbers, and will elicit the correct response regardless of whether B has seen the larger or the smaller of the pair.

I know, it was totally counterintuitive until I coded it. Same kind of deal with the Monte Hall problem.

I think it can be more intuitively explained without getting into math: if you know someone wrote down two random numbers between 1 and 10. You look at one and have to guess if the other one is higher or lower.

Say you flip over a 2: what do you think is the right guess?

Of course, but I'm having trouble understanding why this works on an infinite number line. Say you flip over a 2,387,290,723,013,172,348,238,987: what do you think is the right guess?

Its the largest because its positive, 75% I’m right.

And if we are only looking at positive numbers in an infinite axis I’d need to borrow your generator for a test to approximate its midpoint (which obviously it doesn’t have), which I then weigh against the original number with the logic “if it’s larger than what I got, so is your other number. If it’s smaller so is the other number.” Now since the chance for my number being the middle of the three drawn is 1/3(only case I lose), that gives me 66% chance of winning that bet.

I think this distracts from the actual problem. They have a more generalized case, (-inf, inf).

In your case, if we don't allow double selecting, 2 is the lowest number between 1 and 10. So you have a 100% chance of guessing right. You're using the bound to help you. Being unbounded you still have an infinite set of numbers smaller than the number you see and an infinite number higher. To be more analogous, that would be like flipping over 5 every single time (on [0,10]). You have {1,2,3,4} below and {6,7,8,9} above. EVERY TIME.

The reason it's counterintuitive is because, in the game, you don't know that the two numbers are random. In fact, they are chosen by an adversary. You flip a 2: do you think this is most likely the lower number, or do you think the other player picked 1 and 2 just to mess with you?

That's the point of picking a random pivot: it reduces your opponent's ability to influence the situation to only placing their numbers as close to each other as possible.