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:
“It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
—William Shakespeare (1564–1616)
“But before the extremity of the Cape had completely sunk, it appeared like a filmy sliver of land lying flat on the ocean, and later still a mere reflection of a sand-bar on the haze above. Its name suggests a homely truth, but it would be more poetic if it described the impression which it makes on the beholder.”
—Henry David Thoreau (1817–1862)