Answer: Ties in Matching Pennies

Key Idea / Intuition

After the first flip, one player is ahead by 1. For the score to never return to even, the leading player must stay strictly ahead the entire time — this is exactly the ballot problem in disguise. The key insight is a reflection/symmetry argument: sequences that do reach a tie can be paired with sequences that don't in a way that lets us count exactly. Surprisingly, the probability depends only on the binomial coefficient $\binom{2n}{n}$, and it equals the same value for $N = 2n$ and $N = 2n+1$.

---

Formal Proof / Solution

Setup. We have $N = 2n$ flips. After the first flip (say A is ahead), we need A to stay strictly ahead for all $2n - 1$ remaining flips. By symmetry, the probability doesn't depend on who wins the first flip.

Reduction to ballot problem. After flip 1, A leads 1–0. We need: among all $2n - 1$ remaining flips, A never drops to the level of B. This is equivalent to asking: in a sequence of $2n - 1$ coin flips (each ±1), a running sum starting at +1 never hits 0.

Counting via the ballot problem result.

The full $2n$ flips produce a sequence of $\pm 1$ values. Define $S_k$ = cumulative score difference (A minus B) after $k$ flips, with $S_0 = 0$.

The probability that A leads B throughout (i.e., $S_k > 0$ for all $k = 1, \ldots, 2n$) equals, by the ballot problem:

$P(S_k > 0 \text{ for all } k = 1, \ldots, 2n \mid S_{2n} = 2m) = \frac{2m}{2n} = \frac{m}{n}, \quad m \geq 1.$

But we want: after the first flip, never a tie. So we want $S_k \neq 0$ for $k = 2, 3, \ldots, 2n$, given that $S_1 = +1$ (or $-1$, by symmetry — the condition is the same).

Direct computation using Mosteller's formula. The probability of no tie after the first flip, over all $N = 2n$ flips, is:

$P(\text{no tie}) = \frac{\binom{2n}{n}}{2^{2n}} \cdot \frac{1}{1} \quad \text{... let's derive carefully.}$

The $2^{2n}$ equally likely sequences of $n$ heads and $n$ tails... actually let $x$ = number of heads for A in $2n$ flips, $x \sim \text{Binomial}(2n, \tfrac{1}{2})$.

• If $x \neq n$ (no tie possible at end): by the ballot problem, $P(\text{tie occurs}) = \frac{2\min(x, 2n-x)}{2n}$.
• So $P(\text{no tie} \mid x) = 1 - \frac{2\min(x,n)}{2n}$ for $x \neq n$.
• If $x = n$: a tie must occur, so $P(\text{no tie} \mid x = n) = 0$.

$P(\text{no tie}) = \sum_{x=0}^{2n} \binom{2n}{x} \frac{1}{2^{2n}} \cdot \left(1 - \frac{\min(x,2n-x)}{n}\right)$

By symmetry and careful summation (as worked out by Mosteller), this simplifies beautifully to:

$\boxed{P(\text{no tie}) = \frac{\binom{2n}{n}}{2^{2n}}}$

Verification for $N = 4$ ($n = 2$):

$P(\text{no tie}) = \frac{\binom{4}{2}}{2^4} = \frac{6}{16} = \frac{3}{8}.$

Let's verify by enumeration. The 16 equally likely sequences (A = heads, B = tails):

| Sequence | Score after each flip | Tie after flip 1? | |---|---|---| | AAAA | 1,2,3,4 | No ✓ | | AAAB | 1,2,3,2 | No ✓ | | AABA | 1,2,1,2 | No ✓ | | AABB | 1,2,1,0 | Tie | | ABAA | 1,0,... | Tie | | ABAB | 1,0,... | Tie | | ABBA | 1,0,... | Tie | | ABBB | 1,0,... | Tie | | BAAA | -1,0,... | Tie | | BAAB | -1,0,... | Tie | | BABA | -1,0,... | Tie | | BABB | -1,0,... | Tie | | BBAA | -1,-2,-1,0 | Tie | | BBAB | -1,-2,-1,-2 | No ✓ | | BBBA | -1,-2,-3,-2 | No ✓ | | BBBB | -1,-2,-3,-4 | No ✓ |

Sequences with no tie: AAAA, AAAB, AABA, BBAB, BBBA, BBBB → 6 sequences.

$P = \frac{6}{16} = \frac{3}{8} = \frac{\binom{4}{2}}{2^4}. \checkmark$

The beautiful surprise: The answer $\dfrac{\binom{2n}{n}}{4^n}$ is exactly the probability that in $2n$ fair coin flips, exactly $n$ are heads — the central binomial probability. And remarkably, the same probability holds for $N = 2n+1$ (an odd number of flips).