0
$\begingroup$

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)    

enter image description here

$\endgroup$
5
$\begingroup$

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: enter image description here

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.

$\endgroup$
  • $\begingroup$ Thank you. Right, that's the same game as the famous Gambler's ruin problem, but with different objective. I was hoping to find a better modeling of the problem, perhaps using random walks and seeing why the mean (in this case) should be around 25, etc. I guess, the referenced paper might answer those questions. $\endgroup$ – Ehsan M. Kermani Jul 26 '15 at 2:35
  • 1
    $\begingroup$ @Ehsan The mean of the distribution is in fact exactly 25. In the symmetric case (boundaries evenly spaced either side of the start position and constant probability 0.5), it's the square of the number of spaces from the start to the absorbing barrier. $\endgroup$ – Glen_b Jul 26 '15 at 5:34
  • $\begingroup$ Right, that was shown in the paper referenced above. $\endgroup$ – Ehsan M. Kermani Jul 26 '15 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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