Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
Probability Theory and Stochastic Processes
Steven R. Dunbar
The Ballot Theorem and the Reﬂection Principle
Mathematicians Only: prolonged scenes of intense rigor.
Suppose that in an election candidate A receives votes and candidate B receives 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?
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 Reﬂection 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 Reﬂection Principle for Bernoulli random walks. In later sections the Reﬂection Principle is a tool in the proof of the Arcsine Law for binomial random variables.
Deﬁnition. Bertrand’s Ballot Problem is the following combinatorial problem: Suppose that in an election, candidate A receives votes and candidate B receives votes, where for some positive integer . In how many ways can the ballots be ordered so that A maintains more than times as many votes as B throughout the counting of the ballots?
Deﬁnition. More strictly, the Ballot Theorem when is called the strict Ballot Problem and for called the generalized Ballot Problem.
The solution of both problems is:
Theorem 1 (Ballot Theorem). Suppose that in an election, candidate A receives votes and candidate B receives votes, where for some positive integer . The number of ways the ballots can be ordered so that A maintains more than times as many votes as B throughout the counting of the ballots is
The history of the Ballot Problem is tangled. Renault  gives a brief history of the Ballot Problem with four proofs. Takás  gives a complete historical account of the development of ballot theorems with several proofs of the Ballot Theorem. Kager , van der Hofstad and Keane , and Grimmett and Stirzaker  all cite Whitworth  with a priority arrangement version in 1878. However, the Ballot Problem in its usual form is credited to Bertrand . In 1887 Joseph Bertrand introduced the Ballot Problem for , 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  stated a solution to the ballot problem for arbitrary , but without any proof. Still in the same year (and only 29 pages later yet in the same journal) Désiré André  produced a short combinatorial proof of the Ballot Problem for . In 1923, Aeppli  gave the ﬁrst proof of the Ballot Theorem for in his Ph. D. thesis, . Takás  includes the original proofs by André and Aeppli.
According to Renault  many sources cite André  claiming that he used the “Reﬂection Principle” to solve Bertrand’s Ballot Problem. It is not strictly accurate to say that André employed the Reﬂection Method in his proof. The “Reﬂection Principle” is a variation of André’s method of proof. Bertrand’s textbook on probability , ﬁrst published in 1888, solves the Ballot Problem exactly as André did. Comtet  formulated the “Reﬂection Principle”, stating that it is essentially “due to André”. In the following years, many other minor variations appeared (see  for references).
In 1923 Aebly  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]). Mirimanoﬀ  (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, Mirimanoﬀ’s method is exactly the reﬂection method we know today. When did authors start claiming that André actually used the reﬂection method in his solution? This is more diﬃcult to ascertain. In 1947 Dvoretzky and Motzkin  introduced a new method of proof to the Ballot Problem and its generalization. They accurately describe André’s contribution, making no mention of the Reﬂection 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 diﬀerent proofs in reality use the reﬂection principle …” suggesting, perhaps, that the reﬂection method was the original method of solution. Feller, four pages later, states the reﬂection principle and makes the footnote, “The probability literature attributes this method to D. André, (1887).” The ﬁrst edition of Feller’s book (1950) mentions neither André nor the Reﬂection Principle. The earliest source that Renault could ﬁnd linking André and the Reﬂection 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 reﬂection principle of Désiré André.” These early sources do not explicitly state that André used the reﬂection method in his own proof, but this could be inferred, and other writers since then have naturally assumed that André did indeed use the reﬂection method.
Proof (Generalized Ballot Theorem by Induction). Let denote the number of ways the ballots () can be ordered so that candidate A maintains more than times as many votes as B throughout the counting of the ballots. The conditions for all and for all are easily veriﬁed by considering the statement of the ballot problem, and they both satisfy
For and , note that by considering the last vote in a ballot permutation. By induction, this quantity is
which simpliﬁes to
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 Reﬂection Principle is a popular proof because it is easy, visual, and it has generalizations beyond ballot counting to random walks and Brownian Motion. Feller  gives an account of the Reﬂection Principle.
Visualize ballot permutations as lattice paths in the Euclidean plane with votes for A as upsteps with vector and votes for B as downsteps with vector . See Figure 1. Call ballot permutations (or paths) that satisfy the ballot problem “good”, and call those that do not “bad.”
Deﬁnition. The Reﬂection Principle is that the set of paths from to that do touch the -axis somewhere is in one-to-one correspondence with the set of all paths from to .
Proof (Strict Ballot Theorem by the Reﬂection Principle). The terminal point of the path is . Since every good path must start with an upstep, there are as many good paths as there are paths from to that never touch the -axis.
The claim is that the set of paths from to that do touch the -axis somewhere is in one-to-one correspondence with the set of all paths from to . The claim is established by reﬂecting across the -axis the initial segment of the path that ends with the step that ﬁrst touches the -axis. Subtracting the number of these paths from the number of all paths from to produces the number of good paths:
André was the ﬁrst 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 Reﬂection Principle. However, whereas the Reﬂection Principle modiﬁes 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 ballots are marked “A” and ballots are marked “B”. He ﬁrst notes that every ballot permutation starting with a “B” is bad and there are 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 .
“The number of possible outcomes is obviously the number of permutations one can form with letters A and letters B. Let 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 letters A and 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 letters A and letters B. This rule is composed of two parts:
It results from all the above that the total number of unfavorable outcomes is twice the number of permutations one can form with letters A and letters B.”
Thus André establishes a one-to-one correspondence between the bad ballot permutations starting with “A” and all permutations consisting of “A’s” and “B’s”. There are of these. The number of bad ballot permutations is . The ballot theorem then follows by simplifying
Example. Consider an example with votes, for A and for B. There are possible vote count patterns, of which are bad. There are unfavorable permutations starting with B.
|ABAAAB||Bad||Starts with A||A B AAAB||AAABA|
|BAAAAB||Bad||Suppress initial B||AA AAB||AABBAA|
|ABAABA||Bad||Starts with A||A B AABA||AABAA|
|BAAABA||Bad||Suppress initial B||AA ABA||ABABAA|
|AABBAA||Bad||Starts with A||AAB B AA||AAAAB|
|ABABAA||Bad||Starts with A||A B ABAA||ABAAA|
|BAABAA||Bad||Suppress initial B||AA BAA||BAABAA|
|ABBAAA||Bad||Starts with A||A B BAAA||BAAAA|
|BABAAA||Bad||Starts with B||ABA AA||AABABA|
|BBAAAA||Bad||Starts with B||BAA AA||AABBAA|
This proof for the Generalized Ballot Problem uses the lattice path idea from the Reﬂection Principle proof. In the Generalized Ballot Problem, votes for A are upsteps , votes for B are downsteps . We wish to ﬁnd the number of lattice paths starting at the origin and consisting of upsteps and downsteps such that no step ends on or below the -axis. The diﬃculty in generalizing the Reﬂection Principle is that when one reﬂects such a lattice path, the result does not have the required types of upsteps and downsteps. Goulden and Serrano  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 reﬂection principle.” They go on to provide a proof that rotates the initial path segment by ; even so, they acknowledge that their proof does not specialize to the Reﬂection Principle when . (As a side note, rotating a path is equivalent to writing a ballot permutation in reverse order. Uspensky  used this principle to solve the Ballot Problem in 1937.)
Proof (Generalized Ballot Theorem). For , let denote the set of bad paths whose ﬁrst bad step ends units below the -axis. Note that the paths in necessarily start with a downstep. Clearly these sets are disjoint and their union is the set of all bad paths. Let be the set of all paths consisting of upsteps and downsteps, without regard to location in the plane; . We prove that for each in the range by providing a one-to-one correspondence between and .
Given a path write where is the ﬁrst downstep that ends on or below the -axis (note that is empty if ). The path is then uniquely determined and is an element of . Given a path , scan the path from right to left until a vertex is found lying units below the terminal vertex of (note that this vertex is the terminal vertex of itself if ). Such a vertex must exist since the initial vertex of lies more than units below the terminal vertex of because so . Write , where and are the paths joined at that vertex. Construct path by interchanging and and inserting a downstep between them. Translating to start at , the path touches the -axis only at the origin, and ends units below the -axis; hence . Therefore, the number of good paths is
Proof (Alternative Proof to Generalized Ballot Theorem). An alternate formulation of the proof: For , let denote the set of bad paths whose ﬁrst bad step ends units below the -axis. Clearly these sets are disjoint and their union is the set of all bad paths. Notice that the paths in are exactly those paths that start with a downstep, and so . We now show that for any we actually have . Let be a path in , (), and identify the ﬁrst step of that ends units below the -axis. Let be the initial segment of that ends with that step and write . Let denote the path that results from rotating by , exchanging its endpoints; see Figure ??. Since ends with a downstep, starts with a downstep, and consequently .
The same process converts a path in into a path in , (). If , then identify the ﬁrst step that ends units below the -axis. Let denote the initial segment of that ends with that step and write . Since necessarily ends with an upstep, we have .
Therefore, the number of good paths is
Proof (Generalized Ballot Theorem by the Cycle Lemma). A ballot permutation is a sequence of terms where each term is either or ; votes for A correspond to the ’s and votes for B correspond to the ’s. A sequence is called good if every partial sum is positive, and bad otherwise. Observe that the sum of a sequence is . Let be any circular arrangement of ’s and ’s. Now prove the Cycle Lemma: of the terms in , exactly start good sequences when is read once around clockwise.
The claim is now that there must exist a sequence in with consecutive ’s. Suppose not, that is, there is a placement of ’s around the circle with at most ’s between each . Then the total number of ’s around the circular arrangement is at most . But which is not possible, so the claim is true.
No term of can start a good sequence, because the partial sum would be less than or equal to zero at the term.
Let be the circular arrangement created from by removing . Then has terms of ’s and terms of ’s. Note that so satisﬁes the same hypotheses as . Furthermore, since the sequence has sum , it has no “net eﬀect” on good sequences. Thus, a term of starts a good sequence if and only if the corresponding term in starts a good sequence. Consequently, and have exactly the same number of terms that start good sequences. See Figure 5. Continuing in this manner, one removes sequences of the form until a circular arrangement consisting only of ’s remains. At this stage, there are ’s, and every term starts a good sequence. Hence there are exactly good sequences in , and the Cycle Lemma is proved. If there is periodicity in then not all good sequences will be distinct. However, we can conclude that the ratio of good sequences to all sequences is to . Therefore, the number of good paths is
Remark. The Cycle Lemma provides a surprising result: for any ballot sequence of votes for A and votes for B, exactly of the cyclic permutations of the sequence are good. Consequently, a fraction of all ballot permutations are good.
Remark. As an overview, the following proof considers a set with elements, and partitions this set into subsets of equal size. This is called a uniform partition into subsets. One of the subsets corresponds to the set of good ballot permutations, and from this the ballot theorem follows. The proof is from  and extends the proofs in .
Proof (Generalized Ballot Theorem by Uniform Partition). Consider lattice paths starting from the origin and consisting of upsteps with vector and downsteps with vector , and assume the strict inequality . Let be the set of all such paths. Given path we let denote the set of -values of the “rightmost lowest” vertices of ; see Figure 6. More precisely, given path , let denote the least -value of all the vertices of , and let denote the -value of the rightmost vertex of along the line ; then .
Let and note that . Let , deﬁned for . The sets partition into disjoint subsets.
The two claims above imply that the number of good paths in is
Remark. Suppose we let denote the set of paths for which is among the -values of the rightmost vertices, i.e., . When , the sets are disjoint and all have the same cardinality. In other words, partitioning according to the -value of a path’s rightmost lowest vertex creates a uniform partition of . When , the sets continue to have the same cardinality. However the are no longer disjoint. To the contrary, each path in will be a member of precisely of these sets.
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 modiﬁes their proof to this “up-and-down” random walk representation and shortens the explanation.
Rotation and Shadowing. Consider any particular arrangement of the ballots in a list. From this list we can obtain new lists as follows: move the ﬁrst ballot from the front of the list to the last place, thus creating a new arrangement in which the second, third, …, and th ballot of the original list are now one place forward. Then repeat the process. By repeating the process, we obtain a total of new lists, adding to this the original list, we have a total of arrangements. We will show that of these arrangements are good. Then the total number of arrangements is
To represent all rotated arrangements obtained from a particular arrangement, adjoin to the end 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 . Now the rotated arrangements correspond to the paths which consist of the subpaths that start respectively at and consequently end at the points . Good arrangements correspond to paths of length in which every vertex other than the ﬁrst is preceded by more upsteps with vector than downsteps with vector , 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 That is, the base point does not lie in the shadow thrown by some downsteps. (Note that if the does not lie in the shade of the path , then cannot lie in the shade thrown by the steps from to either. This follows from the fact that the path to is a duplicate of ). Thus we only have to count how many of the points are illuminated by the parallel rays.
Of the points, the only ones which have a chance of being illuminated are the points which correspond to an upstep with vector . But even such a point may lie in the shade cast by a later upstep. For example, in Figure 7, and lie in the shade cast by .
Denote by the number of downsteps of which cast their shadows to the left, i. e. segments like and in Figure 7. Then the other downsteps cast their shadows on upsteps. Since , , , …, is a replica of , , , …, , exactly downsteps of , , , …, cast their shadows to the left of . These shadows fall on upsteps to the left of . These shadows fall on upsteps of ; hence there are altogether upsteps in the shade. Thus, of the points which have a chance of being illuminated, exactly are removed by virtue of the shadow cast on the segment . Hence there remain illuminated points of . For example, in Figure 7, , and exactly are illuminated. This proves that for exactly of the arrangements of ballot counts obtained from any one arrangement by rotation satisfy the requirements of the Ballot Theorem.
Note that the arrangements obtained from a single one by rotations are not necessarily all distinct. If and are not relatively prime, then it may happen that an arrangement may consist of parts which are repetitions. For example, with and , an arrangement may be . In such a case, the rotations will result in arrangements which are repeated the same number of times. In the example, among the arrangements from rotations, there are arrangements, each repeated times.
In any case, the ratio of the number of good arrangements to the total number of arrangements is
Therefore, the number of possible good arrangements is
Remark. The proof by rotation and shadowing is another proof of the Cycle Lemma.
Remark. This rotation and shadowing proof can be modiﬁed for the generalized ballot theorem. The parallel rays are not horizontal, but come at an angle to the axis. See [24, pages 179-182].
The ballot problem is often stated in a “weak” version: suppose that candidate A receives votes and candidate B receives votes, where for some positive integer , and compute the number of ways the ballots can be ordered so that A always has at least times as many votes as B throughout the counting of the ballots.
Any ballot permutation in which A maintains at least times the number of votes for B can be converted into one in which A maintains more than 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 votes and B receives votes:
Putting and produces the Catalan numbers:
This section is adapted from Renault,  and . The Reﬂection Principle is adapted from . Some the history is also adapted from . The rotation and shadowing proof is adapted from . Some of the problems are from .
For the generalized ballot problem, set the size of a downstep , the number of ballots for A and the number of ballots for B. Then the total number of ballots is the length . There are then 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 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 . For each of the ballot counts, ﬁnd the minimum value . Then create a block matrix of size with blocks of size . Fill each block with the coordinates of the points corresponding to the values . Save the matrix for later plotting or analysis.
Note that this algorithm does not scale well because of the inherent growth of the binomial coeﬃcients.
Octave script for uniform partitions.
GnuPlot script for uniform partitions.
Explain why this is the same as the previous problem.
 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, reﬂection principle.
 W. A. Whitworth. Arrangements of things of one sort and things of another sort under certain conditions of priority. Messenger of Math, 8:015–114, 1878. http://www.archive.org/details/messengermathem04glaigoog.
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 eﬀort 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 reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial 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 modiﬁed: Processed from LATEX source on December 31, 2013