Theorem: Bertrand's Ballot Theorem

Consider an election involving two candidates $A$ and $B$, which $A$ has won.
Let $p$ be the number of votes that $A$ received, and $q < p$ be the number of votes that $B$ received.
We assume that $A$ did not win by default, and that at least one vote was cast.
We put all $p + q$ votes in a ballot box and draw them at uniform random.
As we do this, we keep a tally $T_A$ of the votes cast for candidate $A$ and a tally $T_B$ of the votes cast for candidate $B$.
For $1 \le k \le p + q$, we let $\map {T_A} k$ be the number of ballots for $A$ that have been drawn from the ballot box up to and including the $k$th ballot drawn.
We write $\map {T_B} k$ for the corresponding quantity for $B$.
Then the probability that the inequality $\map {T_B} k < \map {T_A} k$ holds for all $k$ is equal to:
:$\dfrac {p - q} {p + q}$
In other words, the probability that candidate $A$ is always ahead of candidate $B$ in the count is:
:$\dfrac {p - q} {p + q}$

Proof:
Given that $A$ wins, the claim that $\map {T_B} k < \map {T_A} k$ for all $k$ is equivalent to the claim that there exists no $k$ with $\map {T_B} k = \map {T_A} k$. 
That is, at no point in the count are candidates $A$ and $B$ tying.
We therefore aim to compute:
:$\map \Pr {\map {T_A} k \ne \map {T_B} k \text { for all } k \in \set {1, \ldots, p + q} }$
That is:
:$1 - \map \Pr {\map {T_A} k = \map {T_B} k \text { for some } k}$
We consider the case where $\map {T_B} 1 = 1$ (that is, the first ballot drawn is for $B$) and the case where $\map {T_A} 1 = 1$ (the first ballot drawn is for $A$).
Using the Law of Total Probability, we write:
:$\map \Pr {\map {T_A} k = \map {T_B} k \text { for some } k} = \map \Pr {\map {T_A} k = \map {T_B} k \text { for some } k \text { and } \map {T_B} 1 = 1} + \map \Pr {\map {T_A} k = \map {T_B} k \text { for some } k \text { and } \map {T_A} 1 = 1}$
If $\map {T_B} 1 = 1$, then there exists a point $k$ at which $\map {T_A} k = \map {T_B} k$, since $A$ wins and must therefore eventually catch up to $B$.
Hence:
:$\map \Pr {\map {T_A} k = \map {T_B} k \text { for some } k \text { and } \map {T_B} 1 = 1} = \map \Pr {\map {T_B} 1 = 1}$
by Intersection with Subset is Subset.
Since there are $q$ votes for $B$ and the first ballot is drawn at uniform random out of a box of $p + q$, we have:
:$\ds \map \Pr {\map {T_B} 1 = 1} = \frac q {p + q}$ 
We now deal with the second probability.
We consider the draws from the ballot as a $\paren {p + q}$-long sequence of $A$s and $B$s, with $p$ $A$s and $q$ $B$s.
That is, we consider a ballot as a string $s \in \set {A, B}^{p + q}$. 
We aim to put the sequences satisfying $\map {T_A} k = \map {T_B} k$ for some $k$ and $\map {T_A} 1 = 1$ in one-to-one correspondence with those sequences that have $\map {T_B} 1 = 1$.
For notational convenience, we write $\map {T_A} {s, k}$ for the number of $A$s occurring in the string $s$ up to character $k$, and similarly for $\map {T_B} {s, k}$. 
We do this by considering the ballots up to the first tie.
We consider the sequence of ballots formed by looking up to and including the ballot that causes the first tie, and then reversing every such ballot.
That is, we flip every vote for candidate $A$ to be a vote for candidate $B$.
We denote this mapping by $\pi : \set {A, B}^{p + q} \to \set {A, B}^{p + q}$.
Explicitly, we take the least $k$ such that $\map {T_A} {s, k} = \map {T_B} {s, k}$ and form $\map \pi s$ by flipping all $A$ votes to $B$ votes and vice versa up to and including ballot $k$. 
For example, the sequence $AABBABA$ sees its first tie at the second instance of $B$.
In this case, we have $p = 4$ and $q = 3$. 
We therefore map $AABBABA$ to the sequence $BBAAABA$, which we write:
:$\map \pi {AABBABA} = BBAAABA$
We argue that $\pi$ is a bijection from $\set {s \in \set {A, B}^{p + q} : \map {T_A} {s, k} = \map {T_B} {s, k} \text { for some } k \text { and } \map {T_A} {s, 1} = 1}$ to $\set {s \in \set {A, B}^{p + q} : \map {T_A} {s, k} = \map {T_B} {s, k} \text { for some } k \text { and } \map {T_B} {s, 1} = 1}$.
Since the first vote for $A$ is reversed to a vote for $B$, we can see that $\pi$ maps $\set {s \in \set {A, B}^{p + q} : \map {T_A} {s, k} = \map {T_B} {s, k} \text { for some } k \text { and } \map {T_A} {s, 1} = 1}$ to $\set {\map {T_A} {s, k} = \map {T_B} {s, k} \text { for some } k \text { and } \map {T_B} {s, 1} = 1}$.
We argue that $\pi$ is an injection.
Suppose that $\map \pi {s_1} = \map \pi {s_2}$ for two strings $s_1, s_2$.
Then $s_1$ is obtained by flipping all the votes up to the first tie in $\map \pi {s_1}$.
We obtain $s_2$ from $\map \pi {s_2}$ similarly.
Since we are applying the process to the same string, we obtain $s_1 = s_2$.
We now argue that $\pi$ is a surjection.
Note that $\pi$ preserves the position of the first tie, since $\map {T_A} {\map \pi s, k} = \map {T_B} {s, k}$ and $\map {T_B} {\map \pi s, k} = \map {T_A} {s, k}$. 
Hence, if we take $t \in \set {\map {T_A} {s, k} = \map {T_B} {s, k} \text { for some } k \text { and } \map {T_B} {s, 1} = 1}$, then by flipping all votes up to the first tie (which includes the first), we obtain $s \in \set {\map {T_A} {s, k} = \map {T_B} {s, k} \text { for some } k \text { and } \map {T_A} {s, 1} = 1}$ with $\map \pi s = t$. 
Hence $\pi$ is a bijection.
Hence:
:$\size {\set {s \in \set {A, B}^{p + q} : \map {T_A} {s, k} = \map {T_B} {s, k} \text { for some } k \text { and } \map {T_A} {s, 1} = 1} } = \size {\set {s \in \set {A, B}^{p + q} : \map {T_A} {s, k} = \map {T_B} {s, k} \text { for some } k \text { and } \map {T_B} {s, 1} = 1} }$
Hence:
:$\Pr \paren {\map {T_A} k = \map {T_B} k \text { for some } k \text { and } \map {T_A} 1 = 1} = \Pr \paren {\map {T_A} k = \map {T_B} k \text { for some } k \text { and } \map {T_B} 1 = 1}$
We have already found that:
:$\ds \Pr \paren {\map {T_A} k = \map {T_B} k \text { for some } k \text { and } \map {T_B} 1 = 1} = \frac q {p + q}$
We therefore have:
:$\ds \map \Pr {\map {T_A} k = \map {T_B} k \text { for some } k} = \frac {2 q} {q + p}$
We established that our desired probability is:
:$1 - \map \Pr {\map {T_A} k = \map {T_B} k \text { for some } k}$
Hence our desired probability is:
:$\ds 1 - \frac {2 q} {q + p} = \frac {q + p - 2 q} {q + p} = \frac {p - q} {p + q}$
{{qed}}
{{Namedfor|Joseph Louis François Bertrand|cat = Bertrand}}
Category:Combinatorics
mu0xvqmv8yyzagsvitwx9wmvct8xomc