$\textit{Question:}$
Given a coin with probability p of landing heads after being flipped, pick two numbers a, b such that a $\neq$ b, and associate “heads” to one of them and “tails” to the other. Flip the coin and give the number associated to the flip to your friend. For what values of p is there a strategy for your friend so that the probability of predicting whether the number that is given is bigger than the number that is not given is strictly greater than 1/2 despite being allowed to know how you select the numbers a and b?
Stuck with this problem recently. A strategy definitely exists for certain values of $p$, that's what my prof told. Can't get my head around it though.
The case when $p=1/2$ is a classic puzzle. WLOG, $a<b$.
For any real number $x$, define $S_x$ to be the following strategy:
If the number you are told is less than $x$, guess that it is lower than the other number.
Otherwise, guess that the number you are told is higher than the other number.
Note that $S_x$ always gives a win whenever $a< x \le b$. If $x\le a$, then you always guess "higher" and win with probability $1/2$. Similarly, if $x>b$, you always guess "lower" and win with probability $1/2$.
Therefore, in order for your friend to ensure they have an edge, all they need to do is randomly choose $x$ so that $x\in (a,b]$ with some nonzero probability. If $a,b$ are integers, this can be done by using a geometric random variable to choose a random integer $n$, then let $x=n+\frac12$. If $a$ and $b$ are real numbers, you can instead choose a random rational number by writing all the rational numbers in a list and using a geometric random variable to choose an element of this list.
I am not sure what to do when $p\neq 1/2$. Certainly when $p=0$ or $p=1$, there is no way to get an edge. I suspect that the same is true for all other $p\neq 1/2$, but I am not sure.