In an election between two candidates, n ballots for the…

In an election between two candidates, $n$ ballots for the first candidate and $m$ for the second were placed in the ballot box, $n\gt m$. What is the probability that, when the ballots are drawn one by one, the number of votes for the first candidate will always be greater than the number of votes for the second?

Step 1: Paths

All $\binom{n+m}{n}$ orders of the votes (as sequences of A and B) are equally likely. Draw a path starting at $0$: up by $1$ for a vote for A, down by $1$ for B. The path ends at $n-m$. We need it to stay strictly above $0$ after the start.

Step 2: Reflection principle (see Problem 55)

A good path starts with A. Among paths starting with A, the "bad" ones touch $0$; reflecting the part before the first touch maps them one-to-one onto the paths starting with B. So

\[ \#\text{good} = \#(\text{start with A}) - \#(\text{start with B}) = \binom{n+m-1}{n-1}-\binom{n+m-1}{n}=\frac{n-m}{n+m}\binom{n+m}{n}. \]

\[ \boxed{P=\frac{n-m}{n+m}.} \]

Step 3: Second proof — induction on the last vote

Let $P(n,m)$ be the probability. Look at the last ballot drawn: it is for A with probability $\frac n{n+m}$ and for B with probability $\frac m{n+m}$. If A was always ahead during the whole count, he was also always ahead during the count of the first $n+m-1$ ballots. So

\[ P(n,m)=\frac{n}{n+m}P(n-1,m)+\frac{m}{n+m}P(n,m-1). \]

If $P(n-1,m)=\frac{n-1-m}{n-1+m}$ and $P(n,m-1)=\frac{n-m+1}{n+m-1}$ (induction hypothesis), then

\[ P(n,m)=\frac{n(n-1-m)+m(n-m+1)}{(n+m)(n+m-1)}=\frac{(n-m)(n+m-1)}{(n+m)(n+m-1)}=\frac{n-m}{n+m}. \]

(The base cases $P(n,0)=1$ and $P(n,n)=0$ agree with the formula.)

Step 4: Examples

Even with a clear majority of $60\%$, the winner is ahead during the whole count only in $20\%$ of cases.