## 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 _{k}),_{k} is the difference between the number of votes given to the two candidates among the first k votes that have been counted. _{1} = 1_{n} = u - v._{k} > 0,

### Ballot Lemma

Let, n, u, v, c = u - v, be all positive integers, _{n}(0, c),

where N_{n}(0, c) is the total number of walks from

### Proof

To stay above the x-axis, a walk that starts at the origin, must on the first step get to

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

N_{n-1}(1, c) - N_{n-1}(-1, c) | = C(n - 1, u - 1) - C(n - 1, v - 1) | |

= C(u + v - 1, u - 1) - C(u + v - 1, v - 1) | ||

= [(u - v) / (u + v)] C(u + v, u) | ||

= (c / n) N_{n}(0, c). |

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

What if applet does not run? |

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: _{1}, S_{2}, ..., S_{n})._{n}, S_{n-1}, ..., S_{1}).*dual* statement are the walks for which point

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

**The Ballot Theorem**. The solution to the ballot problem is

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

### References

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

### Pascal's Triangle and the Binomial Coefficients

- Binomial Theorem
- 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
- Lucas' Theorem II
- 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
- Another Binomial Identity with Proofs
- Vandermonde's Convolution Formula
- Counting Fat Sets
- e in the Pascal Triangle
- Catalan Numbers in Pascal's Triangle
- Sums of Binomial Reciprocals in Pascal's Triangle
- Squares in Pascal's Triangle
- Cubes in Pascal's Triangle
- Pi in Pascal's Triangle
- Pi in Pascal's Triangle via Triangular Numbers
- Ascending Bases and Exponents in Pascal's Triangle
- Determinants in Pascal's Triangle

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

Copyright © 1996-2017 Alexander Bogomolny

62618322 |