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:
“War is a beastly business, it is true, but one proof we are human is our ability to learn, even from it, how better to exist.”
—M.F.K. Fisher (1908–1992)
“With some people solitariness is an escape not from others but from themselves. For they see in the eyes of others only a reflection of themselves.”
—Eric Hoffer (1902–1983)