Recall that the stopping rule for the game of red and black is to continue playing until the gambler is ruined or her fortune reaches the target fortune \(a\). Thus, the gambler's strategy is to decide how much to bet on each game before she must stop. Suppose that we have a class of strategies that correspond to certain valid fortunes and bets; \(A\) will denote the set of fortunes and \(B_x\) will denote the set of valid bets for \(x \in A\). For example, sometimes (as with timid play) we might want to restrict the fortunes to set of integers \(\{0, 1, \ldots, a\}\); other times (as with bold play) we might want to use the interval \([0, 1]\) as the fortune space. As for the bets, recall that the gambler cannot bet what she does not have and will not bet more than she needs in order to reach the target. Thus, a betting function \(S\) must satisfy \[ S(x) \le \min\{x, a - x\}, \quad x \in A \] Moreover, we always restrict our strategies to those for which the stopping time \(N\) is finite.
The success function of a strategy is the probability that the gambler reaches the target \(a\) with that strategy, as a function of the initial fortune \(x\). A strategy with success function \(V\) is optimal if for any other strategy with success function \(U\), we have \(U(x) \le V(x)\) for \(x \in A\).
If there exists an optimal strategy, then the optimal success function is unique.
However, there may not exist an optimal strategy or there may be several optimal strategies. Moreover, the optimality question depends on the value of the game win probability \(p\), in addition to the structure of fortunes and bets.
Our main theorem gives a condition for optimality:
A strategy \(S\) with success function \(V\) is optimal if \[ p V(x + y) + q V(x - y) \le V(x); \quad x \in A, \, y \in B_x \]
Consider the following strategy: if the initial fortune is \(x \in A\), we pick \(y \in A_x\) and then bet \(y\) on the first game; thereafter we follow strategy \(S\). Conditioning on the outcome of the first game, the success function for this new strategy is \[ U(x) = p V(x + y) + q V(x - y) \] Thus, the theorem can be restated as follows: If \(S\) is optimal with respect to the class of strategies just described, then \(S\) is optimal over all strategies. Let \(T\) be an arbitrary strategy with success function \(U\). The random variable \(V(X_n)\) can be interpreted as the probability of winning if the gambler's strategy is replaced by strategy \(S\) after time \(n\). Conditioning on the outcome of game \(n\) gives \[ \E[V(X_n) \mid X_0 = x] = \E[p V(X_{n - 1} + Y_n) + q V(X_{n - 1} - Y_n) \mid X_0 = x] \] Using the the optimality condition gives \[ \E[V(X_n) \mid X_0 = x] \le \E[V(X_{n - 1}) \mid X_0 = x] , \quad n \in \N_+, \; x \in A \] If follows that \(\E[V(X_n) \mid X_0 = x] \le V(x)\) for \(n \in \N_+\) and \(x \in A\). Now let \(N\) denote the stopping time for strategy \(T\). Letting \(n \to \infty\) we have \(\E[V(X_N) \mid X_0 = x] \le V(x)\) for \(x \in A\). But \(\E[V(X_N) \mid X_0 = x] = U(x)\) for \(x \in A\). So \(U(x) \le V(x)\) for \(x \in A\).
Suppose now that \(p \ge \frac{1}{2}\) so that the trials are favorable (or at least not unfair) to the gambler. Next, suppose that all bets must be multiples of a basic unit, which we might as well assume is $1. Of course, real gambling houses have this restriction. Thus the set of valid fortunes is \(A = \{0, 1, \ldots, a\}\) and the set of valid bets for \(x \in A\) is \(B_x = \{0, 1, \ldots, \min\{x, a - x\}\}\). Our main result for this case is
Timid play is an optimal strategy.
Recall the success function \(f\) for timid play and recall the optimality condition in . This condition trivally holds if \(p = \frac{1}{2}\) so that \(f(x) = x / a\) for \(x \in A\). If \(p \gt \frac{1}{2}\), \[f(x) = \frac{1 - (q / p)^x}{1 - (q / p)^a}, \quad x \in A\] so the condition for optimality is equivalent to \[ p \left(\frac{q}{p}\right)^{x + y} + q \left(\frac{q}{p}\right)^{x - y} \ge \left(\frac{q}{p}\right)^x \] But this condition is equivalent to \(p q \left(p^y - q^y\right)\left(p^{y - 1} - q^{y - 1}\right) \le 0\) which clearly holds since \(p \gt \frac{1}{2}\).
We will now assume that the house allows arbitrarily small bets and that \(p \gt \frac{1}{2}\), so that the trials are strictly favorable. In this case it is natural to take the target as the monetary unit so that the set of fortunes is \(A = [0, 1]\), and the set of bets for \(x \in A\) is \(B_x = [0, \min\{x, 1 - x\}]\). Here is our main result.
There is no optimal strategy.
For \(n \in \N_+\), consider the strategy that makes constant bets \(1 / n\) with the following exceptions: if the fortune is \(x \in (0, 1 / n)\), bet \(x\) and if the fortune is \(x \in (1 - 1 / n, 1)\) bet \(1 - x\). With initial fortunes restricted to \(\{k / n: k \in \{0, 1, \ldots, n\}\}\) the strategy is equivalent to timid play (so with unit bets) with target \(n\). Suppose that we start with initial fortune \(k_n / n\) where \(k_n / n \to x \in (0, 1)\) as \(n \to \infty\). In particular, \(k_n \to \infty\) as \(n \to \infty\). Let \(r = q / p\) so that \(r \in (0, 1)\). From the results for timid play, the probability of winning is \[ \frac{1 - r^{k_n}}{1 - r^n} \to 1 \text{ as } n \to \infty\] Thus, we can devise betting strategies that give win functions that are arbitrarily close to 1.
We will now assume that \(p \le \frac{1}{2}\) so that the trials are unfair, or at least not favorable. As before, we will take the target fortune as the basic monetary unit and allow any valid fraction of this unit as a bet. Thus, the set of fortunes is \(A = [0, 1]\), and the set of bets for \(x \in A\) is \(B_x = [0, \min\{x, 1 - x\}]\). Our main result for this case is
Bold play is optimal.
Let \(F\) denote the success function for bold play, and let \[ D(x, y) = F \left(\frac{x + y}{2}\right) - [p F(x) + q F(y)] \] The optimality condition in equivalent to \(D(x, y) \le 0\) for \(0 \le x \le y \le 1\). From the continuity of \(F\), it suffices to prove this inequality when \(x\) and \(y\) are binary rationals. It's simple to see that \(D(x, y) \le 0\) when \(x\) and \(y\) have rank 0: \(x = 0\), \(y = 0\) or \(x = 0\), \(y = 1\) or \(x = 1\), \(y = 1\). Suppose now that \(D(x, y) \le 0\) when \(x\) and \(y\) have rank \(m\) or less. We have the following cases:
The induction hypothesis can now be applied to each case to finish the proof.
Consider again the sub-fair case where \(p \le \frac{1}{2}\) so that the trials are not favorable to the gambler. We will show that bold play is not the only optimal strategy; amazingly, there are infinitely many optimal strategies. Recall first that the bold strategy has betting function \[ S_1(x) = \min\{x, 1 - x\} = \begin{cases} x, & 0 \le x \le \frac{1}{2} \\ 1 - x, & \frac{1}{2} \le x \le 1 \end{cases} \]
Consider the following strategy, which we will refer to as the second order bold strategy:
The second order bold strategy has betting function \(S_2\) given by \[ S_2(x) = \begin{cases} x, & 0 \le x \lt \frac{1}{4} \\ \frac{1}{2} - x, & \frac{1}{4} \le x \lt \frac{1}{2} \\ \frac{1}{2}, & x = \frac{1}{2} \\ x - \frac{1}{2}, & \frac{1}{2} \lt x \le \frac{3}{4} \\ 1 - x, & \frac{3}{4} \lt x \le 1 \end{cases} \]
The second order bold strategy is optimal.
Let \(F_2\) denote the success function associated with strategy \(S_2\). Suppose first that the player starts with fortune \(x \in (0, \frac{1}{2})\) under strategy \(S_2\). Note that the player reaches the target 1 if and only if she reaches \(\frac{1}{2}\) and then wins the final game. Consider the sequence of fortunes until the player reaches 0 or \(\frac{1}{2}\). If we double the fortunes, then we have the fortune sequence under the ordinary bold strategy, starting at \(2 x\) and terminating at either 0 or 1. Thus it follows that \[ F_2(x) = p F(2 x), \quad 0 \lt x \lt \frac{1}{2} \] Suppose next that the player starts with fortune \(x \in (\frac{1}{2}, 1)\) under strategy \(S_2\). Note that the player reaches the target 1 if and only if she reaches 1 without falling back to \(\frac{1}{2}\) or falls back to \(\frac{1}{2}\) and then wins the final game. Consider the sequence of fortunes until the player reaches \(\frac{1}{2}\) or 1. If we double the fortunes and subtract 1, then we have the fortune sequence under the ordinary bold strategy, starting at \(2 x - 1\) and terminating at either 0 or 1. Thus it follows that \[ F_2(x) = F(2 x - 1) + [1 - F(2 x - 2)] p = p + q F(2 x - 1), \quad \frac{1}{2} \lt x \lt 1 \] But now, using the functional equation for ordinary bold play, we have \(F_2(x) = F(x)\) for all \(x \in (0, 1]\), and hence \(S_2\) is optimal.
Once we understand how this construction is done, it's straightforward to define the third order bold strategy and show that it's optimal as well.
Explicitly give the third order betting function and show that the strategy is optimal.
More generally, we can define the \(n\)th order bold strategy and show that it is optimal as well.
The sequence of bold strategies can be defined recursively from the basic bold strategy \(S_1\) as follows: \[ S_{n+1}(x) = \begin{cases} \frac{1}{2} S_n(2 x), & 0 \le x \lt \frac{1}{2} \\ \frac{1}{2}, & x = \frac{1}{2} \\ \frac{1}{2} S_n(2 x - 1), & \frac{1}{2} \lt x \le 1 \end{cases} \] \(S_n\) is optimal for each \(n\).
Even more generally, we can define an optimal strategy \(T\) in the following way: for each \(x \in [0, 1]\) select \(n_x \in \N_+\) and let \(T(x) = S_{n_x}(x)\). The graph below shows a few of the graphs of the bold strategies. For an optimal strategy \(T\), we just need to select, for each \(x\) a bet on one of the graphs.
Let's return to the unscaled formulation of red and black, where the target fortune is \( a \in (0, \infty) \) and the initial fortune is \( x \in (0, a) \). In the subfair case, when \( p \le \frac{1}{2} \), no strategy can do better than the optimal strategies, so that the win probability is bounded by \( x / a \) (with equality when \( p = \frac{1}{2} \)). Another elegant proof of this can be given in terms of martingale inequalities.