Ballot Lemma

One of the circumstances modeled by random walks is the process of counting votes during elections with two candidates. A vote for one of them is thought as +1 and a vote for the other as -1. If a walk starts at (0, 0) and goes through point (k, s_k), k > 0, where s_k is the difference between the number of votes given to the two candidates among the first k votes that have been counted. s₁ = 1 means that the very first vote has been given to the first candidate so that the latter took the lead in the vote counting. Assume there were n votes in all and that, at the final count, the first candidate received u votes and the second v votes so that s_n = u - v. The Ballot Lemma answer the question of the number of ways to order the ballots so that at all steps of vote counting the first candidate maintain his/her leadership over the second candidates, i.e. for how many walks s_k > 0, k > 0?

Ballot Lemma

Let, n, u, v, c = u - v, be all positive integers, n = u + v. The number of walks from (0, 0) to (n, c) that do not touch or cross the x-axis (except at the origin), is given by (c / n) N_n(0, c),

where N_n(0, c) is the total number of walks from (0, 0) to (n, c).

Proof

To stay above the x-axis, a walk that starts at the origin, must on the first step get to (1, 1). SO this is the point where actual counting of walks starts. That is, we are concerned with the number of walks from (1, 1) to (n, c) that neither touch nor cross the x-axis.

It follows from the The Reflection Lemma and the The Reflection Lemmatotal count of walks that the sought number is

The Ballot Lemma has an easy corollary that is illustrated by the applet below.

In the applet, a walk between A and B is paired with its reflection in the midpoint of AB. A walk α is a sequence of ±1 steps: α = (S₁, S₂, ..., S_n). Its (half-turn) reflection α' is the same sequence of steps but performed backwards: α' = (S_n, S_n-1, ..., S₁). The walks with no points on the x-axis, correspond to the walks that never reach the final count c but on the last step. Feller calls this pairing between the two walks "duality". Whereas the Ballot Lemma deals with the walks for which point (0, 0) is the lowest, the subject of its dual statement are the walks for which point (n, c) is the highest.

The Ballot Lemma/Problem was introduced by Joseph Bertrand in 1887 (J. Bertrand, 1822-1900, is popularly known for his Bertrand's Paradox and Bertrand's conjecture in number theory.) The short geometric solution based on the Reflection Principle appeared in 1923 in a paper by J. Aebly followed by a paper by D. Mirimanoff. Already at that time, the problem was generalized to the following form.

The Ballot Problem. Suppose that in an election, candidate A receives u votes and candidate B receives v votes, where u > kv for some positive integer k. Compute the number of ways the ballots can be ordered so that A maintains more than k times as many votes as B throughout the counting of the ballots.

The Ballot Theorem. The solution to the ballot problem is [(u - kv) / (u + v)] C(u + v, u).

For a more detailed history of the problem and a collection of proofs of the theorem, see the paper by M. Renault.

References

1. W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition, Wiley, 1968
2. M. Renault, Four Proofs of the Ballot Lemma, Mathematics Magazine, v. 80, n. 5, December 2007

Pascal's Triangle and the Binomial Coefficients

• Arithmetic in Disguise
• Construction of Pascal's Triangle
• Dot Patterns, Pascal Triangle and Lucas Theorem
• Integer Iterations on a Circle
• Leibniz and Pascal Triangles
• Lucas' Theorem
• Patterns in Pascal's Triangle
• Random Walks
  • Ballot Lemma
  • The Reflection Lemma
• Sierpinski Gasket and Tower of Hanoi
• Treatise on Arithmetical Triangle
• Ways To Count

|Activities| |Contact| |Front page| |Contents| |Algebra| |Up| |Store|

Copyright © 1996-2012 Alexander Bogomolny