xxv. Ballot Problem

Problem. Candidate A gets $a$ votes and B gets $b<a$ votes, counted in random order. What is the probability that A is strictly ahead throughout the count?

Answer: $\frac{a-b}{a+b}$ (Bertrand). The number of such orderings is $\frac{a-b}{a+b}\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$.

long long ballotCount(int a, int b) {             // orderings of a A-votes and b B-votes (a > b) with A strictly ahead throughout
    long long c = 1; for (int i = 1; i <= b; i++) c = c * (a + i) / i;   // C(a + b, b)
    return c * (a - b) / (a + b);
}

Proof: the reflection principle

Count lattice paths with $a$ up-steps and $b$ down-steps that stay strictly above $0$ after the first step. Such a path must start with an up-step. Bad paths starting with an up-step touch $0$ at some point; reflecting the part before the first touch gives a bijection with all paths starting with a down-step, of which there are $\left(\genfrac{}{}{0ex}{}{a+b-1}{a}\right)$. Good paths: $\left(\genfrac{}{}{0ex}{}{a+b-1}{a-1}\right)-\left(\genfrac{}{}{0ex}{}{a+b-1}{a}\right)=\frac{a-b}{a+b}\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$. Divide by $\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$ for the probability. Checked by enumerating all orderings for $a\le 8$. With $a=b+1$ and “ahead or tied” this gives the Catalan numbers (Catalan and Lattice Paths).