Stopping time distribution of a fun and simple game!

Question

A friend of mine asked the following question, which I haven't found a convincing answer for it yet. I'd appreciate any comment in advance.

The game has two players $A$ and $B$, each having $\$5$ initially. At each round a fair coin is tossed. If it comes up head, $B$ has to give $A$ a dollar, and if tail comes up, $A$ has to give a dollar to $B.$ The game continues until one of them runs out of money and the other one wins.

Now the question is

What's the distribution of number of tosses until one wins and game finishes? (stopping time distribution of the game!)

My thoughts:

The following is my simulation of $10,000$ games. I first thought, that follows a Poisson distribution with mean $25,$ but its median, if it was Poisson, would be around $25$ as well (precisely, according to Wikipedia, the median $\nu$ should be $25 - \ln 2 < \nu < 25 + 1/3$) which is not the case here.

Now I wonder what that is?

set.seed(123)
funGame <- function(moneyA, moneyB) {
    N <- 0 # number of games to finish
    results <- c(0)
    while((sum(results) != moneyA) && (sum(results) != -moneyB)) {
        results <- c(results,  sample(c(-1, 1), 1, replace=T))
        N <- N + 1 
    }
    return(N)
}

moneyA <- 5
moneyB <- 5
nsim <- 10000
nres <- c()
for(n in 1:nsim) nres <- c(nres, funGame(moneyA, moneyB))
hist(nres, breaks=25, col='grey', xlab="Finish time",
 main="Histogram of stopping time of a fun game, $5 for each player")
abline(v=median(nres), col='red', lty=2, lwd=2)
abline(v=mean(nres), col='blue', lty=1, lwd=2)
legend("topright", c("median", "mean"), col=c('red', 'blue'),
   lty=c(2,1), lwd=c(2,2))
text(median(nres), 0, toString(median(nres)) , pos = 2)
text(mean(nres), 0, toString(mean(nres)), pos = 4)    

Answer 1

This problem is a version of what is commonly known as the "Gambler's ruin" problem. In this case, both players have an equal amount of input (\$5 each) and the game ends when one player is broke, and the other has \$10. If we let $n$ denote the number of games (coin flips) it takes to reach this point, then the probability of ruin at the $n$th game is given by:

\begin{equation} P(N=n)=\frac{1}{10}2^n\frac{1}{2}^{n}\sum_{v=1}^{9}\cos^{n-1}\left(\frac{\pi v}{10}\right)\sin\left(\frac{\pi v}{10}\right)\sin\left(\frac{\pi v}{2}\right) \end{equation}

Which looks horrible.

A very detailed derivation of the distribution would be quite complicated and technical, so I will not go into it. Here is a paper that works through it quite nicely if you are interested in the nitty gritty.

Below is a simple implementation of the distribution from the link in R, where $a$ is the dollar amount needed to win, $z$ is the starting values, $p$ is the probability of heads (or tails, 0.5 for both in this case).

ruin = function(a,z,p,n){
  q = 1-p
  v = seq(1,a-1)
  u = rep(0,length(n))
  for (k in 1:length(n)){
    u[k] = (1/a)*(2^n[k])*(p^((n[k]-z)/2))*(q^((n[k]+z)/2))*sum(((cos(pi*v/a))^(n[k]-1))*sin(pi*v/a)*sin(pi*z*v/a))
  }
  return (u)
}

Calling this function with ruin(10,5,0.5,n) for a vector of $n$'s then plotting yields:

So, this is not some well behaved function of $n$, notice for example that it will be zero for every even number. This is because, from the starting point of \$5, it is impossible to reach exactly \$0 or \$10 in an even number of steps. Each player can either gain or lose exactly \$1 per game, so that would be like adding an even number to an odd and getting an even number out! Therefore the game must end on an odd number of plays.

The expression above will also be zero for $n=1,2,3,4$, even if a player loses 4 times in a row from start, he cannot be ruined. The first time that the expression above is positive, is then for $n=5$ where $P(N=5)=0.03125$. The only way this can occur is if the player loses 5 times in a row, so the probability can also be derived directly as $0.5^5$.

While the histogram resembles a poisson distribution, the bin sized hides the complexity of the problem.