Gamblers Ruin Problems: Exercises

Introduction

Gamblers ruin is a problem involving a particular discrete time Markov chain. The transition matrix for this Markov chain has a special symmetry, which ensures that it is possible to find the hitting probabilities by solving a homogeneous difference equation. Elsewhere on this site there are exercises that will take you through the process of solving this particular problem. On this page we focus on problems that one can solve by using the solutions that you find when you solve these difference equations with some clever mathematical tricks.

Example problems

Click on the problems to reveal the solution

Problem 1

Consider the symmetric (random) walk of an ant along a line. The ant takes a step either left or right each second, with equal probability, and the size of the step is always one unit. Suppose that there is an absorbing barrier at $x=N$: if the ant reaches this point it stays there forever. There is also a reflecting barrier at $x=0$: if the ant reaches $x=0$ it moves back to $x=1$ at the next step. Let $s_{kj}$ be the probability that the ant, having started from the point $x=k$, visits $x=0$, $j$ times before it stops permanently at $x=N$. We make the convention that if $k=0$ then the starting point counts as one visit. Show that: $$ s_{kj} = { N-k \over N^2 } \left( 1 - {1 \over N} \right)^{j-1} \qquad \qquad j \geq 1, \qquad 0 \leq k \leq N \qquad . $$ Hint: Recall that for the symmetric random walk, $p = q$, with absorbing barriers at $x=0$ and $x=N$, starting at x = k, the probability of finishing at $x = 0$ is $$ p_k = 1 -{k \over N} \quad . $$

Let's think about the first wall that the ant encounters. We know (from the hint) that the probability it encounters the reflecting wall at $x=0$ first is: $$ p_k = 1 -{k \over N} $$ We also know that if it encounters the reflecting wall at $x=0$ it will, on the next step, be deposited at $x=1$. The probability, from $x=1$, that it will then go on and encounter the reflecting wall at $x=0$ again before it encounters the absorbing wall at $x=N$ is: $$ p_1 = 1 -{1 \over N} $$ which is the equation from the hint with $k=1$

Events during the later parts of the ants walk are independent of those that occured during the earlier parts of the walk. We can thus calculate the probability of multiple visits to the reflecting wall by multiplying probabilities of individual events. In other words: $$ P(j\textrm{ visits to reflecting wall} ) = \left( 1 -{k \over N} \right)\left( 1 -{1 \over N} \right)^{j-1} $$ This is the probability of $j$ or more visits to the walk. We want the probability of exactly $j$ visits. The probability of moving to the absorbing wall at $x=N$ after having been reflected by the wall at $x=0$ is given by: $$ (1 -p_1 ) = 1 - \left( 1 - \frac{1}{N} \right) = \frac{1}{N} $$ Hence the probability of {\bf exactly} $j$ vists to the reflecting wall is: $$ s_{kj} = \left( 1 -{k \over N} \right)\left( 1 -{1 \over N} \right)^{j-1} \frac{1}{N} = \left(\frac{N-k}{N^2}\right)\left( 1 -{1 \over N} \right)^{j-1} $$

Problem 2

Consider the simple random walk, with absorbing boundaries at $x=0$ and $x=N$, starting at $x=k$. The probability of a step to the right is $p$, and to the left is $q$. Let $p_k$ be the probability of loss (absorption at $x=0$) and let $d_k$ be the expected value of the duration of the walk. That is $d_{k}$ is the expected number of steps taken before the walk terminates. Let $X$ be the number of steps to the {\em right} before absorption occurs (at either end), and $Y$ be the corresponding number of steps to the {\em left}, during the walk. Then clearly: $d_k = \mathbb{E}(X+Y)$. Hence show that: $$ \mathbb{E}[X] = {1 \over 2}\left\{ d_k -k +N(1-p_k) \right\} \quad . $$

We begin by noting that $d_k = \mathbb{E}(X+Y) = \mathbb{E}(X) + \mathbb{E}(Y)$ by the linearity of expectation function

Now consider $X - Y$:

For walk starting at $k$ and ending at $N$ (win) : $X-Y=N-k$
For walk starting at $k$ and ending at $0$ (loss) : $X-Y=-k$

Lets now consider $\mathbb{E}(X-Y)=\mathbb{E}(X) - \mathbb{E}(Y)$, which is simply: $$ \begin{aligned} \mathbb{E}(X-Y) & = (N-k)p(\textrm{win}) - kp(\textrm{loss}) \\ & = (N-k)(1-p_k) - kp_k \\ & = N(1-p_k) - k + kp_k - kp_k = N(1-p_k) - k \end{aligned} $$ We now have two simultaneous equations: $$ \begin{aligned} \mathbb{E}(X) + \mathbb{E}(Y) & = d_k \\ \mathbb{E}(X) - \mathbb{E}(Y) & = N(1-p_k) - k \end{aligned} $$ Adding these together gives: $$ 2 \mathbb{E}(X) = d_k - k + N(1 - p_k) $$

Gamblers Ruin Problems: Exercises

Introduction

Example problems

Problem 1

Problem 2

Contact Details