Probability by Conditioning¶

The theory in this section isn't new. It's the old familiar multiplication rule. We are just going to use it in the context of processes indexed by time, in a method that we are going to call conditioning on early moves.

Winning a Game of Dice¶

Suppose Jo and Bo play the following game. Jo rolls a die, then Bo rolls it, then Jo rolls again, and so on, until the first time one of them gets the face with six spots. That person is the winner.

Question. What is the chance that Jo wins?

Answer. Before you do any calculations, notice that the game isn't symmetric in the two players. Jo has the advantage of going first, and could win on the first roll. So the probability that Jo wins should be greater than half.

To see exactly what it is, notice that there's a natural recursion or "renewal" in the setup. For Jo to win, we can condition on the first two moves as follows:

• either Jo wins on Roll 1;
• or Jo gets a non-six on Roll 1, then Bo gets a non-six on Roll 2, and then the game starts over and Jo wins.

So if $x$ is the chance that Jo is the winner, then $x$ satisfies an equation:

$$ x = \frac{1}{6} + \big{(}\frac{5}{6}\big{)}^2 x $$

This is easy to solve.

$$ \frac{11}{36}x = \frac{6}{36} ~~~~ \text{and so } ~~~~ x = \frac{6}{11} $$

which is greater than half as we had guessed.

Gambler's Ruin: Fair Coin¶

Let $a < b$ be two positive integers. Suppose a gambler starts with $\$a$ and bets on the tosses of a coin. Every time the coin lands heads, the gambler wins a dollar. Every time it lands tails, the gambler loses a dollar.

Now suppose the gambler has a stopping rule: he will stop once his fortune gets to $\$b$ or to $\$0$, whichever happens first. If the gambler ends up stopping at $\$0$, he is ruined. Our goal in this example is to find the probability of ruin.

It's a good idea to start visualizing the random trajectory of the gambler's fortune as a path. Here are two graphs that assume $a = 3$ and $b = 10$. The first graph shows a path that leads to the gambler reaching $\$10$. The second shows a path to ruin.

Question. What is the probability that the gambler is ruined?

Answer. Let's start by setting up some notation. For $0 \le k \le b$, Let $p_k$ be the chance that the gambler is ruined given that he starts with $\$k$. Then the answer that we want is $p_a$. By *conditioning on the first move*, we can see that $p_k$ satisfies an equation:

$$ p_k = \frac{1}{2}p_{k-1} + \frac{1}{2}p_{k+1}, ~~~~ 1 \le k \le b-1 $$

with the "edge cases" defined as

$$ p_0 = 1 ~~~~~ \text{and} ~~~~~ p_b = 0 $$

Write the left hand side of the equation as $\frac{1}{2}p_k + \frac{1}{2}p_k$ and rearrange it to see that

$$ p_k - p_{k-1} = p_{k+1} - p_k $$

The successive differences are equal, which means that $p_k$ is a linear function of $k$.

Here is the line assuming $a= \$3$ and $b = \$10$ as before. The red lines show that $p_3 = 0.7$.

For general $a$ and $b$, the line starts at $(0, 1)$ and has slope $-1/b$. So the chance of ruin, starting with $\$a$, is

$$ p_a = \frac{b-a}{b} $$

This makes sense. For fixed $b$, the bigger $a$ is, the closer the gambler's starting fortune is to $\$b$ and hence the smaller his chance of ending in ruin. And correspondingly, the higher his chance of ending up with $\$b$:

$$ 1 - p_a = \frac{a}{b} $$

Gambler's Ruin: Unfair Coin¶

If the gambler bets on tosses of a coin that lands heads with $p \ne 1/2$, then the equations become

$$ p_k = q\cdot p_{k-1} + p\cdot p_{k+1}, ~~~~ 1 \le k \le b-1 $$

where $q = 1-p$, and the edge cases are

$$ p_0 = 1 ~~~~~ \text{and} ~~~~~ p_b = 0 $$

as before. Now the rearrangement is

$$ q(p_k - p_{k-1}) = p(p_{k+1} - p_k) $$

which means that the ratio of the successive differences is constant and equal to $r = \frac{q}{p}$. So the probabilities $p_k$ are the sums of the terms in a geometric progression with common ratio $r$. You can check that this works out to

$$ p_k = \frac{r^k - r^b}{1 - r^b}, ~~~~~ 0 \le k \le b $$

Note that if $p < 1/2$ then $r > 1$ and both the numerator and denominator are negative.

Here is a graph of the probabilities, for $a = 3$ and $b = 10$ as before, but now with a coin that is biased towards heads with $p = 0.6$. Not surprisingly, as the initial fortune increases the probability of ruin falls more sharply for this coin than for the fair coin. Even when the gambler starts with only $\$3$, his chance of ruin is less than 30%.