# Probability Coin Toss Game Never Ties in N tosses

### 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.

• Your idea to simplify the problem was good, but I think you could find a more helpful simplification. Have you tried considering simple cases like N = 1, N = 2?
– jtb
Commented Feb 22, 2023 at 21:48
• Another hint: If a tie hasn't happened in a series of N coin-flips, then it did not happen in the subseries of N - 1 coin flips before the final one.
– jtb
Commented Feb 22, 2023 at 21:49
• why can't you just do 1 - P(Tie), also if you want to know how the ordering matters check en.wikipedia.org/wiki/Bernoulli_trial , and its obvious that a tie can't happen when N is odd so don't worry about that
Commented Feb 22, 2023 at 21:51
• @JoshBone I've tried building up to N=6, I've noticed that at each even N, you lose 1/2 the wins where Player 1 has won only by a difference of one toss... not sure where to go with that logic
– Joe
Commented Feb 22, 2023 at 22:00
• @AadiSinha I'm trying to build up the series N, N-2, N-4... etc. but the second term is not easy to construct. $P(Tie_N) = P(T_{N-2}) + [P(T_{\delta1}) + P(T_{\delta2})]$ where $P(T_{\delta1})$ is probability there was a 1-point difference between them and they tied, and the same for $P(T_{\delta2})$ but two point diff.
– Joe
Commented Feb 22, 2023 at 22:27

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

• can you give an example of the bijection in the third paragraph? I'm having trouble understanding that part and I think there's either a small typo in your answer or I am wrong (probably the latter)
– Joe
Commented Feb 24, 2023 at 21:36
• I added an example. I wouldn't be surprised if I made a mistake. Commented Feb 24, 2023 at 22:08