You and I play the following game: You write two distinct, real numbers on two different sheets of papers (in a way such that I cannot read the numbers). Then I flip one of these sheets, read the number and guess whether the other number is higher or lower. If I guess right, I win, else you win.
There is one caveat: Before you write down your numbers, I will tell you my guessing strategy (a randomized algorithm, I have access to as much truly random data as I want).
Let's say the loser gives the winner 100\$ and my task is to make as much money as possible. There is a strategy with a winning percentage of more than 50%:
I choose a normally distributed random variable $X$. I choose one of the sheets uniformly at random. Let $A$ denote the number behind this sheet. If $X > A$, I say “$B>A$”, else I say “A>B”.
If $X$ is between $A$ and $B$ I win, else I have a winning percentage of $50\%$. As $P(X \in (A, B)) > 0$ my total winning percentage is larger than 50%. (This works with any random real variable having positive probability on all intervals.)
Problem: That strategy does not suffice to make a lot of money, given $\newcommand{\eps}{\varepsilon}\eps > 0$ you can choose your numbers in a way such that my winning percentage is smaller than $0.5 + \eps$. Even if we play the game 1000 times, you can choose your numbers such that my expected win is less than a cent.
That is nearly a fair game – how do I make substantially more money? Are there $\eps \gt 0$ and a strategy with a winning percentage of at least $0.5 + \eps$? I have to tell you my strategy before you choose your numbers.
Or is there no such strategy?
Best Answer
Your strategy is completely defined by specifying, for each number in $\mathbb R$ that you might see, the probability that you guess that it's the higher one. You can only guarantee a winning percentage $\gt\frac12$ if this probability strictly monotonically increases. (Otherwise I can pick a pair where it hasn't increased.) So this probability that defines your strategy is a strictly increasing function $f:\mathbb R\to[0,1]$.
For any $\epsilon\gt0$, I can find $n\in\mathbb N$ such that $f(n+1)-f(n)\lt\epsilon$ and write down $n$ and $n+1$. For if not, the function would increase by at least $\epsilon$ in each integer step, and thus would increase beyond any bound, in contradiction to it being bounded to $[0,1]$. But your winning percentage above $\frac12$ is proportional to this difference. Thus no matter how you choose $f$, I can make your winning percentage as close to $\frac12$ as I want.