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.
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.
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.
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).
It's important to remember that Alice is a perfect random number generator. She certainly isn't going limit her numbers to what can be comfortably written on the paper for instance.
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 (-∞,∞)
Good point. So our methods are similar, but yours puts the randomness in the choice of hand rather than the choice of integer. But in the (10,20) case your method gets exactly 50% and not more than 50%.
This is why your choice of threshold matters. Your strategy should be to choose a threshold randomly from any distribution that is non-zero everywhere (such as a normal distribution), then choose a hand uniformly at random.
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.
Does not work according to [1], see followup puzzle 2 and its solution. At least if my interpretation of your proposed solution is correct, i.e. that you fix your threshold number in advance. Not sure if a delayed random choice would help.
Hmmm... If Ininterpret their proof (i.e. “Puzzle 2”) correctly, they prove that there’s no deterministic solution that yields probability > 50% for any two numbers... the idea of the solution I posted (which is deterministic) is that you have >= 50% for all numbers, and > 50% for some numbers.
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..
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.
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%?
> 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.
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...
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.
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.
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.
> 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.
> 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.
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.
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.
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.
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.