Basic Theory

Recall that with the strategy of timid play in the game of red and black, the gambler makes a small constant bet, say $1, on each game until she stops. Thus, on each trial, 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 \((X_0, X_1, \ldots)\) is a random walk on the fortune space \(\{0, 1, \ldots, a\}\) with 0 and \(a\) as absorbing barriers.

As usual, we are interested in the probability of winning and the expected number of trials. The key idea in the analysis is that after each trial, 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. The chapter on Markov processes explores these random processes in more detail. In particular, the sections on birth and death chains and random walks on graphs generalize the random processes that we are studying here.

The Probability of Winning

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) = \P(X_N = a \mid X_0 = x), \quad x \in \{0, 1, \ldots, a\} \] where as usual, \(\bs{X} = (X_0, X_1, \ldots)\) is the sequence of fortunes and \(N = \min\{n \in \N_+: X_n \in \{0, a\}\}\) is the stopping rule.

The difference equation in 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). Recall that linear homogeneous difference equations can be solved by finding the roots of the characteristic equation.

So we have the distribution of the final fortune \(X_N\) in either casse: \[ \P(X_N = 0 \mid X_0 = x) = 1 - f(x), \; \P(X_N = a \mid X_0 = x) = f(x); \quad x \in \{0, 1, \ldots, a\} \]

The Expected Number of Trials

As before, let \(N\) denote the number of trials played, so that \(N = \min\{n \in \N_+: X_n \in \{0, a\}\}\) where \(\bs{X} = (X_0, X_1, \ldots)\) is the sequence of fortunes. Given \(X_0 = x \in \{1, 2, \ldots a - 1\}\), random variable \(N\) takes values in \(\{x, x + 1, \ldots\}\), and of course, \(N = 0\) if \(x = 0\) or \(x = a\). In general, the distribution of \(N\) is quite complicated and highly skewed.

Our interest in this subsection is simpley the expected value of \(N\) as a function of the initial fortune, so let \[ g(x) = \E(N \mid X_0 = x), \quad x \in \{0, 1, \ldots, a\} \]

The difference equation in 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\) in . Thus, only a little additional work is needed to solve the non-homogeneous equation.

When \( p = \frac{1}{2} \), the maximum value of \( g \) is \( \frac{a^2}{4} \) and occurs when \( x = \frac{a}{2} \). When \(p \ne \frac{1}{2}\), the value of \(x\) where the maximum occurs is rather complicated.

For many parameter settings, the expected number of games is surprisingly large. For example, suppose that \(p = \frac{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.

Increasing the Bet

What happens if the gambler makes constant bets, but with an amount higher than 1? The answer to this question gives insight into what will happen with bold play. First we will need to embellish our notation to indicate the dependence on the target fortune. Let \[ f(x, a) = \P(X_N = a \mid X_0 = x), \quad x \in \{0, 1, \ldots, a\}, \; a \in \N_+ \] Now fix \(p\) and suppose that the target fortune is \(2 a\) and the initial fortune is \(2 x\). If the gambler plays timidly (betting $1 each time), then of course, her probability of reaching the target is \(f(2 x, 2 a)\). On the other hand:

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

So 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 the expected value function in 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.

Of course, the expected values agree (and are both 0) if \(x = 0\) or \(x = a\). This result 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).

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