Expected number of turns till finish

Question

Two players play a game. Player A starts with $n$ stones and player B starts with $m$ stones. In each turn a fair coin is flipped. If head comes up, A gives a stone to B. If tail comes up, B gives a stone to A. The game ends when someone has $0$ stones. What is the expected number of turns till the game ends?

Answer 1

Consider the real number line.

We start from the origin. Every time $A$ gives a stone to $B$, we move one step to the left. Every time $B$ gives a stone to $A$, we move one step to the right. The distance from $-n$ tells us how many stone $A$ still has and the distance from $m$ tells us how many stone $B$ still has.

We stop the process when we either reach $-n$ or $m$.

This is a 1D symmetric random walk.

Let's $v_x$ denotes the number of steps required to reach $-n$ or $m$ if we started from $x$. (We are intereseted in $v_0$)

If we starts from $-n$ or $m$, we require $0$ step. $v_{-n}=0$ and $v_{m}=0.$

Also, we have $$v_x=1+\frac12 v_{x-1}+\frac12 v_{x+1},$$ that is when I move a step, I reach either $x-1$ or $x+1$ with equal probability and it is as if I started from there.

Hence I just need to solve this linear system.

The solution is $v_0=nm$.