Under what conditions the gambler's ruin problem may continue indefinitely?

Question

I'v seen the gambler's ruin problem problem on Ross.A book on probability. My question is that under what conditions on the starting money of A and B will the game continue indefinitely?

In the book it says:

with probability $1$, either A or B will wind up with all of the money; in other words, the probability that the game continues indefinitely with A’s fortune always being between $1$ and $N − 1$ is zero

I can't understand that well.

Answer 1

Let's say they play a very simple game. They both put one money in a pot, then they flip a coin. If heads, $A$ takes the two money in the pot, and if tails, $B$ takes the two money in the pot. The moment one player has zero money (and the other player has all the money) the game cannot continue. This means that if the game is to continue indefinitely, player $A$ (and player $B$) must both, at all times, have between $1$ and $N-1$ money, where $N$ is the total amount of money between player $A$ and player $B$. (That's an inclusive "between", by the way; both $1$ and $N-1$ can occur without the game stopping.)

It is definitely possible for the game to continue indefinitely. For instance, if the coin flips are exactly every other tails and every other heads. However, most of the time that's not how it's going to go.

For instance, say they each have $5$ money. After $5$ coin flips, there is a probability of $\frac1{32}$ that the game has ended. If it has not ended, then there is a probability of (at least) $\frac1{32}$ that it ends in the next five flips. And if it hasn't ended yet, there is a probability of ...

And this way it keeps going. The probability that the game hasn't ended by, say $100$ flips is quite small (rudimentary testing reveals it to be less than $1\%$). The probability that the game lasts longer than $200$ flips is less than a percent of that again. The probability that it keeps going past $1000$ flips is really small.

The probability that the game continues indefinitely is equal to $0$. (That does not mean that it cannot happen.)

The possibilities of the game continuing indefinitely has little to do with the starting money of $A$ and $B$, and a lot more to do with what happens with the coin.

Answer 2

The easiest way to see this is that from any point, if A currently has fortune $k$, the game will end if A wins the next $N-k$ tosses or B wins the next $k$ tosses, so the game ends within $N$ turns with probability at least $p^{N-k}+(1-p)^k$. This probability is bounded below (crudely, since one of $p,1-p$ is at least $1/2$, it is bigger than $2^{-N}$). So the probability the game hasn't ended after the first $N$ tosses is less than $(1-2^{-N})$, the probability it hasn't ended after the first $2N$ tosses is less than $(1-2^{-N})^2$, and so on. These bounds tend to $0$, so the probability of the game lasting forever must be $0$.