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.
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.
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.
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).
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.
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.
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 (-∞,∞)
[1] https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-...
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-o...
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.
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%?
pyk's solution above works 66.6% even for the first try...
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.
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.
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
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
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.
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.
This is impossible; there's no uniform measure on the integers (as σ-additivity makes it impossible to bound such a measure).
If the range isn't limited, hoe would we even define a normalized probability distribution?