Person $A$ and $B$ are going to play a coin toss game. There is an initial score $0$, and whenever a head/tail appears, the score $+1$/$-1$. Repeat the coin toss until one wins, that is, when the score reaches $+2$/$-2$, $A$/$B$ wins the game. There is also an initial stake \$$1$ for the game and person $A$ has the option to double the stake every time before a coin toss. When one person wins the game, the other player needs to pay the amount of dollars on the stake to the winner. The question is: if you are person $A$, what is your strategy and what is your highest expected payoff of the game?
I suspect that the stake should be doubled when you have a score of $0$ or $+1$ but if that is the case, the expectation will be infinity according to my calculation. Also, I ran a computer simulation on $10$ runs of $1000000$ games, but for the $10$ means I get, the mean does not converge to a single value. Could someone enlighten me what is the correct approach?
Best Answer
Let $x$ denote player $A$'s score before a toss.
There are two strategies to consider . . .
First suppose player $A$ doubles only at $x=1$.
Let $W_k$ be the probability that player $A$ wins exactly $2^k$, and let $L_k$ be the probability that player $A$ loses exactly $2^k$.
Starting at $x=0$, let $p$ be the probability of reaching $x=1$ before reaching $x=-2$.
It's easily shown that $p={\large{\frac{2}{3}}}$.
There's no way for $A$ to win exactly $1$, hence $W_0=0$.
For $A$ to lose exactly $1$, the score, starting at $x=0$, must reach $x=-2$ before reaching $x=1$, hence $L_0=1-p={\large{\frac{1}{3}}}$.
For $A$ to win exactly $2$, the score, starting at $x=0$, must reach $x=1$ before reaching $x=-2$, and once reaching $x=1$, the next toss must be $\text{H},\;$hence $W_1=(p)\bigl({\large{\frac{1}{2}}}\bigr)=\bigl({\large{\frac{2}{3}}}\bigr)\bigl({\large{\frac{1}{2}}}\bigr)={\large{\frac{1}{3}}}$.
Considering the $2$-toss sequences $\text{TH},\text{HT},\;$we get the recursion $$ \begin{cases} W_k=\frac{1}{4}W_k+\frac{1}{4}W_{k-1}&\text{for}\;k\ge 2\\[4pt] L_k=\frac{1}{4}L_k+\frac{1}{4}L_{k-1}&\text{for}\;k\ge 1\\ \end{cases} $$ or equivalently, $$ \begin{cases} W_k=\frac{1}{3}W_{k-1}&\text{for}\;k\ge 2\\[4pt] L_k=\frac{1}{3}L_{k-1}&\text{for}\;k\ge 1\\ \end{cases} $$ It follows that $$ \begin{cases} W_0=0\\[4pt] W_k=\left(\frac{1}{3}\right)^k&\text{if}\;k\ge 1\\[4pt] L_k=\left(\frac{1}{3}\right)^{k+1}&\text{if}\;k\ge 0\\ \end{cases} $$ Letting $e$ denote $A$'s expectation using this strategy, we get \begin{align*} e&= \sum_{k=0}^{\infty}\left(W_k\right)\left(2^k\right) - \sum_{k=0}^{\infty}\left(L_k\right)\left(2^k\right)\\[4pt] &= \sum_{k=1}^{\infty}\left({\small{\frac{2}{3}}}\right)^k - \left({\small{\frac{1}{3}}}\right)\sum_{k=0}^{\infty}\left({\small{\frac{2}{3}}}\right)^k\\[4pt] &=2-1\\[4pt] &=1 \end{align*} Next, suppose player $A$ doubles at both $x=0$ and $x=1$.
Using this strategy, let $e$ be player $A$'s expectation.
For sequences of $2n$ tosses where the game ends on toss $2n$, there is a one-to-one correspondence between sequences where $A$ loses, and sequences where $A$ wins, obtained by using the exact same toss sequence except reversing the last two tosses from $\text{TT}$ to $\text{HH}$. Call such sequences conjugates of each other. But for any pair of conjugate sequences, if the losing one loses $2^k$, the winning one wins $2^{k+1}$, hence the conditional expectation, given that the game ends after $2n$ tosses, is positive.
It follows that $e > 0$ (possibly positive infinity).
Suppose $e$ is finite.
Starting at $x=0$, and considering the $2$-toss sequences $\text{TT},\text{TH},\text{HT},\text{HH}$, we get the recursion $$e=\left(\small{\frac{1}{4}}\right)(-2)+\left(\small{\frac{1}{4}}\right)(2e)+\left(\small{\frac{1}{4}}\right)(4e)+\left(\small{\frac{1}{4}}\right)(4)$$ which yields $e=-1$, contrary to $e > 0$.
It follows that $e=+\infty$.
Thus, if the goal is to maximize expectation, then doubling at both $x=0$ and $x=1$ is optimal.
But the conjugate of a big win is a big loss (though only half as much), so this strategy, though it has expectation positive infinity, and offers the potential for huge gains, also risks huge losses.