Coin Tossing Game: Head/Tail Difference

Question

Consider this experiment:

A coin is tossed and the outcome of the toss recorded. If the outcome is heads the toss is given a score of $1$. If the outcome is tails the toss is given a score of $-1$. The coin is then tossed again and scores given in the same way, until the cumulative score of each toss gets back to $0$.

My questions are:

1. Is this game guaranteed to finish in a finite number of tosses (i.e. can it go on forever with the cumulative score never reaching $0$)
2. What is the expected length of the game?

So far I can see that each coin toss is an independent Bernoulli trial but the cumulative score after $k$ tosses depends on the cumulative score after $k-1$ tosses. I can't think of any distribution that could model the random variable of the cumulative score so could anyone give me some pointers about how to solve this problem?

Thanks!

Answer 1

In answer to the first question, the game could technically go on "forever". No matter how many times (n) you flip the coin, there will be a $\frac{1}{2^n}$ chance of getting all heads or all tails as long as the coin is flipped a countable number of times. Thus you would have a score of $\pm n$ and not zero. However, as the comments have pointed out, if you really flip the coin a truly infinite number of times, then you must eventually get a score of 0.
As for the second question, I'm not sure. It would have to be an even number of turns so that the number of heads would equal the number of tales, but as the game goes on, you get less and less likely to "win". Flipping two coins gives a 50% chance of winning (HeadsTails or TailsHeads), but flipping four coins only gives a 37.5% chance (HHTT, HTHT, THHT, HTTH, THTH, TTHH). The chance of taking four turns to win is even less because in 4 out of those 6 scenarios you would have already won on the first turn. I would say the most common game length would be two turns, but the average game length would be closer to 6 or 8 turns.

Answer 2

The game can take an arbitrarily long time—and on average, it does take an arbitrarily long time.

First, the game can go on arbitrarily long: if you flip a coin $n$ times, you may get $n$ heads in a row. As a result, the game can last longer than any number $n$ of turns.

Next, the expected length of the game is also infinite. To see this, let $x$ be the expected length of the game assuming the first throw is heads. Evidently, $x$ is also the expected length of the game assuming the first throw is tails, and it's also the expected length of the game overall.

We can get a formula for $x$ as follows. To play the game, you flip the coin once and get, say, heads. Now your score is +1. You flip the coin a second time. Either you get tails and win immediately (probability 1/2), or (probability 1/2) you get heads, your score goes up, and you must keep flipping coins until it gets back down to +1 again. The expected time it takes to get back to +1 starting from +1 is, of course, $x$.

Once you've returned to the score +1, you flip the coin again. You either get tails and win (probability 1/2), or your score goes up again, and you must keep flipping coins until it gets back down to +1 again, and ....

In formulas, the expected length of the game is:

$$x = \underbrace{1}_{\text{move right}} + \underbrace{\frac{1}{2}(1)}_{\text{move left and win}} + \frac{1}{2}\left( \underbrace{x}_{\text{loop from +1 to +1}} + \frac{1}{2}\left[\underbrace{1}_{\text{left and win}} + x + \frac{1}{2}(\ldots)\right]\right)$$

$$x = 1 + \frac{1}{2}\left(1 + x + \frac{1}{2}\left[1+x+\frac{1}{2}\left(1 + x + \ldots\right)\right]\right)$$

If we add $x$ to both sides, divide by two, and add one, we find that

$$1+x\; =\; 1 + \frac{1}{2}\left(1 + x + \frac{1}{2}\left[1+x+\frac{1}{2}\left(1 + x + \ldots\right)\right]\right) \qquad = x$$

so $x = x+1$. This problem occurs because the expected length is infinite— it exceeds all finite bounds.

---

We can see this result another way. The expected length of the game is:

$$x = \sum_{\text{winning sequence}} P(\text{sequence})\times\text{length}(\text{sequence})$$

Of course, a winning sequence of throws is any sequence of heads and tails with the same number of heads and tails. If $n$ is the number of heads in such a sequence, the length of the sequence is $2n$ and the probability of the sequence is $\frac{1}{2^{2n}}$. Also there are ${2n \choose n}$ winning sequences containing $n$ heads.

Hence

$$x = \sum_{n=1}^\infty {2n \choose n }\frac{1}{2^{2n}} \times 2n$$

which diverges to infinity.