Thoughts surrounding Ballot Box problem and the extensions of it.
Introduction
The Ballot problem is one of the most elegant results in combinatorics:
it counts how often one candidate can stay ahead in an election count.
Surprisingly, its logic also extends to games like matching pennies, where two players alternately win or lose coins — and we ask:
What is the probability that they are never even again?
We’ll start with the ballot theorem, then reinterpret it through lattice paths and end with the “matching pennies” variant.
The Ballot Box Problem
Imagine candidate A receives $a$ votes and B receives $b$ votes, with $a > b$.
The votes are counted in random order, and we ask:
What is the probability that A is always strictly ahead during the count?
Combinatorial setup & Gemoetric view
The Ballot theorem
The probability that A always leads is:
$$\boxed{P(\text{A always ahead}) = \frac{a-b}{a+b}}.$$
Lattice Path and Geometric View
TBC.
Extension: Matching Pennies
We now consider the matching pennies problem.
Two players, A and B, flip coins $N$ times.
A gains $+1$ for each win and loses $1$ for each loss.
Let $S_k$ be the cumulative score after $k$ rounds:
$$
S_k = X_1 + X_2 + \dots + X_k, \qquad X_i \in {+1,-1}.
$$
We are interested in
$$
P_N = \Pr(S_k \neq 0 \text{ for all } 1 \le k \le N),
$$
the probability that they are never tied at any time during the match.
Setup
The parity of $N$ matters because it determines whether a final tie ($S_N=0$) is even possible.
- Case 1: $N = 2n$ (even) → possible to end tied ($S_N=0$).
- Case 2: $N = 2n+1$ (odd) → final score must be odd, cannot end tied.
We handle both cases separately.
Let $k$ = number of A’s wins.
Then $S_N = 2k - N$.
Each configuration with exactly $k$ wins occurs with probability:
$$
\Pr(\text{A wins } k) = \frac{\binom{N}{k}}{2^N}.
$$
Applying Ballot Thoerem
For fixed $k$, the Ballot theorem gives the probability that the cumulative sum never hits 0:
$$
\Pr(\text{no tie} \mid k) = \frac{|2k - N|}{N},
$$
since only when $k = N/2$ does the path ever return to the axis.
Thus the total probability is obtained by summing over all possible $k$:
$$
P_N = \sum_{k=0}^{N} \Pr(\text{no tie} \mid k) \cdot \Pr(\text{A wins } k)
= \frac{1}{N 2^N} \sum_{k=0}^{N} |2k - N| \binom{N}{k}.
$$
By symmetry, we can simplify each case.
Suming up using Algebra
Case A: $N = 2n$
When $N$ is even, symmetry allows us to sum over $k > n$ and double it:
$$
P_{2n} = \frac{2}{2n , 2^{2n}} \sum_{k=n+1}^{2n} (2k - 2n) \binom{2n}{k}
= \frac{1}{n,2^{2n}} \sum_{k=n+1}^{2n} (k - n) \binom{2n}{k}.
$$
A known binomial identity simplifies the sum:
$$
\sum_{k=n+1}^{2n} (k-n) \binom{2n}{k} = n \binom{2n}{n}.
$$
Hence,
$$
\boxed{
P_{2n} = \frac{\binom{2n}{n}}{2^{2n}}.
}
$$
Or equivalently, with $N=2n$,
$$
\boxed{
P(\text{no tie}) = \frac{\binom{N}{N/2}}{2^{N}}.
}
$$
Case B: $N = 2n + 1$
When $N$ is odd, there is no middle tie term.
Similarly, we sum over $k > n$ and double:
$$
P_{2n+1} = \frac{2}{(2n+1) 2^{2n+1}} \sum_{k=n+1}^{2n+1} (2k - (2n+1)) \binom{2n+1}{k}.
$$
Using another binomial identity:
$$
\sum_{k=n+1}^{2n+1} (2k - (2n+1)) \binom{2n+1}{k}
= (2n+1)\binom{2n}{n}.
$$
Therefore,
$$
\boxed{
P_{2n+1} = \frac{\binom{2n}{n}}{2^{2n}}.
}
$$
Rewriting in terms of $N = 2n + 1$,
$$
\boxed{
P(\text{no tie}) = \frac{\binom{N-1}{(N-1)/2}}{2^{N-1}}.
}
$$
Closing Thoughts
The next time you see a “probability of tie” or “stay below” problem, think of it as a path trapped inside a polygon — and decide which of these three lenses brings the boundary into focus.
Thanks to Bertrand, André, and Catalan for showing that even the humblest ballot box hides deep geometry.
Appendix: Useful Binomial Identities
This section collects several binomial-sum formulas frequently used in combinatorial proofs, including the identity used in the main derivation.
$$ k \cdot \binom{n}{k} = n \cdot \binom{n-1}{k-1} $$
$$\sum_{k=0}^{n} \binom{n}{k} = 2^{n}$$
$$\sum_{k=0}^{n} \binom{2n}{k}
= 2^{2n-1} + \frac{1}{2}\binom{2n}{n}$$
$$\sum_{k=0}^{n} \binom{2n+1}{k} = 2^{2n}$$