Proof By Reflection
For A to be strictly ahead of B throughout the counting of the votes, there can be no ties. Separate the counting sequences according to the first vote. Any sequence that begins with a vote for B must reach a tie at some point, because A eventually wins. For any sequence that begins with A and reaches a tie, reflect the votes up to the point of the first tie (so any A becomes a B, and vice-versa) to obtain a sequence that begins with B. Hence every sequence that begins with A and reaches a tie is in one to one correspondence with a sequence that begins with B, and the probability that a sequence begins with B is, so the probability that A always leads the vote is
- the probability of sequences that tie at some point
- the probability of sequences that tie at some point and begin with A or B
Read more about this topic: Bertrand's Ballot Theorem
Famous quotes containing the words proof and/or reflection:
“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (1819–1891)
“Public morning diversions were the last dissipating habit she obtained; but when that was accomplished, her time was squandered away, the power of reflection was lost, [and] her ideas were all centered in dress, drums, routs, operas, masquerades, and every kind of public diversion. Visionary schemes of pleasure were continually present to her imagination, and her brain was whirled about by such a dizziness that she might properly be said to labor under the distemper called the vertigo.”
—Sarah Fielding (1710–1768)