Recall that the stopping rule for red and black is to continue playing until the gambler is ruined or her fortune reaches the target fortune
. 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;
will denote the set of fortunes and
will denote the set of valid bets for
.
For example, sometimes (as with timid play) we might want to restrict the fortunes to set of integers
;
other times (as with bold play) we might want to use the interval
as the fortune space. As for the bets, recall that the gambler cannot bet what she does not have and does not bet more than she needs in order to reach the target. Thus, a betting function
must satisfy
Moreover, we always restrict our strategies to those for which the stopping time is
finite.
The success function of a strategy is the probability that the gambler reaches the target
with that strategy, as a function of the initial fortune
. A strategy with success function
is optimal if for any other strategy with success function
, we have
for
Show 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
, in addition to the structure of fortunes and bets.
A Condition for Optimality
Our main theorem, and a sketch of its proof, are given in the following exercise:
A strategy
with success function
is optimal if
Consider the following strategy: if the initial fortune is
,
we pick
and then bet
on the first game; thereafter we follow strategy
. Condition on the outcome of the first game to show that the success function for this new strategy is
.
Thus, the theorem can be restated as follows: If
is optimal with respect to the class of strategies in part (a), then
is optimal over all strategies.
Let
be an arbitrary strategy with success function
. The random variable
can be interpreted as the probability of winning if the gambler's strategy is replaced by strategy
after time
.
Condition on the outcome of game
to show that
.
Use (d) and the optimality condition to show
for
and
.
Use (e) to show that
for
and
Let
denote the stopping time for strategy
. Let
in (f) to show that
for
.
Show that
.
Conclude that
for
.
Favorable Trials with a Minimum Bet
Suppose now that
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
and the set of valid bets for
is
.
Our main result, and a sketch of its proof, are given in the following exercise:
If
,
show that the condition for optimality is equivalent to
Show that the inequality in (d) is equivalent to
.
Show that the inequality in (e) holds for
.
In the red and black game set the target fortune to 16, the initial fortune to 8, and the game win probability to 0.45. Define the strategy of your choice and play 100 games. Compare your relative frequency of wins with the probability of winning with timid play.
Favorable Trials without a Minimum Bet
We will now assume that the house allows arbitrarily small bets and that
,
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
,
and the set of bets for
is
.
Our main result, and a sketch of the proof, are given in the following exercise. The results for timid play will play an important role in the analysis, so we will let
denote the probability of reaching an integer target
, starting at the integer
,
with unit bets.
Show that the optimal success function is
for
.
Fix a rational initial fortune
.
Let
be a positive integer and suppose that, starting at
,
the gambler bets
on each game.
Show the strategy in (a) is equivalent to timid play with target fortune
,
and initial fortune
,
The probability of reaching the target 1 under the strategy in (b) is
.
Show that
as
.
From (d), show that
if
is rational.
From (e) and the fact that
is increasing to show that
for all
Unfair Trials
We will now assume that
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
,
and the set of bets for
is
.
The following exercise gives our main result and a sketch of the proof.
Show that bold play is optimal.
Let
denote the success function for bold play, and let
Show that the optimality condition is in Exercise 2 equivalent to
for
.
Use the continuity of
to show that it suffices to prove the inequality in (b) when
and
are binary rationals.
Show that the inequality in (b) holds when
and
have rank 0:
,
;
,
;
and
,
.
Suppose that the inequality in (b) holds when
and
have rank
or less. For parts (f)-(k) below, suppose that
and
have rank
or less.
Suppose that
.
Show that
.
Suppose that
.
Show that,
.
Suppose that
and that
.
Show that
Suppose that
and that
.
Show that
Suppose that
and that
.
Show that
Suppose that
and that
.
Show that
Use the induction hypothesis in (e) and parts (f)-(k) to finish the proof that bold play is optimal when the trials are unfair.
In the red and black game, set the target fortune to 16, the initial fortune to 8, and the game win probability to 0.45. Define the strategy of your choice and play 100 games. Compare your relative frequency of wins with the probability of winning with bold play.
Other Optimal Strategies in the Sub-Fair Case
Consider again the sub-fair case where
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
Now consider the following strategy, which we will refer to as the second order bold strategy:
With fortune
,
play boldly with the object of reaching
before falling to 0.
With fortune
,
play boldly with the object of reaching 1 without falling below
.
With fortune
,
bet
.
Show that the second order bold strategy has betting function
given by
if
if
if
if
Show that the second order bold strategy is optimal.
Let
denote the success function associated with strategy
.
Suppose that the player starts with fortune
under strategy
.
Note that the player reaches the target 1 if and only if she reaches
.
and then wins the final game.
In the setting of (b), consider the sequence of fortunes until the player reaches 0 or
.
Argue that if we double the fortunes, then we have the fortune sequence under the ordinary bold strategy, starting at
and terminating at either 0 or 1.
From parts (b) and (c) argue that
.
Suppose that the player starts with fortune
under strategy
.
Note that the player reaches the target 1 if and only if she reaches 1 without falling back to
or falls back to
and then wins the final game.
In the setting of (b), consider the sequence of fortunes until the player reaches
or 1. Argue that if we double the fortunes and subtract 1, then we have the fortune sequence under the ordinary bold strategy, starting at
and terminating at either 0 or 1.
Argue from (e) and (f) that
.
Using (d) and (g) and the functional equation for ordinary bold play, conclude that
for all
,
and hence that
.
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. The graph of the betting function is shown below:
Explicitly give the third order betting function and show that the strategy is optimal.
More generally, we can define the
order bold strategy and show that it is optimal as well.
Show that the sequence of bold strategies can be defined recursively from the basic bold strategy
as follows:
if
if
Even more generally, we can define an optimal strategy
in the following way: for each
select
and let
.
The graph below shows a few of the graphs of the bold strategies. For an optimal strategy
, we just need to select, for each
a bet on one of the graphs.