A coin tossing game which leads to a contradiction

Question

The question is:

Person $A$ and $B$ are going to play a coin tossing game. There is an initial score $0$, and whenever a head/tail appears, the score $+1$/$-1$. Repeating the coin tossing 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?

My idea is as follows:

We first denote the initial stake as $S$ ($S>0$), and denote the expected payoff $A$ can get when using some non-random strategy $g$ as $\mathop{\mathbb{E}}_g(S)$. Then no matter what the strategy $g$ is, we always have that

$$\mathop{\mathbb{E}}_g(S)=\frac{1}{2^{x_1}}\times (2^{y_1}\times (-1)^{z_1} \times S) + \frac{1}{2^{x_2}}\times (2^{y_2}\times (-1)^{z_2}\times S) + \dots = k_gS$$

where $x_i$ stands for some possible path leading to $A$'s winning or losing, $y_i$ stands for the possible stake-doubling actions, and $z_i$ stands for $A$'s winning or losing.

We denote the best strategy $A$ can use as $G$, and we have $\mathop{\mathbb{E}}_G(S)=k_GS$. It must hold that $k_G\ge0$ because if $A$ never doubles the stake, $A$'s expected payoff is $0$. Therefore under the best strategy, the payoff must be not less than $0$.

Now I claim that $A$ should always double the stake when the score reaches $+1$. The reason is that when you double the stake when your stake is $S'$ and the score is $+1$, you can earn an extra money of

$$\frac{1}{2} S'+\frac{1}{2}\mathop{\mathbb{E}}_{G'}(2S')-\frac{1}{2}\mathop{\mathbb{E}}_{G'}(S')=\frac{1}{2}S'+\frac{1}{2}k_{G'}S>0$$

And I also claim that $A$ should double the stake when the score reaches $0$. The reason is that since $A$'s expected payoff is $k_GS$ and $k_G\ge0$, if in strategy $G$, $A$ doesn't double the stake on score $0$, then after we double the stake on $0$, our expected payoff becomes $2k_GS\ge k_GS$, and thus we can at least break even comparing to not doubling the stake on $0$.

But the strange thing is, no matter we double the stake on $-1$ or not, there always remains a contradiction as follows:

Case $1$ is that we don't double the stake on $-1$. Then we can list an equation:

$$\mathop{\mathbb{E}}_G(S)=\frac{1}{4}\times 4S + \frac{1}{4}\mathop{\mathbb{E}}_G(4S)+\frac{1}{4}\mathop{\mathbb{E}}_G(2S)-\frac{1}{4}\times 2S$$

and if we substitute $\mathop{\mathbb{E}}_G(S)=k_GS$ into the equation, we can get that $k_G=-1$, which contradicts with $k_G\ge 0$.

Case $2$ is that we double the stake on $-1$. This indicates that

$$\frac{1}{2}\mathop{\mathbb{E}}_G(2S)-\frac{1}{2}\mathop{\mathbb{E}}_G(S)-\frac{1}{2}S\ge 0$$

(this is the expected extra payoff we can get when we double the stake on $-1$, and this should be $\ge0$ otherwise we won't double the stake on $-1$), which leads to $k_G\ge 1$. But when we list the similar equation as case $1$:

$$\mathop{\mathbb{E}}_G(S)=\frac{1}{4}\times 4S + \frac{1}{4}\mathop{\mathbb{E}}_G(4S)+\frac{1}{4}\mathop{\mathbb{E}}_G(4S)-\frac{1}{4}\times 4S$$

and substitute $\mathop{\mathbb{E}}_G(S)=k_GS$ into the equation, we can get that $k_G=0$, which contradicts with $k_G\ge 1$.

What's wrong with my reasoning and what's your thought to the original question? Thanks!

UPDATE:

Thanks to all the users' answers, and I think the contradiction comes from the fact that under some strategies, the expected payoff doesn't exist. Thus I cannot write $\mathbb{E}_g(S)=k_gS$ in the first place for all strategies. And a strategy without a existent expectation should not be considered as a "good" strategy (not to mention the optimal one) because it cannot ensure you a positive expected payoff. However, I have thought of a new strategy that can result in arbitrarily large expected payoffs: double on all $+1$'s, double on the first $k$ $0$'s, and never double on $-1$'s. First we calculate the probability that you end in $+2$ after $2j$ coin tosses: $$\sum_{i=0}^{j-1}{j-1\choose i}\times \frac{1}{2^{2j}} = \frac{1}{2^{j+1}}$$ and the expected payoff if you double on all $+1$'s and $0$'s and ends in $+2$ after $2j$ steps: $$\sum_{i=0}^{j-1}{j-1\choose i}\times \frac{1}{2^{2j}}\times 2^{i+1} \times S = \frac{2}{3}\times (\frac{3}{4})^j\times S$$. Similarly when you end in $-2$ it is: $$\sum_{i=0}^{j-1}{j-1\choose i}\times \frac{1}{2^{2j}}\times 2^{i} \times (-S) = \frac{1}{3}\times (\frac{3}{4})^j\times (-S)$$. Thus if you add up these two expectations you can get the expected payoff if you end in $+2/-2$, and it is $$\frac{1}{3}\times (\frac{3}{4})^j\times S$$. Then the expected payoff of my new strategy can be calculated as: $$\sum_{j=1}^{k} \frac{1}{3}\times (\frac{3}{4})^j\times 2^j \times S + \sum_{j=k+1}^{+\infty} \frac{1}{3}\times (\frac{3}{4})^j\times 2^k \times S = (2\times (\frac{3}{2})^k-1)S$$, which can be arbitrarily large if we choose large enough $k$.

Answer 1

Let's call the strategy "always double the stakes" $g_1$ and the strategy "double if score $\ge 0$" $g_2$.

Your reasoning is correct, that every optimal strategy has to double the stake on 1 and at least one optimal strategy doubles on 0 (I believe it should be possible to show that $ \mathbb{E}_G(S)>0$ and therefore every optimal strategy should double on 0).

From this we can conclude, that either $g_1$ or $g_2$ is optimal.

It can be shown by symmetry, that $\mathbb{E}_{g_1}(S)=0$. If we now calculate the "extra payout" for doubling at -1 we see that, $g_1$ can not be the best strategy:

$$\frac{1}{2}\mathbb{E}_{g_1}(2S)-\frac{1}{2}\mathbb{E}_{g_1}(S)-\frac{1}{2}S=-\frac{1}{2}S<0$$

We have now proven, that $g_2$ (your case 1) is the best strategy. But why is the equation you gave contradictory? To answer this let's rewrite the definition of $k_g$ as a series:

$$k_g = \frac{1}{S}\mathbb{E}_{g}(S) = \sum_{i=0}^{\infty}\frac{2^{y_i}×(-1)^{z_i}}{2^{x_i}}$$

There are infinite possible paths. Every path has an length $x_i$, a number of doubling-actions $y_i$ (this is the only number which depends on $g$) and an result $z_i \in \{0,1\}$.

Now my previous claim, that $\mathbb{E}_{g_1}=0$ is easy to verify, because for every path $i$ ending in 2 there is a symmetric path $j$ ending in -2, satisfying the conditions: $$y_i=x_i=x_j=y_j \text{, } z_i=0 \text{, and }z_j=1$$

What about the value of $k_{g_2}$? You have shown, that if the series converges and $k_{g_2}$ is therefore a real number, a contradiction follows. From this we can conclude, that the series diverges. We can show, that the series diverges towards infinity:

Every path ending at 2 must be reached from a score of 1 and the score of 1 can only be reached from a score of 0. Therefore every winning path consists of a random walk ending at 0 and 2 consecutive wins for $A$. Similarly we can show, that every loosing path consists of a random walk ending at 0 and two consecutive losses.

For every winning path $i$ there is a loosing path $j$ consisting of the same random walk to 0, but with two lost coin tosses at the end. We can now derive the following conditions:

$$ x_i=x_j \text{, } y_i=y_j+1 \text{, } z_i=0 \text{, and }z_j=1$$

By pairing up the summands for this corresponding paths and noting, that $2×y_i \ge x_i$ (because we reach a score $\neq -1$ at least every other coin toss), we can simplify the series to:

$$k_g = \sum_{j=0}^{\infty}(\frac{2^{y_j+1}×(-1)^0}{2^{x_j}}+\frac{2^{y_j}×(-1)^{1}}{2^{x_j}})=\sum_{j=0}^{\infty}\frac{2^{y_j}}{2^{x_j}}=\sum_{j=0}^{\infty}2^\frac{y_j}{x_j} \ge \sum_{j=0}^{\infty}2^{0.5}=\infty$$

The expected payout is infinite!

Edit: Henry corrected me by stating, that I can not simply pair up the summands for infinite sums. But the main point of the answer still remains, if we formulate in a way involving only a finite number of possible paths: For any given maximal game length $n$ the expected value for $g_1$ is $0$ and for $g_2$ is positive. The limit of the expected value for $g_2$ with $n \to \infty$ is $\infty$.

Answer 2

If player A never doubles the stake then it is fairly obvious that the expected outcome is $0$. One way of seeing this is to calculate the expected outcome for Player A if Player A wins, which is $+\$1$, and the expected outcome for Player A if Player B wins, which is $-\$1$; the two outcomes are equally likely and cancel each other out.

If player A doubles the stake only when the score reaches $+1$ then the expected outcome for Player A if Player A wins turns out to be $+\$4$, and the expected outcome for Player A if Player B wins $-\$2$; the two outcomes are equally likely so the overall expected outcome for A is $4 \times \frac12 - 2 \times \frac12 = \$1$.

If player A doubles the stake when the score reaches $0$ or $+1$ then the expected outcome for Player A if Player A wins turns out to be $+\infty$, and the expected outcome for Player A if Player B wins $-\infty$, whether or not player A also doubles when the score reaches $-1$. The sequences of alternating tosses like $HTHTHTHTHT\ldots$ keep raising the stakes fast enough to balance the low probability of them occurring. So in these cases there no meaningful expected value of the game since $\infty\times \frac12 -\infty\times \frac12$ is indeterminate

There is a meaningful difference between the player A doubling or not when the score reaches $-1$, if there is a finite limit on the number of tosses. Suppose for example the game is limited to a maximum of $20$ tosses (so a probability of $\frac{1}{1024}$ of no result)

• if player A does not double the stake when the score reaches $-1$, the expected outcome for Player A if Player A wins turns out to be about $+\$226.88$, and the expected outcome for Player A if Player B wins about $-\$113.44$, making the overall expected outcome for Player A about $\$56.665$

• if player A does double the stake when the score reaches $-1$, the expected outcome for Player A if Player A wins turns out to be $+\$2048$, and the expected outcome for Player A if Player B wins $-\$2048$, making the overall expected outcome for Player A zero, as you might expect by symmetry

Answer 3

Let's call the players Alice and Bob.

It always makes sense for Alice to double the bet when the score is $+1$: You can think of the doubling as placing a side bet on the outcome of a "new" game in which Alice has a head start. In other words, Alice should expect no profit, on average, from the initial bet (because Bob has an equal probability of winning it), but can expect a net profit from any side bets she forces Bob to accept when she has the advantage.

Because Alice now has a strategy (double on $+1$) that gives her a positive expected profit, she would like the game to start with as large a stake as possible. Thus anytime the score returns to $0$, Alice should also double the bet.

Should Alice ever double the bet when the score is $-1$? Ask Bob. He would like to see a side bet made on the "new" game in which has the head start. If doubling on $-1$ ever offers Alice an advantage, then it would always offer her an advantage, so she would always double the bet no matter what the score. But this would be like not consulting either Alice or Bob on strategy, at which point the game back to a symmetric draw. So Alice should not double the bet when the score is $-1$.

A mathematical drawback to this optimal strategy (especially from Bob's point of view) is that it results in an expected value (to Alice) of $\infty$. One way to see this is to imagine Alice is only allowed a fixed number of doublings, $n$, when the score is $0$ (but is always allowed to double on $+1$). For $n=0$, the expected value satisfies

$$E_0={1\over4}(2)+{1\over4}(2E_0)+{1\over4}(E_0)-{1\over4}(1)$$

That is, after two coin tosses, Alice either doubles once on $+1$ and then wins the total bet of $2$, or she doubles once $+1$ and then drops back to $0$ with the stakes now doubled, or she drops to $-1$ and then gets back to $0$ with the original bet, or loses her (undoubled) bet of $1$. It's easy to see that this solves to $E_0=1$.

Recursion now says

$$E_n={1\over4}(2)+{1\over4}(4E_{n-1})+{1\over4}(2E_{n-1})-{1\over4}(1)$$

for $n\ge1$, which simplifies to

$$E_n={3\over2}E_{n-1}+{1\over4}$$

and it's now clear that $E_n\to\infty$ as $n\to\infty$. If you like, you can derive the direct formula

$$E_n=\left(3\over2\right)^{n+1}-{1\over2}$$

It might be more interesting to consider Alice's expected value if she is limited to a finite number of doublings altogether (and not just on doublings when the score is $0$), i.e., if the maximum amount that can be wagered in a single game is $2^n$ for some $n\ge0$. Let's let $\mathcal{E}_n^*$ denote the expected value from an optimal strategy. The live question is whether (and when) an optimal strategy has her double on $0$.

It's obvious that $\mathcal{E}_0^*=0$. For $n\gt0$, Alice needs to choose between a strategy $\mathcal{E}_n$, in which she waits for the score to reach $+1$ before her first doubling, and a strategy $\mathcal{E}_n'$, in which she doesn't wait (i.e., doubles if the score returns from $-1$ to $0$). The first possibility satisfies

$$\mathcal{E}_n={1\over4}(2)+{1\over4}(2\mathcal{E}_{n-1}^*)+{1\over4}(\mathcal{E}_n)-{1\over4}(1)$$

which solves to

$$\mathcal{E}_n={2\mathcal{E}_{n-1}^*+1\over3}$$

The second possibility satisfies

$$\mathcal{E}_n'={1\over4}(2)+{1\over4}(2\mathcal{E}_{n-1}^*)+{1\over4}(2\mathcal{E}_{n-1}^*)-{1\over4}(1)=\mathcal{E}_{n-1}^*+{1\over4}$$

The expected value for the optimal strategy is thus

$$\mathcal{E}_n^*=\max\{\mathcal{E}_n,\mathcal{E}_n'\}=\max\left\{{2\over3}\mathcal{E}_{n-1}^*+{1\over3},\mathcal{E}_{n-1}^*+{1\over4} \right\}$$

We get

$$\begin{align} \mathcal{E}_1^*&=\max\left\{{1\over3},{1\over4} \right\}={1\over3}\\ \mathcal{E}_2^*&=\max\left\{{5\over9},{7\over12} \right\}={7\over12}\\ \mathcal{E}_3^*&=\max\left\{{13\over18},{5\over6} \right\}={5\over6} \end{align}$$

etc. It's easy to see that the $\mathcal{E}_n'$ strategy is the best choice for $n\gt1$ and that

$$\mathcal{E}_n^*={1\over3}+{n-1\over4}\quad\text{for }n\ge1$$

In other words, Alice should double on $0$ until she gets down to her last doubling, at which point she should wait for the score to reach $+1$. Note, we still have $\mathcal{E}_n^*\to\infty$ as $n\to\infty$, but at a much slower rate than $E_n$, when the doublings on $+1$ didn't count against her limit.