How Long Will It Last?


How Long Will It Last?, problem

Solution 1

Let's denote $K=m+n.$ There are two ways the game may end: it's either you or me. Conditioned on me being the winner, let $L(x),$ $0\le x\le K,$ be the expected length of the game if I have $x$ coins. There is an obvious recurrence relation

$\displaystyle L(x)=\frac{1}{2}L(x-1)+\frac{1}{2}L(x+1)+1,$

as I can win or lose a coin with the same probability of $\displaystyle \frac{1}{2}.$ $1$ is added to account for the present toss.

Thus we have a non-homogeneous difference equation of order two:


The characteristic polynomial of the homogeneous equation has a double root $1$ such that the general solution of the non-homogeneous equation is a quadratic polynomial, say $L(x)=u+vx+wx^2.$ Substituting that into the recurrence yields $2w=-2,$ so that $\displaystyle w=-1.$

For the boundary conditions, we have two: $L(0)=0$ and $L(K)=0.$ From the first one $u=0$ and from the second $\displaystyle v=K.$ Thus the solution is $\displaystyle L(x)=x(K-x).$ If I start with $n$ coins, $\displaystyle L(n)=n(K-n)=mn.$

Perhaps curiously, the expectation is symmetric in $n$ and $m.$

Solution 2

Let $E(n,m)$ be the expected length of the game in case I start $n$ and you with $m$ coins. On a toss, we'll move to either $E(n-1,m+1)$ or $E(n+1,m-1),$ both with the probability of $\displaystyle \frac{1}{2}$ which leads to a recurrence relation

$\displaystyle E(n,m)=1+\frac{1}{2}E(n-1,m+1)+\frac{1}{2}E(n+1,m-1),$

$1$ indicating the first toss. Of course this assumes $n,m\gt 0.$ The boundary conditions are $E(0,m)=0$ and $E(n,0)=0.$

If we view $E(n,m)$ as the function of one variable, say, $n$ along the line $m+n=const,$ then the formula says that the second difference is a constant $(-2),$ and so $E(n,m)$ is a quadratic function. Vanishing it at the endpoints forces this to be $cmn,$ and direct evaluation shows that $c=1,$ implying $E(n,m)=mn.$


This is problem 98 from D. Newman's A Problem Seminar (Springer-Verlag, 1982). Solution 2 is an adaptation of the one from the book.


|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny