Probabilistic Game Theory

387 Views Asked by At

I would appreciate help on the following problem:

Problem. You just bought a new a card printer which continuously prints cards in red or blue, chosen independently and uniformly at random. You play the following game with your friend: You may unplug the printer once at least $n$ cards have been printed. You then shuffle the cards and reveal the top one. If it is red you win, otherwise your friend wins. Prove that you cannot win with probability larger than $1/2 + o(1)$ for $n\to\infty$.

For clarity: We always see all cards that have been printed, i.e. we know our winning probability when stopping the printer.

I see that a Chernoff Bound can prove that with high probability, there are not more than $\frac{n}{2} + \sqrt[3]{n}$ red cards after printing $n$ cards, and this gives a winning probability of $1/2 + o(1)$ when stopping the printer after the $n$-th card. But how can this be extended to cover other strategies?