3
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ I haven't given it much thought, but I'm inclined to think that you can't do terribly much better than 50% $\endgroup$ Oct 1, 2018 at 21:01

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

We are in a similar situation as in the following links.

(And in many others. There is not too much to say about why the chance to win is > 1/2, but as i started a wrong answer, now i rather correct it instead of deleting it. Very probably i would have not even started an answer form my today position of understanding.)

"My" strategy of play was to choose independently a random variable $Y$ with values in $\{S,T\}$ for some real values $S,T$ with $S<T$, uniformly distributed, then get the probability of win depending on the mean $\mu=EX$ and variance $\sigma^2$ of $X$.

Let $\bar Y = (S+T-Y)$. (So $\bar Y$ is $S$ if and only if $Y$ is $T$.)

Then we have a two-levels experiment, the first level being the choice of the sheet.

Then we have to compute the win probability $W$ with the described strategy $$ \begin{aligned} W =& \frac 12\Big( \ P( X>Y\text{ and }\bar Y>Y )+ P( X<Y\text{ and }\bar Y<Y )\ \Big)\\&\qquad\text{[ Sheet A is $Y$ ]} \\ +& \frac 12\Big( \ P( X>\bar Y\text{ and }Y>\bar Y )+ P( X<\bar Y\text{ and }Y<\bar Y )\ \Big)\\&\qquad\text{[ Sheet A is $\bar Y$ ]} \\[4mm] =& \frac 12\Big( \ P( X>Y\text{ and }Y=S )+ P( X<Y\text{ and }Y=T )\ \Big) \\ +& \frac 12\Big( \ P( X>\bar Y\text{ and }Y=T )+ P( X<\bar Y\text{ and }Y=S )\ \Big) \\[4mm] =& \frac 12\Big( \ P( X>S\text{ and }Y=S )+ P( X<T\text{ and }Y=T )\ \Big) \\ +& \frac 12\Big( \ P( X>S\text{ and }Y=T )+ P( X<T\text{ and }Y=S )\ \Big) \\[4mm] =& \frac 12\Big( \ P( X>S)+ P( X<T)\ \Big) \\ =& \frac 12+\frac 12 P(S\le X\le T)\ . \end{aligned} $$ Same as in the question.


There is nothing new above, only that i was trying to explain the things for myself in a very special case. Now the question is if there is a strategy that works with a better probability for you, based on the only information of the number of the number in one randomly chosen sheet, and i suppose, we still proceed in the following order:

  • you fix a random strategy to keep or switch, for instance the parameters of the gaussian random variable in the original post, and the decision strategy based on it, you tell me the strategy, but not also the (class and) parameters of the random variable,
  • i choose two numbers, write them on two sheets, offer the sheets, and to fix the ideas, i will always write two fixed numbers, $S<T$.
  • now you make visible one of the numbers, $S$ or $T$, as known from my side. (I assume this step is kept regarding the question "...how do I make substantially more money?" else the strategy could be changed to show both sheets of paper with their numbers.) And with a "simpler" random variable the decision is to switch or keep. For each $s\in \Bbb R$ let $k(s)\in[0,1]$ be the probability to keep the $s$. This depends on the strategy chosen. So in our case, only the numbers $k(S)$ and $k(T)$ do matter.

Now to the question. Fix some $\epsilon >0$. We have an infinite family $(k(s))_{s\in\Bbb R}$ of numbers in $[0,1]$. Then we can find two members in the family, $k(S)$ and $k(T)$, so that $$ |k(S)-k(T)|<\frac {\epsilon}{2018}\ . $$ If i have the information in $(k(s))_s$, then i am choosing them in this way, and the probability that you win is smaller than $\frac 12+\epsilon$ with an argument similar to the above for a gaussian $X$ implementing the decision to keep the visible sheet.

Even if i do not have the information, there is a chance that i am randomly choosing two numbers $S,T$ with $|k(S)-k(T)|<\epsilon/2018$ with positive probability, so that you cannot "do better than $\frac 12+\epsilon$".


$\endgroup$
3
  • $\begingroup$ Sorry, I cannot follow. Why does your third „$=$“ hold? Do you claim $P(X < 1 \land Y = 1) = P(X < -1 \land Y = -1)$? That is wrong, isn‘t it? (As $X, Y$ are independent the first probability is $\frac12 P(X<1)$ while the second one is $\frac12 P(X<-1)$). What do I miss? $\endgroup$
    – Keba
    Oct 1, 2018 at 22:54
  • $\begingroup$ Additionally, if I just insert the values for $Y$, don‘t I arrive at $\frac12(P(X > -1) + P(X <1))$? $\endgroup$
    – Keba
    Oct 1, 2018 at 22:56
  • $\begingroup$ Sorry, it was to much copy+paste. I have to change a lot in the essence... $\endgroup$
    – dan_fulea
    Oct 2, 2018 at 10:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .