Recall that with the strategy of bold play in red and black, the gambler on each game bets either her entire fortune or the amount needed to reach the target fortune, whichever is smaller. As usual, we are interested in the probability that the player reaches the target and the expected number of trials. The first interesting fact is that only the ratio of the initial fortune to the target fortune matters, quite in contrast to timid play.
Suppose that the gambler plays boldly with initial fortune
and target fortune
. As usual, let
denote the fortune process for the gambler. Argue that for any
,
the random process
is the fortune process for bold play with initial fortune
and target fortune
.
Because of this result, it is convenient to use the target fortune as the monetary unit and to allow irrational, as well as rational, initial fortunes. Thus, the fortune space is
.
Sometimes in our analysis we will ignore the states 0 or 1; clearly there is no harm in this because in these states, the game is over.
Recall that the betting function
is the function that gives the amount bet as a function of the current fortune. Show that
The Probability of Winning
We will denote the probability that the bold gambler reaches the target
a1
starting from the initial fortune
x01
by
Fx.
By Exercise 1, the probability that the bold gambler reaches some other target value
a, starting from
x0a
is
Fxa.
By conditioning on the outcome of the first game, show that
F satisfies the functional equation in part (a) and boundary conditions in part (b):
FxpF2xx012pqF2x1x121
F00, F11
From the prvious exericse, and a little thought, it should be clear that an important role is played by the function
d defined on
01
by
dx2x2x2xx0122x1x121
The function
d is sometimes called the doubling function, mod 1, since
dx
gives the fractional part of
2x.
Note that until the last bet that ends the game (with the player ruined or victorious), the successive fortunes of the player follow iterates of the map
d. Thus, bold play is intimately connected with the dynamical system associated with
d.
Binary Expansions
One of the keys to our analysis is to represent the initial fortune in binary form. The binary expansion of
x01
is
xi1xi2i
where
xi01
for each
i.
This representation is unique except when
x is a binary rational (sometimes also called a dyadic rational), that is, a number of the form
k2n
where
n
and
k132n1;
the positive integer
n is called the rank of
x. For a binary rational
x of rank
n, we will use the standard terminating representation where
xn1
and
xi0
for
in.
Rank can be extended to all numbers in [0, 1) by defining the rank of 0 to be 0 (0 is also considered a binary rational) and by defining the rank of a binary irrational to be
.
We will denote the rank of
x by
rx.
Applied to the binary sequences, the doubling function
d is the shift operator:
Show that
dxixi1
for
x01
Bold play in red and black can be elegantly described by comparing the bits of the inital fortune with the game bits.
Suppose that gambler starts with initial fortune
x01.
Show that the gambler eventually reaches the target 1 if and only if there exists a positive integer
k such that
Ij1xj
for
j12k1
and
Ikxk.
That is, the gambler wins if and only if when the game bit agrees with the corresponding fortune bit for the first time, that bit is 1.
The random variable whose bits are the complements of the fortune bits will play an important role in our analysis. Thus, let
Wi11Ij2j
Note that
W is a well defined random variable taking values in
01.
Suppose that the gambler starts with initial fortune
x01.
Use the result of the previous exercise to show that the gambler reaches the target 1 if and only if
Wx.
From the previous two exercises, it follows that
F is simply the distribution function of
W. In particular,
F is an increasing function, and since
W has a continuous distribution,
F is a continuous function.
Show that the success function
F is the unique continuous solution of the functional equation in Exercise 3.
Use induction on the rank to show that any two solutions must agree at the binary rationals.
Use part (a) and continuity to show that any two continuous solutions must agrre for all
x.
If we introduce a bit more notation, we can give nice expression for
Fx,
and later for the expected number of games
Gx.
Let
p0p
and
p1q1p.
Show that
Fxn1px1pxn1pxn
Show that
F is strictly increasing on
01.
This means that the distribution of
W has support
01;
that is, there are no subintervals of
01
that have positive length, but 0 probability.
In particular, show that
F18p3
F28p2
F38p2p2q
F48p
F58pp2q
F68ppq
F78ppqpq2
Suppose that
p12.
Show that
Fxx
for
x01
in two ways:
Thus, for
p12
(fair trials), the probability that the bold gambler reaches the target fortune
a starting from the initial fortune
x is
xa,
just as it is for the timid gambler. Note also that the random variable
W has the uniform distribution on
01.
When
p12,
the distribution of
W is quite strange. To state the result succinctly, we will indicate the dependence of the of the probability measure
on the parameter
p01.
First we define
Cpx011ni1n1xip as n
Thus,
Cp
is the set of
x01
for which the relative frequency of 0's in the binary expansion is
p.
Show that when
p12,
W does not have a probability density function, even though it has a continuous distribution. The following steps outline a proof by contradiction
Suppose that
W has probability density function
f
Then
pWCpxCpfx.
By the previous exercise,
pWCp1.
But also
xCp112WCp0.
That is,
Cp
has Lebesgue measure 0.
Hence
xCpfx0.
When
p12,
F has derivative 0 at almost every point in
01,
even though it is strictly increasing. The following picture shows the graphs of
F when
p0.5,
p0.4,
and
p0.2.
In the red and black experiment, select Bold Play. Vary the initial fortune, target fortune, and game win probability with the scroll bars and note how the probability of winning the game changes. In particular, note that this probability depends only on
xa.
Now for various values of the parameters, run the experiment 1000 times with an update frequency of 100 and note the apparent convergence of the
relative frequency function to the probability density function.
The Expected Number of Trials
Let
GxNX0x
for
x01,
the expected number of trials starting at
x. For any other target fortune
a0,
the expected number of trials starting at
x0a
is just
Gxa.
By conditioning on the outcome of the first game, show that
G satisfies the following functional equation in (a) and boundary conditions (b):
Gx1pG2xx0121qG2x1x121
G00, G10
Note, interestingly, that the functional equation is not satisfied at
x0
or
x1.
As before, we can give an alternate analysis using the binary representation of an initial fortune
x01.
Suppose that the initial fortune of the gambler is
x01.
Show that
NkIkxkkrx.
If
x is a binary rational then
N takes values in the set
12rx.
Play continues until the game number agrees with the rank of the fortune or a game bit agrees with the corresponding fortune bit, whichever is smaller. In the first case, the penultimate fortune is
12,
the only fortune for which the next game is always final.
If
x is a binary irrational then
N takes values in
.
Play continues until a game bit agrees with a corresponding fortune bit.
We can give an explicit formula for the expected number of trials
Gx
in terms of the binary representation of
x.
Suppose that
x01,
and recall our special notation:
p0p,
p1q.
Show that
Gxn0rx1px1pxn
Note that the
n0
term is 1, since the product is empty.
The sum has a finite number of terms if
x is a binary rational.
The sum has an infinte number of terms if
x is a binary irrational.
Use the result of the last exercise to verify the following values:
G181pp2
G281p
G381ppq
G181
G581qpq
G681q
G781qq2
Suppose that
p12.
Show that
Gx212rx1x is binary rational2x is binary irrational
In the red and black experiment, select Bold Play. Vary
x,
a, and
p with the scroll bars and note how the expected number of trials changes. In particular, note that the mean depends only on the ratio
xa.
For selected values of the parameters, run the experiment 1000 times with an update frequency of 100 and note the apparent convergence of the sample mean to the distribution mean.
For fixed
x, show that
G is continuous as a function of
p.
However, as a function of the initial fortune
x, for fixed
p, the function
G is very irregular.
Show that
G is discontinuous at the binary rationals in
01
and continuous at the binary irrationals.