First hitting probability to $+1$ of a symmetric random walk if we start at $0$

Question

The following is an interview question taken from Mark Joshi's Quant Job Interview.

Question: Given a fair coin. I gain one on a head and lose one on a tail. I quit when my position is $+1$. What is the probability that the game terminates?

I think it assumes that we start at $0$?

Also, I think this question is related to first hitting probability of a symmetric random walk. But I have no idea how to start at all.

Answer 1

This is a symmetric random walk, which returns to zero infinitely often, hence the game ends with probability 1.

Let $x_k$ be the probability of ending (winning) the game, given that we have $k$ coins.

Assuming that we start with zero coins, we are interested in computing $x_0$.

Now, the following holds for $k\le 0$:

$$x_n = \frac12 x_{n+1} + \frac12 x_{n-1} $$

with $x_1 = 1$ and $x_k >0$ for $k\le 0$.

It's easy to show that $x_k=1$ is the only solution.