[Math] Stopping time in Gambler’s ruin problem

probabilityprobability theoryrecursionstochastic-processes

2 players A and B start with $a$ and $b$ (both integers) dollars respectively, and they bet against each other 1 dollar each time by tossing a fair coin.

Let $X_n = x + \sum_{i=1}^{n}\xi_i$ where $\xi_i$ are i.i.d. with $P(\xi_i=1)=p,P(\xi_i=-1)=q=1-p$.
Let $\tau_0 = \inf{\{n:X_n = 0}\}$, $\tau_{1} = \inf{\{n:X_n = x+y}\}$, and $\tau=\tau_0\wedge \tau_{1}$, which are all stopping times w.r.t. the martingale $(X_n)$.

How to find $E[\tau]$？

My initial thought:Let $E_{a}[\tau]$ denote the value $E[\tau]$ when A start with $a$，so I
get the equation $$E_{a}[\tau]＝pE_{a＋1}[\tau]＋qE_{a-1}[\tau]＋1$$
with the initial condition$$E_{0}[\tau]＝E_{a+b}[\tau]＝0$$
But I don't know how to sovle it.

Or maybe are there some other ways to deal with this problem?

Any hint will be appreciated.

Best Answer

This is a version of the so-called "Gambler's Ruin" problem, and it can be solved elegantly with the Optional Stopping Theorem.

  1. Find the probability that player A defeats player B. There are many ways to do this, but my favorite is to use the martingale $M_n = (q/p)^{X_n}$ and apply the OST. (I'm leaving out a considerable amount of detail here because I'm not sure what you're already comfortable with; if you want clarification, let me know.)
  2. Once you have that probability, use the fact that $M'_n = X_n + (q-p)n$ is a martingale and apply the OST again to compute the expected time for the game to end.

Again, this is a sketch of the solution, but if you'd like more details, let me know.

Related Question