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?
It turns out that the optimal strategy is to stop at the $n$-th card if there are more reds than blues, and if not, stop the first time thereafter that there are more reds than blues (which will eventually happen with probability $1$). The proof is not very difficult.
The expectation value, as a function of $n$, is then
$$\frac{E\left<|S_n|\right>}{2n} + \sum_{k>n} \frac{P_n(k)}{k}$$
where $S_n$ is a random variate representing the position of a balanced random walk at time $n$ and $P_n(k)$ is the probability that the first positive value of a random walk after time $n$ will occur at time $k$, given that $S_n \leq 0$ for that walk.
The first expectation is easily expressed analytically, as is $P_n(k)$. So one has to work with that sum and see if you can bound it by some expression which will turn out to be of the form $Cn^{-\frac12}$. This wll give a stronger result than the problem asks for.