Recall that with the strategy of timid play in red and black, the gambler makes a small constant bet, say $1, on each game until she stops. Thus, on each game, the gambler's fortune either increases by 1 or decreases by 1, until the fortune reaches either 0 or the target $a$ (which we assume is a positive integer). Thus, the fortune process $\left(\begin{array}{c}X_{0}\\ X_{1}\\ \end{array}\right)$ is a random walk on the fortune space $\{0, 1, , a\}$ with 0 and $a$ as absorbing barriers.

As usual, we are interested in the probability of winning and the expected number of games. The key idea in the analysis is that after each game, the fortune process simply starts over again, but with a different initial value. This is an example of the Markov property, named for Andrei Markov. A separate chapter on Markov Chains explores these random processes in more detail. In particular, this chapter has sections on Birth-Death Chains and Random Walks on Graphs, particular classes of Markov chains that generalize the random processes that we are studying here.

Our analysis based on the Markov property suggests that we treat the initial fortune as a variable. Thus, we will denote the probability that the gambler reaches the target $a$, starting with an initial fortune $x$ by

$$f(x)=(X_{N}=a, X_{0}=x)\text{,\hspace{1em}}x\in \{0, 1, , a\}$$By conditioning on the outcome of the first game, show that $f$ satisfies

- $f(x)=qf(x-1)+pf(x+1)$ for $x\in \{1, 2, , a-1\}$ (the difference equation)
- $f(0)=0$, $f(a)=1$ (the boundary conditions)

The difference equation is linear (in the unknown function $f$), homogeneous (because each term involves the unknown function $f$), and second order (because 2 is the difference between the largest and smallest fortunes in the equation).

Show that the characteristic equation of the difference equation in Exercise 1 is $pr^{2}-r+q=0$, and that the roots are $r=1$ and $r=\frac{q}{p}$.

Show that if $p\neq 1/2$, then the roots are distinct. Show that, in this case, the probability that the gambler reaches her target is

$$f(x)=\frac{\left(\frac{q}{p}\right)^{x}-1}{\left(\frac{q}{p}\right)^{a}-1}\text{,\hspace{1em}}x\in \{0, 1, , a\}$$Show that if $p=1/2$, the characteristic equation has a single root 1 that has multiplicity 2. Show that, in this case, the probability that the gambler reaches her target is simply the ratio of the initial fortune to the target fortune:

$$f(x)=\frac{x}{a}\text{,\hspace{1em}}x\in \{0, 1, , a\}$$Thus, we have the distribution of the final fortune $X_{N}$ in all cases:

$$(X_{N}=0, X_{0}=x)=1-f(x)\text{,\hspace{0.5em}}(X_{N}=a, X_{0}=x)=f(x)\text{,\hspace{1em}}x\in \{0, 1, , a\}$$In the red and black experiment, choose *Timid Play*. Vary the initial fortune, target fortune, and game win probability and note how the probability of winning the game changes. For various values of the parameters, run the experiment 1000 times with an update frequency of 10 and note the apparent convergence of the relative frequency of winning a game to the probability of winning a game.

Show that as a function of $x$, for fixed $p$ and $a$,

- $f(x)$ increases from 0 to 1 as $x$ increases from 0 to $a$.
- $f$ is concave upward if $p\le 1/2$ and concave downward if $p\ge 1/2$. Of course, $f$ is linear if $p=1/2$

Show that $f(x)$ is continuous as a function of $p$, for fixed $x$ and $\mathrm{a.}$ Specifically, use L'Hospital's Rule to show that the expression in Exercise 3 converges to the expression in Exercise 4, as $p\to 1/2$.

Show that for fixed $x$ and $a$, $f(x)$ increases from 0 to 1 as $p$ increases from 0 to 1.

The picture below show the typical shape of the graph of $f$ for $p=0.4$, $p=0.5$, and $p=0.6$,

Now let us consider the expected number of games needed with timid play, when the initial fortune is $x$:

$$g(x)=(N, X_{0}=x)\text{,\hspace{1em}}x\in \{0, 1, , a\}$$By conditioning on the outcome of the first game, show that $g$ satisfies

- $g(x)=qg(x-1)+pg(x+1)+1$ for $x\in \{1, 2, , a-1\}$ (the difference equation)
- $g(0)=0$, $g(a)=0$ (the boundary conditions)

The difference equation in the last exercise is linear, second order, but non-homogeneous (because of the constant term 1 on the right side). The corresponding homogeneous equation is the equation satisfied by the win probability function $f$. Thus, only a little additional work is needed here.

Show that if $p\neq 1/2$, then

$$g(x)=\frac{x}{q-p}-\frac{a}{q-p}f(x)\text{,\hspace{1em}}x\in \{0, 1, , a\}$$where $f$ is the win probability function given in Exercise 3

Show that if $p=1/2$, then

$$g(x)=x(a-x)\text{,\hspace{1em}}x\in \{0, 1, , a\}$$Consider $g$ as a function of the initial fortune $x$, for fixed values of the game win probability $p$ and the target fortune $a$.

- Show that $g$ at first increases and then decreases. Except when $p=1/2$, the value of $x$ where the maximum occurs is rather complicated.
- Show that $g$ is concave downward.

Show that $g(x)$ is continuous as a function of $p$, for fixed $x$ and $\mathrm{a.}$ Specifically, show that the expression in Exercise 10 converges to the expression in Exercise 11, as $p\to 1/2$.

For many parameter settings, the expected number of games is surprisingly large. For example, suppose that $p=1/2$ and the target fortune is 100. If the gambler's initial fortune is 1, then the expected number of games is 99, even though half of the time, the gambler will be ruined on the first game. If the initial fortune is 50, the expected number of games is 2500.

In the red and black experiment, select *Timid Play*. Vary the initial fortune, the target fortune and the game win probability and notice how the expected number of games changes. For various values of the parameters, run the experiment 1000 times with an update frequency of 100. Note the apparent convergence of the sample mean number of games to the expect value.

What happens if the gambler makes constant bets, but with an amount higher than 1? The answer to this question may give insight into what will happen with bold play.

In the red and black game, set the target fortune to 16, the initial fortune to 8, and the win probability to 0.45. Play 10 games with each of the following strategies. Which seems to work best?

- Bet 1 on each game (timid play).
- Bet 2 on each game.
- Bet 4 on each game.
- Bet 8 on each game (bold play).

We will need to embellish our notation to indicate the dependence on the target fortune. Let

$$f(x, a)=(X_{N}=a, X_{0}=x)\text{,\hspace{1em}}x\in \{0, 1, , a\}\text{,\hspace{0.5em}}a\in $$Now fix $p$ and suppose that the target fortune is $2a$ and the initial fortune is $2x$. If the gambler plays timidly (betting $1 each time), then of course, her probability of reaching the target is $f(2x, 2a)$. On the other hand:

Suppose that the gambler bets $2 on each game. Argue that the fortune process $\{\frac{X_{i}}{2}\colon i\in \mathbb{N}\}$ corresponds to timid play with initial fortune $x$ and target fortune $a$ and that therefore the probability that the gambler reaches the target is $f(x, a)$.

Thus, we need to compare the probabilities $f(2x, 2a)$ and $f(x, a)$.

Show that $f(2x, 2a)=f(x, a)\frac{\left(\frac{q}{p}\right)^{x}+1}{\left(\frac{q}{p}\right)^{a}+1}$ for $x\in \{0, 1, , a\}$ and hence

- $f(2x, 2a)< f(x, a)$ if $p< 1/2$
- $f(2x, 2a)=f(x, a)$ if $p=1/2$
- $f(2x, 2a)> f(x, a)$ if $p> 1/2$

Thus, it appears that increasing the bets is a good idea if the games are unfair, a bad idea if the games are favorable, and makes no difference if the games are fair.

What about the expected number of games played? It seems almost obvious that if the bets are increased, the expected number of games played should decrease, but a direct analysis using Exercise 10 is harder than one might hope (try it!), We will use a different method, one that actually gives better results. Specifically, we will have the $1 and $2 gamblers bet on the same underlying sequence of games, so that the two fortune processes are defined on the same sample space. Then we can compare the actual random variables (the number of games played), which in turn leads to a comparison of their expected values. Recall that this general method is referred to as coupling.

Let $X_{n}$ denote the fortune after $n$ games for the gamble making $1 bets (simple timid play). Argue that $2X_{n}-X_{0}$ is the fortune after $n$ games for the gambler making $2 bets (with the same initial fortune, betting on the same sequence of games). Assume again that the initial fortune is $2x$ and the target fortune $2a$ where $0< x< a$. Let $N_{1}$ denotes the number of games played by the $1 gambler, and $N_{2}$ denotes the number of games played by the $2 gambler, Argue that

- If the $1 gambler falls to fortune $x$, the $2 gambler is ruined (fortune 0).
- If the $1 gambler hits fortune $x+a$ the $2 gambler is reaches the target $2a$ .
- The $1 gambler must hit $x$ before hitting 0 and must hit $x+a$ before hitting $2a$.
- $N_{2}< N_{1}$ given $X_{0}=2x$
- $(N_{2}, X_{0}=2x)< (N_{1}, X_{0}=2x)$

Of course, the expected values agree (and are both 0) if $x=0$ or $x=a$. Exercise 18 shows that $N_{2}$ is stochastically smaller than $N_{1}$ when the gamblers are not playing the same sequence of games (so that the random variables are not defined on the same sample space).

Generalize the analysis in this subsection to compare timid play with the strategy of betting $$k$ on each game (let the initial fortune be $kx$ and the target fortune $ka$.

It appears that with unfair games, the larger the bets the better, at least in terms of the probability of reaching the target. Thus, we are naturally led to consider bold play.