Consider the following interesting puzzle:
"Alice writes two distinct real numbers between 0 and 1 on two sheets of paper. Bob selects one of the sheets randomly to inspect it. He then has to declare whether the number he sees is the bigger or smaller of the two. Is there any way he can expect to be correct more than half the times Alice plays this game with him?"
SPOILER ALERT: In the linked site below, the solution to this puzzle is right below the posed question.
The puzzle is lifted from here.
In the following questions, I have just given my hunch. My calculations could be wrong as I am not very strong at probability.
Questions:
1) Is there an assumption here that Bob can play the game many times with Alice (from the last statement)? Are the real numbers assumed to be fixed?
My hunch: If it is played in time, then fixed real numbers dont make sense. So perhaps we have to think over different realizations. Is this right?
2)[Variant] If Bob knows that Alice samples the two real numbers uniformly and independently from [0,1] every time she plays then can he design a strategy that works more than half of the times?
My opinion: I have a strategy that works two-thirds of the time. However I am not sure if that is the best! Is there a strategy that works better?
3) Is there a distribution from which if Alice samples her numbers independently, then she can ensure that Bob can never do better than getting right half the time?
My opinion: No! Although I am not sure. I guess the independence assumption is what allows Bob to get a good strategy.
4) If Alice can sample two real numbers in a correlated fashion every time she plays, can she ensure that Bob can never do better than getting right half the time?
My opinion: Yes! I think I have an answer.
P.S: I will post my version of the answers after a few days, if nobody comes up with the same idea. Thanks! 🙂
P.P.S: This is not a homework problem, but just a musing 🙂
Best Answer
1) That's not well-specified in the formulation of the problem.
2) You can attain $3/4$ by choosing the first number iff it's above $1/2$.
3) No, she can't but that has nothing to do with independence; see 4).
4) No, she can't; see the links in my comment under the question.