Bertrand's ballot theorem
In combinatorics, Bertrand's ballot problem is the question: "In an election where candidate A receives p votes and candidate B receives q votes with p > q, what is the probability that A will be strictly ahead of B throughout the count?" The answer is
The result was first published by W. A. Whitworth in 1878, but is named after Joseph Louis François Bertrand who rediscovered it in 1887.
In Bertrand's original paper, he sketches a proof based on a general formula for the number of favourable sequences using a recursion relation. He remarks that it seems probable that such a simple result could be proved by a more direct method. Such a proof was given by Désiré André, based on the observation that the unfavourable sequences can be divided into two equally probable cases, one of which (the case where B receives the first vote) is easily computed; he proves the equality by an explicit bijection. A variation of his method is popularly known as André's reflection method, although André did not use any reflections.
Suppose there are 5 voters, of whom 3 vote for candidate A and 2 vote for candidate B (so p = 3 and q = 2). There are ten possibilities for the order of the votes cast:
For the order AABAB, the tally of the votes as the election progresses is:
For each column the tally for A is always larger than the tally for B so the A is always strictly ahead of B. For the order AABBA the tally of the votes as the election progresses is:
For this order, B is tied with A after the fourth vote, so A is not always strictly ahead of B. Of the 10 possible orders, A is always ahead of B only for AAABB and AABAB. So the probability that A will always be strictly ahead is
and this is indeed equal to as the theorem predicts.
...
Wikipedia