[pyk]

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.

[pred_]

> and then assume a random integer yourself C.

This is impossible; there's no uniform measure on the integers (as σ-additivity makes it impossible to bound such a measure).

[OscarCunningham]

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]

Why does this work with probability 2/3 then?

https://jsfiddle.net/q4qbewp1/

[OscarCunningham]

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.

[22c]

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

I'm not sure if that always holds true. Let's say Alice flips a coin and picks 3 or 4 for num1, then Alice flips another coin and picks either num1 - 2 or num1 + 2 for num2.

You come along and pick a number between 1 and 6. You have a non-zero chance of having picked a number between Alice's two numbers, but your chances of winning are not > 0.5.

If you picked a number between 2 and 5 though, your chances of winning are now > 0.5. Like jstanley said, you'd have to know how Alice picks numbers in order to win in the long run.

[jstanley]

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

Wow. This is the key piece of information that makes the problem interesting, IMO. That's quite unintuitive.

If you know anything at all about how your opponent chooses numbers, you win in the long term.

[kd5bjo]

It also tells us what Alice's optimal strategy is: pick the first number at random, and then select an adjacent integer as the second number. Thus, there's no space between them that your prior can assign any probability to.

[OscarCunningham]

Well your strategy has to have some way of breaking ties, when Alice's number is the same as yours. Lets say that you always say "higher" in that case. Then you always win whenever your number is between Alice's or equal to the smaller of them. Equivalently you could just pick a random half-integer.