Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 3 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|cite|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.