Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that in an election person $A$ gets $60$ votes and person $B$ gets $40$ votes in total.

What's the probability that $A$ always leads $B$ in the process of counting the votes?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

This is the famous Bertrands ballot problem. The upshot of the solution is that among the "bad" possibilities (where $B$ leads $A$ at least once), those where the first vote is for $A$ are as likely as those where $B$ had the first vote. The probability of the latter is obviously $40$% here, so the total bad possibilities amount to $80$%, and the probability of $A$ leading $B$ all the time (after the first vote is counted) is $20$%.

Nowadays the bijection between the bad ballot sequences of the first type (where $A$ has the first vote and where $B$ equalises the score at some point) and the second type (where $B$ has the first vote) is usually shown using a "reflection principle", which involves turning certain votes for $A$ into votes for $B$ and vice versa. Personally I find the original proof by D. André at least as transparent in terms of the ballot formulation (as opposed to an equivalent random walk formulation). Map bad sequences of the first type to bad sequences of the second type by cyclically reordering the votes, so as to start with the first vote where $B$ equalised the score. This moves the sub-sequence preceding that vote to the end, a sub-sequence that starts with a vote for$~A$ and after that has a (possibly empty) "Dyck sequence", having balanced in votes for $A$ and $B$ without those for $B$ ever outnumbering those for$~A$. In a bad sequence of the second type, there is a unique final Dyck sequence preceded by a vote for $A$ (counting votes in reverse order, stop the first moment that $A$ gets a lead) and cycling those votes to the front of the sequence produces a bad sequence of the first type. These cycling operations are easily seen to be inverses of one another.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.