I'm trying to show that the expected stopping time of the Gambler's Ruin game is $x(n-x)$, where the gambler starts with \$$x$ and the game stops at \$0 or \$$n$. The probabilities of gaining and losing \$1 at each time step are equal (1/2).
I've set up a recursion $\mathbb{E}(T_k) = \frac12 \mathbb{E}(T_{k-1}) + \frac12 \mathbb{E}(T_{k+1}) + 1$ where $T_k$ is the stopping time when the gambler has \$$k$. The recursion has base cases $\mathbb{E}(T_0) = \mathbb{E}(T_n) = 0$.
I'm not exactly sure how to proceed from here. I tried expanding the recursion even more, but this just leads to a mess of terms, and I'm not seeing the pattern. Any help would be very much appreciated!
Best Answer
Let $u_k = \mathbb{E}\left[T_{k+1}\right] - \mathbb{E}\left[T_{k}\right]$, we have $u_k = u_{k-1} - 2$. The sequence $\left(u_k\right)_{k\in\mathbb{N}}$ is arithmetic : $$ u_k = -2k + u_0. $$
But $u_0 = \mathbb{E}\left[T_{1}\right]$, $u_{n-1} = - \mathbb{E}\left[T_{n-1}\right] = -2(n-1) + \mathbb{E}\left[T_{1}\right]$ and $\mathbb{E}\left[T_{n-1}\right] = \mathbb{E}\left[T_{1}\right]$. So we get $$ u_0 = \mathbb{E}\left[T_{1}\right] = n-1 $$ and finally, $$ \mathbb{E}\left[T_{k+1}\right] = n-1 - 2k + \mathbb{E}\left[T_{k}\right]. $$ Now, \begin{align*} \mathbb{E}\left[T_{x}\right] & = (n-1)x - 2\sum_{k=0}^{x-1}k \\ & = (n-1)x - x(x-1) \\ & = nx - x - x^2 + x \\ & = nx - x^2 \\ & = (n - x)x. \end{align*}