Consider a one-player Gambler's Ruin, where a gambler starts with capital $k \in \mathbb{Z}^+$ and play fair games (i.e. in each game, he wins \$$1$ with probability $\frac{1}{2}$, and loses \$$1$ with probability $\frac{1}{2}$) until he goes broke. There is no upper limit to how much the gambler wants to win before he stops (i.e. he stops iff he runs out of money). I want to show that the gambler goes broke eventually almost surely.
In my attempt, I let $S_n$ denote the total capital of the gambler after $n$ games, with $S_0 = k$. It is well known that $S_n^2 – n$ forms a martingale. Let $N := \inf\{n \geq 1 : S_n = 0\}$ be a stopping time, which implies that $S_{N \wedge n}^2 – (N \wedge n)$ also forms a martingale. Therefore:
$$
\mathrm{E}[S_{N \wedge n}^2 – (N \wedge n)] = \mathrm{E}[S_0^2] = k^2 \Rightarrow \mathrm{E}[N \wedge n] = \mathrm{E}[S_{N \wedge n}^2 ] – k^2
$$
I'm not entirely sure how to proceed from here. The hint provided for this question says that I should invoke Martingale Convergence Theorem, but I fail to see how it helps. (Note that $S_n$ itself also form a martingale)
Any help would be appreciated.
Side question: If $X_n$ is an increasing martingale w.r.t. $n$, for a stopping time $N$, can we conclude that $X_{N \wedge n} \leq X_n$?
Best Answer
I might have found a solution that invokes Martingale Convergence Theorem, but I'm unsure if this is indeed correct. I welcome anyone to verify and point out the mistakes in my proof, if any. Here, I use the fact that $S_n$ is a martingale, and observe that it can written recursively as follows: \begin{align*} S_{n+1} = \begin{cases} 0, &\text{if $S_n = 0$} \\ S_n - 1, &\text{if $S_n > 0$, and with probability $\frac{1}{2}$} \\ S_n + 1, &\text{if $S_n > 0$, and with probability $\frac{1}{2}$} \end{cases} \end{align*} We suppose for a contradiction that $S_n$ does not go to $0$ eventually with positive probability. We observe that $S_n$ is non-negative, thus we have $S_n \to S$ for some random variable $S$. Since $S_n$ is never zero, the first case never occurs, so $S_n - 1 \to S$ or $S_n + 1 \to S$ as well. This implies that $S_n \to S + 1$ or $S_n \to S - 1$ with positive probability, which clearly contradicts that $S_n \to S$. Thus, we must have $S_n \to S$ almost surely.