3
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ Just to clarify : Each "tails" adds two more tosses so that Bob can never win. Is this right ? The probability is $1$ that eventually Alice gets the lead, so the probability Alice wins is $1$. $\endgroup$
    – Peter
    Feb 25 at 17:43
  • 1
    $\begingroup$ The expected number of rounds is $\infty$ ! $\endgroup$
    – Peter
    Feb 25 at 17:44
  • $\begingroup$ @Peter, those were my guesses, but I'd like to see the reasoning. (It seems counterintuitive that you have a 100% change of winning, but it will take you, on average, forever.) $\endgroup$
    – mscha
    Feb 25 at 17:55
  • $\begingroup$ However, those are famous results of a random walk. In fact, extremely counterintuitive. $\endgroup$
    – Peter
    Feb 25 at 18:34
  • $\begingroup$ For your follow-up question, if the coin has a probability $p>\frac12$ of tails, then the probability the game goes forever is $(1-p)/p$. Proven here: math.stackexchange.com/questions/153123/… $\endgroup$ Feb 25 at 18:43

2 Answers 2

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thanks, @Mike, that makes sense. $\endgroup$
    – mscha
    Feb 26 at 10:34
  • $\begingroup$ One correction: I think that in the followup, the chance of the game ending is $(1-p)/p$. That way, the results for p near ½ and 1 make sense. $\endgroup$
    – mscha
    Feb 26 at 10:36
  • $\begingroup$ One more correction: in step 1, I think $p_n = 2 / (n+1)$. (In the coin-flipping game described here, Alice has $n-1$ coins and Bob has $2$ coins, at this point.) That doesn't affect rest of the reasoning, of course. $\endgroup$
    – mscha
    Feb 26 at 10:39
  • $\begingroup$ @mscha Ah yes, thank you for the feedback. $\endgroup$ Feb 26 at 15:28
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Well, a non-fair coin changes the situation completely : Bob's risk of a loss quickly decreases with the probability of "tails". If the probability is just $0.51$ , Alice will still win many games, but chances that it never ends are relatively high. $\endgroup$
    – Peter
    Feb 25 at 18:32

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.