# Probability: What Is The Average Number of Steps? [duplicate]

$A$ and $B$ play a game. $A$ has $n_{A}\geq 0$ dollars and player B has $n_{B}\geq 0$ dollars. A fair coin is tossed. If it is heads, $B$ gives a dollar to $A$. If tails, $A$ gives a dollar to $B$. The game stops when one of the players loses all of his/her money. What is the average number of steps until the end of the game?

(Hint: Let $m_{j}$ be the expected number of steps required, when player $A$ has $j$ dollars and try to set up a recursive equation for $m_{j}$. Find out if the recursive equation is solvable.)

-

## marked as duplicate by joriki, Ross Millikan, Alexander Gruber♦, Amzoti, tomaszMar 8 '13 at 0:15

Following the hint, clearly $m_0=0$ and $m_{n_A+n_B}=0$. But if $m_j>0$, then we play one round and then are in the situation that $A$ has $j+1$ or $j-1$ dollars, each with probability $\frac12$. Hence $m_j=1+\frac12 m_{j-1}+\frac12m_{j+1}$, in other words $$m_{j+1}=2m_j-m_{j-1}-2.$$ If we let $a_j=m_j+j^2$, we find $$a_{j+1}-(j+1)^2=2a_j-2j^2-a_{j-1}+(j-1)^2-2$$ i.e. $$a_{j+1}=2a_j-a_{j-1}.$$ The general solution for this is $a_j=\alpha +\beta j$, hence we find $$m_j=\alpha+\beta j-j^2.$$ From the condary condition $m_0=0$, we find $\alpha=0$ and then from $m_{n_A+n_B}=0$, $$m_j=j(n_A+n_B-j).$$