Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar

__________________________________________________________________________

The Ballot Theorem and the Reflection Principle

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features. The applets use JavaScript which you need to have enabled in order to display and use the applets.

_______________________________________________________________________________________________

Rating

Rating

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

Section Starter Question

Section Starter Question

Suppose that in an election candidate A receives 4 votes and candidate B receives 3 votes. Explicitly enumerate all the ways that the votes can be ordered. In how many ways does A maintain more votes than B throughout the counting of the ballots?

_______________________________________________________________________________________________

Key Concepts

Key Concepts

  1. Suppose that in an election, candidate A receives a votes and candidate B receives b votes, where a kb for some positive integer k. 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 is
    a kb a + b a + b a .

  2. The Reflection Method is a popular proof of the solution of the Ballot Problem because it is relatively easy, visual and it has generalizations beyond ballot counting to random walks and Brownian Motion.
  3. The Cycle Lemma proves that for any ballot sequence of a votes for A and b votes for B, exactly a kb of the a + b cyclic permutations of the sequence are good. Consequently, a fraction (a kb)(a + b) of all ballot permutations are good.

__________________________________________________________________________

Vocabulary

Vocabulary

  1. Bertrand’s Ballot Problem is the following combinatorial problem: Suppose that in an election, candidate A receives a votes and candidate B receives b votes, where a kb for some positive integer k. In how many ways can the ballots be ordered so that A maintains more than k times as many votes as B throughout the counting of the ballots?
  2. The Reflection Principle is that the set of paths from (1, 1) to (a + b,a b) that do touch the x-axis somewhere is in one-to-one correspondence with the set of all paths from (1,1) to (a + b,a b).
  3. A partition of a set into subsets of equal size is called a uniform partition.

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

This section introduces the Ballot Problem which is a purely combinatorial problem. The solution to the problem results in the Ballot Theorem. This section has several proofs of this combinatorial result, including the Reflection Principle. Later sections have probabilistic interpretations of Bertrand’s Ballot Theorem for positive lattice paths, and hitting time results for a Bernoulli random walk. This interpretation is equivalent to the Reflection Principle for Bernoulli random walks. In later sections the Reflection Principle is a tool in the proof of the Arcsine Law for binomial random variables.

Introduction and History

Definition. Bertrand’s Ballot Problem is the following combinatorial problem: Suppose that in an election, candidate A receives a votes and candidate B receives b votes, where a kb for some positive integer k. In how many ways can the ballots be ordered so that A maintains more than k times as many votes as B throughout the counting of the ballots?

Definition. More strictly, the Ballot Theorem when k = 1 is called the strict Ballot Problem and for k 1 called the generalized Ballot Problem.

The solution of both problems is:

Theorem 1 (Ballot Theorem). Suppose that in an election, candidate A receives a votes and candidate B receives b votes, where a kb for some positive integer k. 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 is

a kb a + b a + b a .

The history of the Ballot Problem is tangled. Renault [17] gives a brief history of the Ballot Problem with four proofs. Takás [19] gives a complete historical account of the development of ballot theorems with several proofs of the Ballot Theorem. Kager [14], van der Hofstad and Keane [21], and Grimmett and Stirzaker [13] all cite Whitworth [22] with a priority arrangement version in 1878. However, the Ballot Problem in its usual form is credited to Bertrand [5]. In 1887 Joseph Bertrand introduced the Ballot Problem for k = 1, gave a proof by induction, and asked if a “direct proof” could be found. In the same year that Bertrand posed his question (and in the same journal only 38 pages later) Émile Barbier [10] stated a solution to the ballot problem for arbitrary k, but without any proof. Still in the same year (and only 29 pages later yet in the same journal) Désiré André [4] produced a short combinatorial proof of the Ballot Problem for k = 1. In 1923, Aeppli [2] gave the first proof of the Ballot Theorem for k 1 in his Ph. D. thesis, [3]. Takás [19] includes the original proofs by André and Aeppli.

According to Renault [18] many sources cite André [4] claiming that he used the “Reflection Principle” to solve Bertrand’s Ballot Problem. It is not strictly accurate to say that André employed the Reflection Method in his proof. The “Reflection Principle” is a variation of André’s method of proof. Bertrand’s textbook on probability [6], first published in 1888, solves the Ballot Problem exactly as André did. Comtet [7] formulated the “Reflection Principle”, stating that it is essentially “due to André”. In the following years, many other minor variations appeared (see [9] for references).

In 1923 Aebly [1] conceived of ballot permutations as paths starting from a corner on a rectangular grid, and he observes a certain symmetry of bad paths across the diagonal (compare [24, pages 172-175]). Mirimanoff [16] (the very next article in the same journal) builds on Aebly’s observations and relates this symmetry to ballot permutations of A’s and B’s by applying a transposition to an initial segment of a bad ballot permutation. Viewed geometrically, Mirimanoff’s method is exactly the reflection method we know today. When did authors start claiming that André actually used the reflection method in his solution? This is more difficult to ascertain. In 1947 Dvoretzky and Motzkin [9] introduced a new method of proof to the Ballot Problem and its generalization. They accurately describe André’s contribution, making no mention of the Reflection Method, and write “André’s proof or variations of it may be found in most of the classical treatises on the theory of probability.” In 1957, citing this paper of Dvoretzky and Motzkin, Feller [11, page 66] not quite accurately writes “As these authors point out, most of the formally different proofs in reality use the reflection principle …” suggesting, perhaps, that the reflection method was the original method of solution. Feller, four pages later, states the reflection principle and makes the footnote, “The probability literature attributes this method to D. André, (1887).” The first edition of Feller’s book (1950) mentions neither André nor the Reflection Principle. The earliest source that Renault could find linking André and the Reflection Method is J. L. Doob [8, page 393], who writes while describing Brownian motion processes, “…similar exact evaluations are easily made …using what is known as the reflection principle of Désiré André.” These early sources do not explicitly state that André used the reflection method in his own proof, but this could be inferred, and other writers since then have naturally assumed that André did indeed use the reflection method.

Proof by Induction

Proof (Generalized Ballot Theorem by Induction). Let Nk(a,b) denote the number of ways the a + b ballots (a kb) can be ordered so that candidate A maintains more than k times as many votes as B throughout the counting of the ballots. The conditions Nk(a, 0) = 1 for all a > 0 and Nk(kb,b) = 0 for all b > 0 are easily verified by considering the statement of the ballot problem, and they both satisfy

Nk(a,b) = a kb a + b a + b a .

For b > 0 and a > kb, note that Nk(a,b) = Nk(a,b 1) + Nk(a 1,b) by considering the last vote in a ballot permutation. By induction, this quantity is

a k(b 1) a + b 1 a + b 1 a + a 1 kb a + b 1 a + b 1 a 1

which simplifies to

a kb a + b a + b a

Remark. This proof is easy and short, but it gives no geometric intuition or indication of the symmetries in the Ballot Problem.

Remark. See also [24, pages 182-184] for a detailed induction proof.

The Reflection Principle

The Reflection Principle is a popular proof because it is easy, visual, and it has generalizations beyond ballot counting to random walks and Brownian Motion. Feller [11] gives an account of the Reflection Principle.

Visualize ballot permutations as lattice paths in the Euclidean plane with votes for A as upsteps with vector (1, 1) and votes for B as downsteps with vector (1,1). See Figure 1. Call ballot permutations (or paths) that satisfy the ballot problem “good”, and call those that do not “bad.”

Definition. The Reflection Principle  is that the set of paths from (1, 1) to (a + b,a b) that do touch the x-axis somewhere is in one-to-one correspondence with the set of all paths from (1,1) to (a + b,a b).

Proof (Strict Ballot Theorem by the Reflection Principle). The terminal point of the path is (a + b,a b). Since every good path must start with an upstep, there are as many good paths as there are paths from (1, 1) to (a + b,a b) that never touch the x-axis.

The claim is that the set of paths from (1, 1) to (a + b,a b) that do touch the x-axis somewhere is in one-to-one correspondence with the set of all paths from (1,1) to (a + b,a b). The claim is established by reflecting across the x-axis the initial segment of the path that ends with the step that first touches the x-axis. Subtracting the number of these paths from the number of all paths from (1, 1) to (a + b,a b) produces the number of good paths:

a + b 1 a 1 2a + b 1 b 1 = a b a + b a + b a


Reflection Principle

Figure 1: Example of the Reflection Principle with a = 4, b = 4

André’s Original Proof

André was the first to solve the ballot problem by subtracting the number of bad ballot permutations from the number of all possible ballot permutations. This is the approach taken by the Reflection Principle. However, whereas the Reflection Principle modifies an initial segment of a lattice path (equivalently, a ballot permutation), André uses no geometric reasoning and he interchanges two portions of a ballot permutation.

André supposes that a ballots are marked “A” and b ballots are marked “B”. He first notes that every ballot permutation starting with a “B” is bad and there are a+b1 a of these.

Proof (André’s Original Proof of the Strict Ballot Theorem). This proof is a paraphrase of a translation of André’s original proof, adapted from Renault [18].

“The number of possible outcomes is obviously the number of permutations one can form with a letters A and b letters B. Let Q(a,b) be the number of unfavorable outcomes. The permutations corresponding to them are of two kinds: those that start with B, and those that start with A. The number of unfavorable permutations starting with B equals the number of all permutations which one can form with a letters A and b1 letters B, because it is obviously enough to suppress the initial letter B to obtain the remaining letters. The number of unfavorable permutations starting with A is the same as above, because one can, by a simple rule, make a one-to-one correspondence with the permutations formed with a letters A and b 1 letters B. This rule is composed of two parts:

  1. Given an unfavorable permutation starting with A, one removes the first occurrence of B that violates the law of the problem [i.e., causes the number of B’s to equal the number of A’s], then one exchanges the two groups separated by this letter: one obtains thus a permutation, uniquely determined, of a letters A and b 1 letters B. Consider, for example, the unfavorable permutation AABBABAA, of five letters A and three letters B; by removing the first B that violates the law, one separates two groups AAB, ABAA; by exchanging these groups, one obtains the permutation ABAAAAB, formed of five letters A and two letters B. (See Figure 2.)
    PIC
    PIC

    Figure 2: Example of André’s one-to-one correspondence with AABBABAA

  2. Given an arbitrary permutation of a letters A and b 1 letters B, one traverses it from right to left until one obtains a group where the number of A’s exceeds [by one] the number of B’s; one considers this group and that which the letters placed at its left form; one exchanges these two groups, while placing between them a letter B: one thus forms an unfavorable permutation starting with A that is uniquely given. Consider, for example, the permutation ABAAAAB; while operating as described, one divides it in two groups ABAA, AAB; by exchanging these groups and placing the letter B between them, one forms the unfavorable permutation AABBABAA.

It results from all the above that the total number of unfavorable outcomes is twice the number of permutations one can form with a letters A and b 1 letters B.”

Thus André establishes a one-to-one correspondence between the bad ballot permutations starting with “A” and all permutations consisting of a “A’s” and b 1 “B’s”. There are a+b1 a of these. The number of bad ballot permutations is 2a+b1 a . The ballot theorem then follows by simplifying

a + b a 2a + b 1 a = a b a + b a + b a .

Example. Consider an example with 6 votes, 4 for A and 2 for B. There are 6 4 = 15 possible vote count patterns, of which 25 4 = 10 are bad. There are 5 4 = 5 unfavorable permutations starting with B.

Ballots TypeStart Partition Rearrangement





AAAABBGood
AAABAB Good
AABAABGood
ABAAAB Bad Starts with A A B AAAB AAABA
BAAAABBad Suppress initial B AA AAB AABBAA
AAABBAGood
AABABA Good
ABAABABad Starts with A A B AABA AABAA
BAAABA Bad Suppress initial B AA ABA ABABAA
AABBAABad Starts with A AAB B AA AAAAB
ABABAA Bad Starts with A A B ABAA ABAAA
BAABAABad Suppress initial B AA BAA BAABAA
ABBAAABad Starts with A A B BAAA BAAAA
BABAAA Bad Starts with B ABA AA AABABA
BBAAAABad Starts with B BAA AA AABBAA

Proof for the Generalized Ballot Problem

This proof for the Generalized Ballot Problem uses the lattice path idea from the Reflection Principle proof. In the Generalized Ballot Problem, votes for A are upsteps (1, 1), votes for B are downsteps (1,k). We wish to find the number of lattice paths starting at the origin and consisting of a upsteps (1, 1) and b downsteps (1,k) such that no step ends on or below the x-axis. The difficulty in generalizing the Reflection Principle is that when one reflects such a lattice path, the result does not have the required types of upsteps and downsteps. Goulden and Serrano [12] also note the literature has many solutions to the generalized ballot problem but “there appears to be no solution which is in the spirit of the reflection principle.” They go on to provide a proof that rotates the initial path segment by 180; even so, they acknowledge that their proof does not specialize to the Reflection Principle when k = 1. (As a side note, rotating a path is equivalent to writing a ballot permutation in reverse order. Uspensky [20] used this principle to solve the Ballot Problem in 1937.)

Proof (Generalized Ballot Theorem). For 0 i k, let i denote the set of bad paths whose first bad step ends i units below the x-axis. Note that the paths in k necessarily start with a downstep. Clearly these k + 1 sets are disjoint and their union is the set of all bad paths. Let 𝒜 be the set of all paths consisting of a upsteps and b 1 downsteps, without regard to location in the plane; |𝒜| = a+b1 a . We prove that |i| = |𝒜| for each i in the range 0 i k by providing a one-to-one correspondence between i and 𝒜.


PIC
PIC

Figure 3: Example with k = 3, XDY 1, and Y X 𝒜.

Given a path P i write P = XDY where D is the first downstep that ends on or below the x-axis (note that X is empty if i = k). The path Y X is then uniquely determined and is an element of 𝒜. Given a path Q 𝒜, scan the path from right to left until a vertex is found lying k i units below the terminal vertex of Q (note that this vertex is the terminal vertex of Q itself if i = k). Such a vertex must exist since the initial vertex of Q lies more than k units below the terminal vertex of Q because a kb 0 so a k(b 1) k. Write Q = Y X, where Y and X are the paths joined at that vertex. Construct path P = XDY by interchanging X and Y and inserting a downstep D between them. Translating P to start at (0, 0), the path touches the x-axis only at the origin, and XD ends i units below the x-axis; hence P i. Therefore, the number of good paths is

a + b a (k + 1)a + b 1 a = a kb a + b a + b a .

Proof (Alternative Proof to Generalized Ballot Theorem). An alternate formulation of the proof: For 0 i k, let i denote the set of bad paths whose first bad step ends i units below the x-axis. Clearly these k + 1 sets are disjoint and their union is the set of all bad paths. Notice that the paths in k are exactly those paths that start with a downstep, and so |k| = a+b1 a . We now show that for any ik we actually have |i| = |k|. Let P be a path in i, (ik), and identify the first step of P that ends i units below the x-axis. Let X be the initial segment of P that ends with that step and write P = XY . Let X̃ denote the path that results from rotating X by 180, exchanging its endpoints; see Figure ??. Since X ends with a downstep, X̃ starts with a downstep, and consequently X̃Y k.


PIC
Figure 4: Rotation of X by 180, exchanging the endpoints.

The same process converts a path in k into a path in i, (ik). If P k, then identify the first step that ends i units below the x-axis. Let X denote the initial segment of P that ends with that step and write P = XY . Since X necessarily ends with an upstep, we have X̃Y i.

Therefore, the number of good paths is

a + b a (k + 1)a + b 1 a = a kb a + b a + b a .

Proof by the Cycle Lemma

Proof (Generalized Ballot Theorem by the Cycle Lemma). A ballot permutation is a sequence of a + b terms where each term is either 1 or k; votes for A correspond to the 1’s and votes for B correspond to the k’s. A sequence is called good if every partial sum is positive, and bad otherwise. Observe that the sum of a sequence is a kb 0. Let C be any circular arrangement of a 1’s and b k’s. Now prove the Cycle Lemma: of the a + b terms in C, exactly a kb start good sequences when C is read once around clockwise.

The claim is now that there must exist a sequence X = 1, 1,, 1,k in C with k consecutive 1’s. Suppose not, that is, there is a placement of k’s around the circle with at most k 1 1’s between each k. Then the total number of 1’s around the circular arrangement is at most (k 1)b. But (k 1)b < kb a which is not possible, so the claim is true.

No term of X can start a good sequence, because the partial sum would be less than or equal to zero at the k term.


PIC
Figure 5: Example of C and C with a = 8, b = 2, k = 3.

Let C be the circular arrangement created from C by removing X. Then C has a = a k terms of 1’s and b = b 1 terms of k’s. Note that a kb = a k k(b 1) = a kb 0 so C satisfies the same hypotheses as C. Furthermore, since the sequence X has sum 0, it has no “net effect” on good sequences. Thus, a term of C starts a good sequence if and only if the corresponding term in C starts a good sequence. Consequently, C and C have exactly the same number of terms that start good sequences. See Figure 5. Continuing in this manner, one removes sequences of the form 1, 1, 1,, 1,k until a circular arrangement consisting only of 1’s remains. At this stage, there are a kb 1’s, and every term starts a good sequence. Hence there are exactly a kb good sequences in C, and the Cycle Lemma is proved. If there is periodicity in C then not all a kb good sequences will be distinct. However, we can conclude that the ratio of good sequences to all sequences is a kb to a + b. Therefore, the number of good paths is

a kb a + b a + b a .

Remark. The Cycle Lemma provides a surprising result: for any ballot sequence of a votes for A and b votes for B, exactly a kb of the a + b cyclic permutations of the sequence are good. Consequently, a fraction (a kb)(a + b) of all ballot permutations are good.

Proof by Uniform Partition

Remark. As an overview, the following proof considers a set with (a kb)a+b a elements, and partitions this set into a + b subsets of equal size. This is called a uniform partition into a + b subsets.  One of the subsets corresponds to the set of good ballot permutations, and from this the ballot theorem follows. The proof is from [17] and extends the proofs in [23].

Proof (Generalized Ballot Theorem by Uniform Partition). Consider lattice paths starting from the origin and consisting of a upsteps with vector (1, 1) and b downsteps with vector (1,k), and assume the strict inequality a > kb. Let 𝒜 = 𝒜(a,b,k) be the set of all such paths. Given path P 𝒜 we let L(P) denote the set of x-values of the a kb “rightmost lowest” vertices of P; see Figure 6. More precisely, given path P 𝒜, let y0 denote the least y-value of all the vertices of P, and let r(t) denote the x-value of the rightmost vertex of P along the line y = t; then L(P) = {r(t)|t ,y0 t y0 + (a kb) 1}.


PIC
Figure 6: Example of uniform partition with k = 2, a = 6, b = 2. For each path P 𝒜, the path P and the set L(P), Observe that among all the sets L(P), each number from 0 to 7 occurs exactly 7 times.

Let Ψ = {(P,j)|P 𝒜,j L(P)} and note that |Ψ| = (a kb)|𝒜|. Let Ωi = {(P,i) Ψ|i L(P)}, defined for 0 i a + b 1. The sets Ωi partition Ψ into a + b disjoint subsets.

Claim 1
There is a one-to-one correspondence between Ω0 and the set of good paths. If P 𝒜 is good, then (0, 0) is the lowest vertex in P and it is the only vertex on the x-axis, so (P, 0) Ω0. Conversely, if (P, 0) is in Ω0, then no vertex of P can lie on the x-axis to the right of the origin, and so P is good.
Claim 2
The sets Ωi uniformly partition Ψ. We show this by providing a one-to-one correspondence between Ωi and Ω0. If (P,i) Ωi, then write P = XY where X is the initial path of P consisting of the first i steps, and Y consists of the remaining steps. Since i L(P), we can observe that Y stays above the height of its initial vertex, and X never descends a kb or more units below the height of its terminal vertex. Consequently the path Y X is good and (Y X, 0) Ω0. Conversely, if (Q, 0) Ω0, then write Q = Y X where X consists of the final i steps of Q. The same qualities of X and Y hold as noted above, and the pair (XY,i) i.

The two claims above imply that the number of good paths in 𝒜 is

|Ω0| = |Ψ| a + b = (a kb)|𝒜| a + b = a kb a + b a + b a

Remark. Suppose we let 𝒜i denote the set of paths for which i is among the x-values of the a kb rightmost vertices, i.e., 𝒜i = {P 𝒜|i L(P)}. When a kb = 1, the sets 𝒜0,𝒜1,,𝒜a+b1 are disjoint and all have the same cardinality. In other words, partitioning 𝒜 according to the x-value of a path’s rightmost lowest vertex creates a uniform partition of 𝒜. When a kb 1, the sets 𝒜i continue to have the same cardinality. However the 𝒜i are no longer disjoint. To the contrary, each path in 𝒜 will be a member of precisely a ykb of these sets.

Proof by Rotation and Shadowing

Remark. The following proof is adapted from the “third proof” of Yaglom and Yaglom, [24, pages 172-175]. Their proof uses an “up-or-right” walk on an integer lattice to represent the ballot count instead of the “up-and-down” random walk orientation used in Figures 1,2,3,?? and6. The adaptation modifies their proof to this “up-and-down” random walk representation and shortens the explanation.

Rotation and Shadowing. Consider any particular arrangement of the a + b ballots in a list. From this list we can obtain a + b 1 new lists as follows: move the first ballot from the front of the list to the last place, thus creating a new arrangement in which the second, third, …, and a + bth ballot of the original list are now one place forward. Then repeat the process. By repeating the process, we obtain a total of a + b 1 new lists, adding to this the original list, we have a total of a + b arrangements. We will show that a b of these arrangements are good. Then the total number of arrangements is

a b a + b a + b a .

To represent all a + b rotated arrangements obtained from a particular arrangement, adjoin to the end (a + b,Aa+b) of the path a replica of the particular path. See Figure 7. For convenience label the vertices of the ballot count path and its appended copy as A0,A1,A2,,Aa+b,Aa+b+1,,A2a+2b. Now the a + b rotated arrangements correspond to the paths which consist of the subpaths that start respectively at A0,A1,,Aa+b1 and consequently end at the points Aa+b,Aa+b+1,,A2a+2b. Good arrangements correspond to paths of length a + b in which every vertex other than the first is preceded by more upsteps with vector (1, 1) than downsteps with vector (1,1), that is, paths which lie above the horizontal. Now illuminate the extended path from the right with a beam of parallel rays. Then the good arrangements correspond to paths in which the light falls upon the base point Ak That is, the base point does not lie in the shadow thrown by some downsteps. (Note that if the Ak does not lie in the shade of the path AkAk+1Ak+2Ak+a+b, then Ak cannot lie in the shade thrown by the steps from Aa+b+k to A2a+2b either. This follows from the fact that the path Aa+b+k to A2a+2b is a duplicate of AkAk+1Aa+b ). Thus we only have to count how many of the points A0,A1,A2,,Aa+b are illuminated by the parallel rays.

Of the points, A0,A1,A2,,Aa+b1 the only ones which have a chance of being illuminated are the a points which correspond to an upstep with vector (1, 1). But even such a point may lie in the shade cast by a later upstep. For example, in Figure 7, A5 and A7 lie in the shade cast by A9.


PIC
Figure 7: Example of the rotation and shadowing proof with a = 7 and b = 4. A copy of the path is adjoined to the original path.

Denote by d the number of downsteps of A0,A1,A2,,Aa+b which cast their shadows to the left, i. e. segments like A0A1 and A1A2 in Figure 7. Then the other b d downsteps cast their shadows on upsteps. Since Aa+b, Aa+b+1, Aa+b+2, …, A2a+2b is a replica of A0, A1 , A2, …, Aa+b1, exactly d downsteps of Aa+b, Aa+b+1, Aa+b+2, …, A2a+2b cast their shadows to the left of Aa+b. These shadows fall on upsteps to the left of Aa+b. These shadows fall on upsteps of A0,A1,A2,,Aa+b; hence there are altogether b d + d = b upsteps in the shade. Thus, of the a points Ai which have a chance of being illuminated, exactly b are removed by virtue of the shadow cast on the segment AiAi+1. Hence there remain a b illuminated points of A0,A1,A2,,Aa+b1. For example, in Figure 7, a = 7, b = 4 and exactly 7 4 = 3 are illuminated. This proves that for a > b exactly a b of the a + b arrangements of ballot counts obtained from any one arrangement by rotation satisfy the requirements of the Ballot Theorem.

Note that the a + b arrangements obtained from a single one by rotations are not necessarily all distinct. If a and b are not relatively prime, then it may happen that an arrangement may consist of parts which are repetitions. For example, with a = 6 and b = 3, an arrangement may be ABAABAABA. In such a case, the rotations will result in arrangements which are repeated the same number of times. In the example, among the 9 arrangements from rotations, there are 3 arrangements, each repeated 3 times.

In any case, the ratio of the number of good arrangements to the total number of arrangements is

a b a + b.

Therefore, the number of possible good arrangements is

a b a + b a + b a .

Remark. The proof by rotation and shadowing is another proof of the Cycle Lemma.

Remark. This rotation and shadowing proof can be modified for the generalized ballot theorem. The parallel rays are not horizontal, but come at an angle to the axis. See [24, pages 179-182].

Weak Ballot Problem and Catalan Numbers

The ballot problem is often stated in a “weak” version: suppose that candidate A receives m votes and candidate B receives n votes, where m kn for some positive integer k, and compute the number of ways the ballots can be ordered so that A always has at least k times as many votes as B throughout the counting of the ballots.

Any ballot permutation in which A maintains at least k times the number of votes for B can be converted into one in which A maintains more than k times the number of votes for B by simply appending a vote for A to the beginning of the permutation. Clearly this process is reversible, and hence the solution to the weak version is the same as the “strict” version when A receives m + 1 votes and B receives n votes:

(m + 1) kn (m + 1) + n (m + 1) + n m + 1 = m + 1 kn m + 1 m + n m .

Putting k = 1 and m = n produces the Catalan numbers

Cn = 1 n + 1 2n n .

Sources

This section is adapted from Renault, [17] and [18]. The Reflection Principle is adapted from [15]. Some the history is also adapted from [14]. The rotation and shadowing proof is adapted from [24]. Some of the problems are from [24].

_______________________________________________________________________________________________

Algorithms, Scripts, Simulations

Algorithms, Scripts, Simulations

Algorithm

For the generalized ballot problem, set the size of a downstep k, the number a of ballots for A and the number b of ballots for B. Then the total number of ballots is the length l = a + b. There are then a+b ab places to have the downsteps corresponding to ballots for B. In a sequence of nested loops systematically place the downsteps representing ballots for B in an (a + b) × a+b ab matrix of ones. Then cumulatively sum this matrix down the columns to get all possible running ballot counts and save the matrix for later plotting or analysis.

Compute a kb. For each of the a+b ab ballot counts, find the minimum value y0. Then create a block matrix of size (a kb) × (a kb)a+b ab with blocks of size (a kb) × (a kb). Fill each block with the coordinates of the points corresponding to the values L(P) = {r(t)|t Z,y0 t y0 + (a kb) 1}. Save the matrix for later plotting or analysis.

Note that this algorithm does not scale well because of the inherent growth of the binomial coefficients.

Scripts

Scripts

Octave

Octave script for uniform partitions.

k = 2; 
a = 6; 
b = 2; 
length = a+b; 
 
ballots = ones(lengthlength(length1)/2); 
 
# Systematically place the downsteps from ballots for B. 
c = 0; 
for i = 1:length
  for j= (i+1):length 
    c = c + 1; 
    ballots(i,c) = k; 
    ballots(j,c) = k; 
  endfor
endfor
 
ballot_count = cumsum(ballots); 
 
# Put the ballot count in a matrix whose 
# first column is xcoordinates 
# and first row is 0 to start at origin 
plot_ballot_count = zeros(length+1, length(length1)/2 + 1); 
plot_ballot_count(2:length+1, 2:length(length1)/2 + 1) =  
ballot_count; 
plot_ballot_count(:,1) = 0:length
 
save uniform_partition_plots.dat plot_ballot_count 
 
# Build an block matrix with length(length1)/2 blocks 
# of size (akb)by2.  Blocks correspond to each plot. 
# Rows of each block contain the (akb) points of L(P), 
# where for path (or plot) P in good paths mathcal(A) 
y0 = min(plot_ballot_count); 
amkb = a  kb; 
LP = zeros(amkb,amkblength(length1)/2); 
# Octave find treats a whole matrix as a single column, 
# but I need to treat the uniform partition column by column, so here is a place 
# where for clarity, better to loop over columns, using find on each 
for p=1:length(length1)/2    # amkbby2 block for each ballot count 
  for i = 1:amkb            # rows for y0,y0+1,...,y0+(amkb1) 
    LP(i,2p1) = maxfind( plot_ballot_count(:,p+1) == y0(p+1) + (i1) ))1; 
    # first column of block p is xcoord where L(P) member (i1) is found 
    LP(i,2p) = y0(p+1) + (i1); 
  # second column of block p is ycoord of the L(p) member (i1) 
  endfor
endfor
 
 
save append uniform_partition_plots.dat LP
GnuPlot

GnuPlot script for uniform partitions.

set term wxt size 640,768      #seems to be a pleasing ratio of width 640 to height 768 
set multiplot layout 7,4 

set border 0              # no border ( mathematical, not eng or physics style) 
set xtics nomirror          # no tic marks on top 
set ytics nomirror          # ... or right 
set xzeroaxis linetype 
set xtics axis 
set yzeroaxis linetype 
unset key 
# ls 7 is black filled circles, with black lines 
do for [i=2:29] { 
    j = 2i3              #gnuplot doesn’t seem to like arithmetic in 
    k = 2i2              # ”using (2i3):(2i4) so do it here first 
    plot ’uniform_partition_plots.dat’ index 0  
             using 1:i:xticlabel(””):yticlabel(””)  
             with linespoints ls 7,   
          ’’                          index 1  
             using j:k  
             with points ls 7 lc rgb ”red” 
} 
 
unset multiplot

__________________________________________________________________________

Problems to Work

Problems to Work for Understanding

  1. Do the calculations to show
    a + b 1 a 1 2a + b 1 b 1 = a b a + b a + b a

  2. Do the calculations to show
    a + b a 2a + b 1 a = a b a + b a + b a .

    Explain why this is the same as the previous problem.

  3. Do the calculations to show
    a + b a (k + 1)a + b 1 a = a kb a + b a + b a .

  4. Do the calculations to show
    a k(b 1) a + b 1 a + b 1 a + a 1 kb a + b 1 a + b 1 a 1

    simplifies to

    a kb a + b a + b a

  5. Consider the case of 7 votes with 4 votes for A and 3 votes for B. Make a chart of “good” and “bad” ballot counting permutations and rearrangements as in the example of André’s proof.
  6. Suppose m + n people are waiting in line at a box office; n of them have only five-dollar bills and the other m have only ten-dollar bills with nothing smaller. The tickets cost $5 each. When the box-office opens, the till has no money. If each customer buys just one ticket, what is the probability that none of them will have to wait for change? (From [24], problem 83a.)
  7. Solve the same problem under the assumption that initially there were p five-dollar bills in the till.
  8. For the purposes of this problem assume there exist three-dollar bills. Suppose m + n people are waiting in line at a box office; n of them have only one-dollar bills and the other m have only three-dollar bills and nothing smaller. The tickets cost $1 each and each person wants one ticket. When the box-office opens, the till has no money. If each customer buys just one ticket, what is the probability that none of them will have to wait for change? (From [24], problem 83c.)
  9. Modify the scripts to display the uniform partition of the ballot counts for 4 votes for A and 3 votes for B.

__________________________________________________________________________

Books

Reading Suggestion:

References

[1]   J. Aebly. Démonstration du problème du scrutin par des considérations géométriques. L’enseignement mathématique, 23:185–186, 1923.

[2]   A. Aeppli. A propos de l’interprétation géométrique du problème du scrutin. L ensiegnement mathématique, 23:328–329, 1923.

[3]   A. Aeppli. Zur Theorie verketter Wahrscheinlichkeitem Markoffsche Ketten höherer Ordnung. PhD thesis, Eidgenössiche Technische Hochschule, Zürich, 1924.

[4]   Désiré André. Solution directe du problème rèsolu par m. bertrand. Comptes Rendus des Scéances de l’Académie des Sciences, Paris, 105:436–437, 1887.

[5]   J. Bertrand. Solution de une problème. Comptes Rendus des Scéances de l’Académie des Sciences, Paris, 105:369, 1887.

[6]   J. Bertrand. Calcul des Probabilités. Chelsea Pub., 3rd edition, 1972.

[7]   L. Comtet. Advanced Combinatorics, the Art of Finite and Infinite Expansions. D. Reidel, Dordrecht and Boston, 1974.

[8]   J. L. Doob. Stochastic Processes. John Wiley, New York, 1953.

[9]   A. Dvoretzky and Th. Motzkin. A problem of arrangements. Duke Mathematics Journal, 14:305–313, 1947.

[10]   Émile Barbier. Généralisation du problème résolu par M. J. Bertrand. Comptes Rendus des Scéances de l’Académie des Sciences, Paris, 105:407, 1887.

[11]   William Feller. An Introduction to Probability Theory and Its Applications, Volume I, volume I. John Wiley and Sons, third edition, 1973. QA 273 F3712.

[12]   I. P. Goulden and I. G. Serrano. Maintaining the spirit of the reflection pricniple when the boundary line has arbitrary integer slope. Journal Combinatorial Theory, Series A, 104:317–326, 2003.

[13]   Geoffrey Grimmett and David Stirzaker. Probability and Random Processes. Oxford University Press, 2001.

[14]   Wouter Kager. The hitting time theorem revisited. The American Mathematical Monthly, 118(8):735–737, October 2011. http://dx/doi.org/10.4169/amer.math.mothly.118.08.735.

[15]   Emmanuel Lesigne. Heads or Tails: An Introduction to Limit Theorems in Probability, volume 28 of Student Mathematical Library. American Mathematical Society, 2005.

[16]   D. Mirimanoff. A propos de l’interprétation géoemétrique du probleme du scrutin. L’enseignement mathématique, 23:187–189, 1923.

[17]   Marc Renault. Four proofs of the ballot theorem. Mathematics Magazine, 80(5):345–352, December 2007.

[18]   Marc Renault. Lost (and found) in translation: André’s Actual method and its application to the generalized ballot problem. American Mathematical Monthly, 115(4):358–363, April 2008. ballot problem, reflection principle.

[19]   L. Takács. On the ballot theorems. In Advances in Combinatorial Methods and Applications to Probabilty and Statistics. Birkhäuser, 1997.

[20]   J. V. Uspensky. Introduction to Mathematical Probability. McGraw-Hill, New York and London, 1937.

[21]   Remco van der Hofstad and Michael Keane. An elementary proof of the hitting time theorem. The American Mathematical Monthly, 115(8):753–756, October 2008.

[22]   W. A. Whitworth. Arrangements of m things of one sort and n things of another sort under certain conditions of priority. Messenger of Math, 8:015–114, 1878. http://www.archive.org/details/messengermathem04glaigoog.

[23]   W. Woan. Uniform partitions of lattice paths and Chung-Feller generalizations. American Mathematical Monthly, 108:556–559, 2001.

[24]   A. M. Yaglom and I. M. Yaglom. Challenging Mathematical Problems with Elementary Solutions. Holden-Day, Inc., San Francisco, London, Amsterdam, 1964.

__________________________________________________________________________

Links

Outside Readings and Links:

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable effort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reflects the thoughts, interests and opinions of its author. They do not explicitly represent official positions or policies of my employer.

Information on this website is subject to change without notice.

Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1

Email to Steve Dunbar, sdunbar1 at unl dot edu

Last modified: Processed from LATEX source on December 31, 2013