Best of N until you win: what are the odds?

Question

Alice and Bob play a game: heads or tails. Alice always takes heads, Bob tails.

If the coin comes up heads, Alice wins. If it comes up tails, Alice says "best of three" and they play two more times. If it comes up tails another time, Alice says "best of five”, and so on. Bob never does this and takes his loss.

In other words, the game goes on until there have been more heads than tails.

What are the odds that Alice wins the game? Obviously, Bob cannot win. But is there a chance > 0 that the game will take forever?

What is the expected number of rounds that the game goes on until Alice wins?

Edit - followup question:

What if the coin is not fair, and has a change of, say, 0.51, 0.7 or 0.8 to land on tails?

Answer 1

Step 1: The probability of the game never ending is zero.

Let $p_n$ be the probability that Bob is eventually $n$ wins ahead of Alice. In order for this to happen, the random walk of the net number of wins for Bob needs to reach $+n$ before it reaches $-1$. By the famous Gambler's ruin problem, $$p_n=\frac{1}{n+1}$$ Now, let $B_n$ be the event that Bob is eventually ahead by $n$ wins. $$ \begin{align} P(\text{game goes forever}) &=P(\text{game goes forever}\mid \text{$B_n$})P(B_n)+P(\text{game goes forever}\mid B_n^c)P(B_n^c) \\&\le 1\cdot (1/n) + P(\text{game goes forever}\mid B_n^c)\cdot 1 \end{align} $$ I claim that $P(\text{game goes forever}\mid B_n^c)=0$. Indeed, given $B_n^c$, the random walk will never reach $+n$, so the game can only go forever if it stays in the range $\{0,1,2,\dots,n-1\}$ forever. However, during the course of any $n$ steps, there is a probability of at least $(1/2)^n$ that Alice will get $n$ wins a row, implying she wins. By dividing the infinite sequence of flips into disjoint sections of $n$, these occurrences are independent, so it will occur at least once with probability one.

Putting this altogether, the probability of the game going forever is at most $1/(n+1)$ for all $n\ge 2$, so the probability must be zero.

Step 2: The expected length of the game is infinite.

Suppose Bob wins the first game. Let $N$ denote the number of games it takes for Alice to regain the majority. We use the well known fact that $E[N]=\sum_{k=0}^\infty P(N>k)$. When $k$ is even, one way for $P(N>k)$ to occur is for both Bob and Alice to win exactly $k/2$ games in the first $k$ games, in such a way that the net number of wins for Bob stays nonnegative. Such paths are known to be enumerated by the Catalan numbers, so the probability of this occurring is $$ \frac1{k/2+1}\binom{k}{k/2} \cdot 2^{-k}\sim \frac{C}{\sqrt k} $$ We have shown that $E[N]=\sum_{k=0}^\infty P(N>k)\ge \sum_{k=0,\text{ $k$ even}} \frac{C}{\sqrt k}$. This last sum diverges, so $E[N]=\infty$.

---

For your follow-up question, if the coin has a probability $p>\frac12$ of heads, then the probability the game goes forever is $(1-p)/p$. Proven here: Hitting probability of biased random walk on the integer line

Answer 2

Purely experimental, with some scripting, the answer seems to be: Yes, Alice always wins, but the expected number of rounds is ∞.

(For instance, if I try 1,000 times, the highest number of rounds could be 364,551; or 4,132,415; or 1,898,733; with average number of rounds respectively 547.30, 7085.13, and 2352.48.)

For my followup question, however, when the coin is not fair, in Bob's advantage, the game almost never ends – even with odds of 0.51 for Bob.