Show that ET is finite in Gambler’s ruin

martingalesprobability theory

I am looking at the simplest application of optional stopping, the Gambler's ruin problem. In particular, in order to apply OST, we need to check that the martingale $X_n$ has bounded increments (this is easy to check for Gambler's ruin) and also $ET<\infty$. But I am not sure how to prove this. I found the this lecture slides online where on page 15 it says we don't need to check $ET<\infty$ but it suffices to know that $EX_{n\wedge T}<\infty$. Well, this makes sense but now we are applying the OST to a different martingale $X_{n\wedge T}$ rather than the original $X_n$. I wonder if there is a direct way to prove that $ET<\infty$?

Best Answer

You have not defined $T$, and this matters. Nor have you defined your Gambler's Ruin problem, but slides 4 and 14 suggest starting from $K$ and at each round you win $1$ with probability $\frac12$ and otherwise you lose $1$.

If you had defined $T$ as the first time you are ahead, as in slides 20 and 21 of your line, or if you had defined it as the first time after the start that you hit $K$, i.e. breaking even, then in either of those cases you would have $\mathbb E[T]=\infty$, even though in both cases you have $\mathbb P(T <\infty)=1$.

But slides 5 and 14 suggests that $T$ is the first time you hit $N$ or $0$ starting from $K$ with $0 < K < N$. Try this argument:

  • You will hit at least one of $N$ or $0$ before you get $N$ consecutive wins, since in that case you must either start at $0$ or below, or end above $N$
  • The probability of $N$ consecutive wins starting at a particular point is $\frac1{2^N}$
  • The expected time until you get $N$ consecutive wins is then less than or equal to $N 2^N$, because you can bound this by: making $N$ attempts, seeing if you won all of them, and if not trying again
  • So for this $T$ you have $\mathbb E[T] \lt N2^N \lt \infty$

In fact $E[T]$ is much less than this and is in fact $K(N-K)$: for example if $N=5$ and $K=2$ then $E[T]=6$ rather than $160$.

Related Question