Gambler's Ruin
In the last section, the simplest kind of symmetric random walk in [math]{\mathbf R}^1[/math] was studied. In this section, we remove the assumption that the random walk is symmetric. Instead, we assume that [math]p[/math] and [math]q[/math] are non-negative real numbers with [math]p+q = 1[/math], and that the common distribution function of the jumps of the random walk is
One can imagine the random walk as representing a sequence of tosses of a weighted coin, with a head appearing with probability [math]p[/math] and a tail appearing with probability [math]q[/math]. An alternative formulation of this situation is that of a gambler playing a sequence of games against an adversary (sometimes thought of as another person, sometimes called “the house”) where, in each game, the gambler has probability [math]p[/math] of winning.
The Gambler's Ruin Problem
The above formulation of this type of random walk leads to a problem known as the Gambler's Ruin problem. This problem was introduced in Exercise, but we will give the description of the problem again. A gambler starts with a “stake” of size [math]s[/math]. She plays until her capital reaches the value [math]M[/math] or the value 0. In the language of Markov chains, these two values correspond to absorbing states. We are interested in studying the probability of occurrence of each of these two outcomes.
One can also assume that the gambler is playing against an “infinitely rich” adversary. In this
case, we would say that there is only one absorbing state, namely when the gambler's stake is 0.
Under this assumption, one can ask for the probability that the gambler is eventually ruined.
We begin by defining [math]q_k[/math] to be the probability that the gambler's stake reaches 0, i.e.,
she is ruined, before it reaches [math]M[/math], given that the initial stake is [math]k[/math]. We note that [math]q_0 =
1[/math] and [math]q_M = 0[/math]. The fundamental relationship among the [math]q_k[/math]'s is the following:
where [math]1 \le k \le M-1[/math]. This holds because if her stake equals [math]k[/math], and she plays one game, then her stake becomes [math]k+1[/math] with probability [math]p[/math] and [math]k-1[/math] with probability [math]q[/math]. In the first case, the probability of eventual ruin is [math]q_{k+1}[/math] and in the second case, it is [math]q_{k-1}[/math]. We note that since [math]p + q = 1[/math], we can write the above equation as
or
From this equation, it is easy to see that
We now use telescoping sums to obtain an equation in which the only unknown is [math]q_1[/math]:
so
If [math]p \ne q[/math], then the above expression equals
while if [math]p = q = 1/2[/math], then we obtain the equation
For the moment we shall assume that [math]p \ne q[/math]. Then we have
Now, for any [math]z[/math] with [math]1 \le z \le M[/math], we have
Therefore,
Finally, if [math]p = q = 1/2[/math], it is easy to show that (see Exercise)
We note that both of these formulas hold if [math]z = 0[/math].
We define, for [math]0 \le z \le M[/math], the quantity [math]p_z[/math] to be the probability that the gambler's
stake reaches [math]M[/math] without ever having reached 0. Since the game might continue indefinitely, it
is not obvious that [math]p_z + q_z = 1[/math] for all [math]z[/math]. However, one can use the same method as above
to show that if [math]p \ne q[/math], then
and if [math]p = q = 1/2[/math], then
Thus, for all [math]z[/math], it is the case that [math]p_z + q_z = 1[/math], so the game ends with probability 1.
Infinitely Rich Adversaries
We now turn to the problem of finding the probability of eventual ruin if the gambler is playing against an infinitely rich adversary. This probability can be obtained by letting [math]M[/math] go to [math]\infty[/math] in the expression for [math]q_z[/math] calculated above. If [math]q \lt p[/math], then the expression approaches [math](q/p)^z[/math], and if [math]q \gt p[/math], the expression approaches 1. In the case [math]p = q = 1/2[/math], we recall that [math]q_z = 1 - z/M[/math]. Thus, if [math]M \rightarrow \infty[/math], we see that the probability of eventual ruin tends to 1.
Historical Remarks
In 1711, De Moivre, in his book De Mesura Sortis, gave an ingenious derivation of the probability of ruin. The following description of his argument is taken from David.[Notes 1] The notation used is as follows: We imagine that there are two players, A and B, and the probabilities that they win a game are [math]p[/math] and [math]q[/math], respectively. The players start with [math]a[/math] and [math]b[/math] counters, respectively.
Imagine that each player starts with his counters before him in a pile, and that nominal values are assigned to the counters in the following manner. A's bottom counter is given the nominal value [math]q/p[/math]; the next is given the nominal value [math](q/p)^2[/math], and so on until his top counter which has the nominal value [math](q/p)^a[/math]. B's top counter is valued [math](q/p)^{a+1}[/math], and so on downwards until his bottom counter which is valued [math](q/p)^{a+b}[/math]. After each game the loser's top counter is transferred to the top of the winner's pile, and it is always the top counter which is staked for the next game. Then in terms of the nominal values B's stake is always [math]q/p[/math] times A's, so that at every game each player's nominal expectation is nil. This remains true throughout the play; therefore A's chance of winning all B's counters, multiplied by his nominal gain if he does so, must equal B's chance multiplied by B's nominal gain. Thus,
[[math]] \begin{equation} P_a\biggl(\Bigl({q\over p}\Bigr)^{a+1} + \cdots + \Bigl({q\over p}\Bigr)^{a+b}\biggr) = P_b\biggl(\Bigl({q\over p}\Bigr) + \cdots + \Bigl({q\over p}\Bigr)^a\biggr)\ . \label{eq 12.2.1} \end{equation} [[/math]]
Using this equation, together with the fact that
it can easily be shown that
if [math]p \ne q[/math], and
if [math]p = q = 1/2[/math].
In terms of modern probability theory, de Moivre is changing the values of the counters to make
an unfair game into a fair game, which is called a martingale. With the new values, the
expected fortune of player A (that is, the sum of the nominal values of his counters) after each
play equals his fortune before the play (and similarly for player B). (For a simpler martingale argument, see Exercise.) De Moivre then uses the fact that when the game ends,
it is still fair, thus \ref{eq 12.2.1} must be true. This fact requires proof, and is
one of the central theorems in the area of martingale theory.
General references
Doyle, Peter G. (2006). "Grinstead and Snell's Introduction to Probability" (PDF). Retrieved June 6, 2024.