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:
“The insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.”
—Charles Baudelaire (1821–1867)
“The Americans ... have invented so wide a range of pithy and hackneyed phrases that they can carry on an amusing and animated conversation without giving a moment’s reflection to what they are saying and so leave their minds free to consider the more important matters of big business and fornication.”
—W. Somerset Maugham (1874–1965)