Puzzle: Guessing the bigger number!

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 amusing :)

-
– joriki Aug 7 '12 at 13:05
I think I saw this on mathoverflow. – Pedro Tamaroff Aug 7 '12 at 14:42

2 Answers

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.

-
Thanks for the links. For the fourth part, if Alice fixes one of the numbers to, say half, and tosses a coin to pick the other number as 0.75 or 0.25. How can Bob ever get it right more than half of the time? – Isomorphism Aug 7 '12 at 13:38
@Isomorphism: Did you follow the links? It would make more sense if you told me what part of the answers there you don't understand rather than me explaining everything again from scratch. You don't need randomization for this example, though -- Bob can just always accept the $.75$ and reject the $.25$ (it doesn't matter what he does with the $.5$) -- then he'll have a $3/4$ chance of winning. – joriki Aug 7 '12 at 13:47
1. If the real numbers are drawn from a fixed and finite set known to Bob, i.e. Alice picks $x,y$ with $x,y \in S$ where $S$ is a finite set, he can win whenever he chooses the minimum or maximum element of $S$. If Alice draws at random from $S$, Bob can win more often than not by setting a threshold at the median of $S$. On the other hand, if $S$ is an infinite set, e.g. the rationals in $(0,1)$, and Alice picks from this set, Bob cannot use this strategy because $S$ has no smallest or largest element, nor does it even have a median.

2. If Alice samples i.i.d. from $U(0,1)$, by symmetry Bob should set a threshold at $0.5$. Then Bob should win with probability $p = \frac{3}{4}$ as per Joriki's answer.

3. I don't think so, but am not sure.

4. Alice first picks a number $x$ distributed as $x \sim U(0,1)$. Then she should write the two numbers $x - \epsilon, x + \epsilon$ where $\epsilon > 0$ is made as small as Alice wants, so that Bob gains no information from knowledge of one of the two numbers. If $\epsilon$ is sufficiently small, Bob can only guess correctly with probability $p = \frac{1}{2}$, i.e. $p \rightarrow \frac{1}{2}^+\text{ as }\epsilon \rightarrow 0^+$.

-