Probability Coin Toss Game Never Ties in N tosses

Question

Question

This question is a rewording of the Matching Pennies problem (Question 23) in Frederick Mosteller's "Fifty Challenging Problems in Probability". Here is my rewording:

Suppose to people play a game where they toss a coin N times. If it is a Heads, then Player A gets one point, if it's a Tails, then Player B gets a point.

What is the probability that in a series of N turns, there is never a tie?

---

Partial Work

There are a few things to do to simplify the problem:

1 - The probability that Player A wins without there ever being a tie, call it $P(W_{AN})$ is the same as probability that Player B wins without there ever being a tie, $P(W_{BN})$. A heads is equally as likely as a tails. So we can just focus on $P(W_{AN})$, and double it.

2 - If $N$ is even, then adding a new toss does not change the probability. Why? If we were tied at $N$, then $P(W_{A(N+1)})$ remains the same as $P(W_{AN})$. If we were not tied, then Player 1 must be ahead by at least two tosses (because it's even), so adding one more toss doesn't change the outcome.

---

Where I'm Stuck

This leaves us with finding the formula for $P(W_{AN})$ when N is odd... I can't quite wrap my head around how to think about this. The solution mentions some very tersely explained answer about binomial coefficients. But the thing is... It's not as simple as that.

I tried to step back and think: If Player A wins in N tosses with no ties, then number of wins for Player A must be at least (N/2 + 0.5), in order to make it simpler, I'll use the solutions notation and work with "small n", where: $n = \frac{N}{2}+\frac{1}{2}$ or: $N = 2n-1$.

Now we just need to know $P(W_{AN})$ given Player A got $x \in [n, N]$ tosses.

The problem of course here, is that the ordering of the tosses matters. And this is where I'm stuck.

---

Solving a different problem to help

Let's say I'm answering the simpler question: What is the probability in N tosses, that we get at least N/2 heads? This is equivalent to winning in the question above, but we ignore ordering.

For 5 Tosses for example, the probability that Player A wins, using the above, in combination with binomial distribution pmf is:

$$ P(W_{A5}) = {5\choose5} \frac{1}{2}^5 + {5\choose4} \frac{1}{2}^5 + {5\choose3} \frac{1}{2}^5 = \frac{1}{2}^5 \times \left[\ {5\choose5} + {5\choose4} + {5\choose3} \ \right] $$

So I'm lost as to how to connect the two... clearly ordering matters.. but how?

---

Any help on how to solve this logically would be appreciated.

I've seen a lot of answers referencing math theorems like Catalan Numbers and such, but I don't know what those are and it seems unlikely that this question depended on that knowledge given the solution.

Answer 1

Lemma: For any natural number $n$, the number of sequences of length $n$ where each entry is either $A$ or $B$, and each initial segment has at least as many $A$'s as $B$'s, is equal to $\binom{n}{\lfloor n/2\rfloor}$.

One proof is given in Marc van Leeuwen's answer. Here is a different proof, using the reflection principle.

First, we count the number of such sequences that have exactly $k$ instances of $B$, for each $k\in \{0,1,\dots,\lfloor n/2\rfloor\}$. There are $\binom{n}k$ sequences total that have $k$ copies of $B$ and $n-k$ copies of $A$, so we just need to subtract the number of "bad" sequences for which some initial segment has more $B$'s then $A$'s.

Given a bad sequence, $s$, define the a reflected sequence $s^*$ as follows. Find the shortest initial segment of $s$ that has more $B$'s than $A$'s, and then replace every symbol after this initial segment with its opposite. While $s$ has $k$ copies of $B$ and $n-k$ copies of $A$, the reflected sequence $s^*$ will have $k-1$ copies of $A$ and $n-k+1$ copies of $B$. Furthermore, the reflection operation is a actually a bijection from the set of bad sequences to the set of all sequences with $k-1$ $A$'s and $n-k+1$ $B$'s. The inverse mapping, given a sequence $s$ with $(k-1)$ $A$'s and the $n-k+1$ $B$'s, is to invert all entries after the first initial segment with more $B$'s than $A$'s.

This bijection proves that the total number of bad sequences is equal to $\binom{n}{k-1}$, so the number of good sequences with $k$ $B$'s is $\binom{n}k-\binom{n}{k-1}$. To get the total number of good sequences, we sum over $k$. Fortunately, the sum is telescoping, so it is easy to compute: $$ \text{# of good sequences}=\sum_{k=0}^{\lfloor n/2\rfloor}\left[\binom nk-\binom n{k-1}\right]=\binom{n}{\lfloor n/2\rfloor}-\binom{n}{-1}=\binom{n}{\lfloor n/2\rfloor}, $$ as claimed.

---

Once we have the lemma, your problem is a corollary. There are two ways to avoid a tie; either $A$ wins the first game, and the remaining sequence has at least as many $A$'s as $B$'s in each initial segment, or $B$ wins the game and the remaining sequence has at least as many $B$'s as $A$'s in each initial segment. From the Lemma, we know that the number of ways this can happen is $$ 2\cdot \binom{N-1}{\lfloor (N-1)/2\rfloor } $$ To get the probability, multiply the above by $2^{-N}$.

---

Here is an illustration of the bijection when $n=6$ and $k=3$. In the left column, there is the complete list of bad sequences of length $n$ with $k$ $B$'s. On the right, there is the complete list of all sequences of length $n$ with $(k-1)$ copies of $A$. The shortest initial segment with more $B$'s than $A$'s is enclosed in parentheses. Note how the initial segment is the same for the input and output, which implies that doing the same operation to the output will return the original input.

 (B)BBAAA  --> (B)AABBB
 (B)BABAA  --> (B)ABABB
 (B)BAABA  --> (B)ABBAB
 (B)BAAAB  --> (B)ABBBA
 (B)ABBAA  --> (B)BAABB
 (B)ABABA  --> (B)BABAB
 (B)ABAAB  --> (B)BABBA
 (B)AABBA  --> (B)BBAAB
 (B)AABAB  --> (B)BBABA
 (B)AAABB  --> (B)BBBAA
 (ABB)BAA  --> (ABB)ABB
 (ABB)ABA  --> (ABB)BAB
 (ABB)AAB  --> (ABB)BBA
 (ABABB)A  --> (ABABB)B
 (AABBB)A  --> (AABBB)B