Probability of a game never ending

Question

The game rules are simple. You take one fair coin and flip it. You start counting how many times did you get heads and how many times did you get tails. When the number of tails equal the number of heads, the game finishes. What is the probability that the game carries on forever?

Answer 1

The probability is zero, as shown by the following simple argument.

For each $n\in\{0,1,2,\dots\}$, let $X_n$ be the quantity (number of heads) - (number of tails) after $n$ flips. WLOG, assume that the first flip is heads, so $X_1=+1$. We will divide the experiment into several "phases" as follows:

• Phase 1 starts at the beginning, and ends the first time that $X_n$ hits either $0$ or $2$. If it exits via $0$, then the experiment is over. Otherwise, phase $2$ starts.

• Phase $2$ ends the first time that $X_n$ hits either $0$ or $4$.

• Phase $3$ ends the first time that $X_n$ hits either $0$ or $8$.

• Phase $4$ ends the first time that $X_n$ hits either $0$ or $16$.

• $\quad\vdots$

The point is, by symmetry, each phase has a $50\%$ chance to end with $X_n=0$, by symmetry, independently of previous phases. The only way for the number of heads to never equal tails is for the this $50\%$ event to never occur after infinitely many attempts, the probability of which is obviously zero.

To be complete, you need to show each phase is almost surely finite. This is not hard to do. For example, phase $4$ ends if at any point there are $16$ heads in a row, so if you divide all of the flips into disjoint blocks of $16$, there will certainly be a block of $16$ heads.