IBM Research | Ponder This | January 2002 solutions

# Ponder This

## January 2002

<<December January February>>

1) k=174.

Let p(k) be the probability that the house will never go broke,
given that the house starts with k coins.
By convention p(0)=0, and p(k) approaches 1 as k grows to infinity.
These probabilities satisfy the equation:
p(k) = 0.499*p(k-1) + 0.501*p(k+1).
The solution to this equation is p(k)=1-(0.499/0.501)**k.
We compute that p(173)=0.4994... and p(174)=0.5014...

2) The house is most likely to go broke at 11PM, February 19, 2003.
Let k=174, and let q(m) be the probability that the house first goes
broke at bet number k+2m.
Consider paths in 2-space (parameterized by time
and the house's current treasury), starting at (0,k) and moving via steps
of either (+1,+1) or (+1,-1), corresponding to bets which the house
wins or loses, respectively.
Let r(m) be the number of paths from (0,k) to (k+2m-1,1), allowing
intermediate visits to (t,0) for some time t, 0<t<k+2m-1.
Let s(m) be the number of paths from (0,k) to (k+2m-1,1), requiring
an intermediate visit to (t,0).
In order to first go broke at time k+2m, we need to execute a path
among those counted by r(m) (but not among those counted by s(m)),
followed by a step of (+1,-1) corresponding to losing that last euro.
So we have q(m)=((r(m)-s(m))*(0.501**m)*(0.499**(k+m)).
Also r(m)=(k+2m-1)!/(k+m)!(m-1)!.
We can calculate s(m) by the "reflection principle" (see Feller,
An Introduction to Probability Theory and its Applications, volume I):
Make a one-to-one transformation on all paths from (0,k), namely
if a path ever reaches (t,0), reverse all the edges after that point.
The paths counted by s(m) are transformed precisely into those paths
from (0,k) to (k+2m-1,-1), so that s(m)=(k+2m-1)!/(k+m-1)!m!.
Now calculate that
q(m+1)/q(m)=.501*.499*(k+2m+1)*(k+2m)/(k+m+1)*(m+1).
When m=4892 or smaller, q(m+1)/q(m)>1.
When m=4893 or larger, q(m+1)/q(m)<1.
So q(m) is maximized when m=4893. The first bet takes place at
midnight on New Years (time = 1), and k+2m = 9960 = 24*(365+50).

3) Her lifespan (1984-2001) evokes the titles of two futuristic novels,
George Orwell's "Nineteen Eighty-Four" and
Arthur C. Clarke's "2001, a Space Odyssey".

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com