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:
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“Much of what passes for quality on British television is no more than a reflection of the narrow elite which controls it and has always thought that its tastes were synonymous with quality.”
—Rupert Murdoch (b. 1931)