Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

$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.)

Thank you for your help.

share|improve this question

marked as duplicate by joriki, Ross Millikan, Alexander Gruber, Amzoti, tomasz Mar 8 '13 at 0:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
@joriki: I was looking for that one, and even remembered your name, but didn't find it. –  Ross Millikan Mar 7 '13 at 23:00

1 Answer 1

up vote 1 down vote accepted

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).$$

share|improve this answer
    
Thank you for your answer. –  user4167 Mar 8 '13 at 13:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.