Steven R. Dunbar
Department of Mathematics
203 Avery Hall
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 Reﬂection 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

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________ ### 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

1. Suppose that in an election, candidate A receives $a$ votes and candidate B receives $b$ votes, where $a\ge 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
$\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

2. The Reﬂection 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 $\left(a-kb\right)∕\left(a+b\right)$ of all ballot permutations are good.

__________________________________________________________________________ ### 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\ge 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 Reﬂection Principle is that the set of paths from $\left(1,1\right)$ to $\left(a+b,a-b\right)$ that do touch the $x$-axis somewhere is in one-to-one correspondence with the set of all paths from $\left(1,-1\right)$ to $\left(a+b,a-b\right)$.
3. A partition of a set into subsets of equal size is called a uniform partition.

__________________________________________________________________________ ### 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 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.

#### Introduction and History

Deﬁnition. 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\ge 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?

Deﬁnition. More strictly, the Ballot Theorem when $k=1$ is called the strict Ballot Problem and for $k\ge 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\ge 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

$\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

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 $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  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é  produced a short combinatorial proof of the Ballot Problem for $k=1$. In 1923, Aeppli  gave the ﬁrst proof of the Ballot Theorem for $k\ge 1$ 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 by Induction

Proof (Generalized Ballot Theorem by Induction). Let ${N}_{k}\left(a,b\right)$ denote the number of ways the $a+b$ ballots ($a\ge 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 ${N}_{k}\left(a,0\right)=1$ for all $a>0$ and ${N}_{k}\left(kb,b\right)=0$ for all $b>0$ are easily veriﬁed by considering the statement of the ballot problem, and they both satisfy

${N}_{k}\left(a,b\right)=\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

For $b>0$ and $a>kb$, note that ${N}_{k}\left(a,b\right)={N}_{k}\left(a,b-1\right)+{N}_{k}\left(a-1,b\right)$ by considering the last vote in a ballot permutation. By induction, this quantity is

$\frac{a-k\left(b-1\right)}{a+b-1}\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)+\frac{a-1-kb}{a+b-1}\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a-1}\right)$

which simpliﬁes to

$\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)$

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

#### The Reﬂection Principle

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 $\left(1,1\right)$ and votes for B as downsteps with vector $\left(1,-1\right)$. 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 $\left(1,1\right)$ to $\left(a+b,a-b\right)$ that do touch the $x$-axis somewhere is in one-to-one correspondence with the set of all paths from $\left(1,-1\right)$ to $\left(a+b,a-b\right)$.

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

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

$\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a-1}\right)-2\left(\genfrac{}{}{0.0pt}{}{a+b-1}{b-1}\right)=\frac{a-b}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)$ Figure 1: Example of the Reﬂection Principle with $a=4$, $b=4$

#### André’s Original Proof

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 $a$ ballots are marked “A” and $b$ ballots are marked “B”. He ﬁrst notes that every ballot permutation starting with a “B” is bad and there are $\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)$ 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 $a$ letters A and $b$ letters B. Let $Q\left(a,b\right)$ 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 ﬁrst 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 ﬁve letters A and three letters B; by removing the ﬁrst B that violates the law, one separates two groups AAB, ABAA; by exchanging these groups, one obtains the permutation ABAAAAB, formed of ﬁve letters A and two letters B. (See Figure 2.)  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 $\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)$ of these. The number of bad ballot permutations is $2\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)$. The ballot theorem then follows by simplifying

$\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)-2\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)=\frac{a-b}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

Example. Consider an example with $6$ votes, $4$ for A and $2$ for B. There are $\left(\genfrac{}{}{0.0pt}{}{6}{4}\right)=15$ possible vote count patterns, of which $2\left(\genfrac{}{}{0.0pt}{}{5}{4}\right)=10$ are bad. There are $\left(\genfrac{}{}{0.0pt}{}{5}{4}\right)=5$ unfavorable permutations starting with B.

 Ballots Type Start Partition Rearrangement AAAABB Good AAABAB Good AABAAB Good ABAAAB Bad Starts with A A B AAAB AAABA BAAAAB Bad Suppress initial B AA AAB AABBAA AAABBA Good AABABA Good 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

#### Proof for the Generalized Ballot Problem

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 $\left(1,1\right)$, votes for B are downsteps $\left(1,-k\right)$. We wish to ﬁnd the number of lattice paths starting at the origin and consisting of $a$ upsteps $\left(1,1\right)$ and $b$ downsteps $\left(1,-k\right)$ such that no step ends on or below the $x$-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 $18{0}^{\circ }$; even so, they acknowledge that their proof does not specialize to the Reﬂection Principle when $k=1$. (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 $0\le i\le k$, let ${\mathsc{ℬ}}_{i}$ denote the set of bad paths whose ﬁrst bad step ends $i$ units below the $x$-axis. Note that the paths in ${\mathsc{ℬ}}_{k}$ necessarily start with a downstep. Clearly these $k+1$ sets are disjoint and their union is the set of all bad paths. Let $\mathsc{𝒜}$ be the set of all paths consisting of $a$ upsteps and $b-1$ downsteps, without regard to location in the plane; $|\mathsc{𝒜}|=\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)$. We prove that $|{\mathsc{ℬ}}_{i}|=|\mathsc{𝒜}|$ for each $i$ in the range $0\le i\le k$ by providing a one-to-one correspondence between ${\mathsc{ℬ}}_{i}$ and $\mathsc{𝒜}$.  Figure 3: Example with $k=3$, $XDY\in {\mathsc{ℬ}}_{1}$, and $YX\in \mathsc{𝒜}$.

Given a path $P\in {\mathsc{ℬ}}_{i}$ write $P=XDY$ where $D$ is the ﬁrst downstep that ends on or below the $x$-axis (note that $X$ is empty if $i=k$). The path $YX$ is then uniquely determined and is an element of $\mathsc{𝒜}$. Given a path $Q\in \mathsc{𝒜}$, 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\ge 0$ so $a-k\left(b-1\right)\ge k$. Write $Q=YX$, 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 $\left(0,0\right)$, the path touches the $x$-axis only at the origin, and $XD$ ends $i$ units below the $x$-axis; hence $P\in {\mathsc{ℬ}}_{i}$. Therefore, the number of good paths is

$\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)-\left(k+1\right)\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)=\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

Proof (Alternative Proof to Generalized Ballot Theorem). An alternate formulation of the proof: For $0\le i\le k$, let ${\mathsc{ℬ}}_{i}$ denote the set of bad paths whose ﬁrst 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 ${\mathsc{ℬ}}_{k}$ are exactly those paths that start with a downstep, and so $|{\mathsc{ℬ}}_{k}|=\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)$. We now show that for any $i\ne k$ we actually have $|{\mathsc{ℬ}}_{i}|=|{\mathsc{ℬ}}_{k}|$. Let $P$ be a path in ${\mathsc{ℬ}}_{i}$, ($i\ne k$), and identify the ﬁrst 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 $\stackrel{̃}{X}$ denote the path that results from rotating $X$ by $18{0}^{\circ }$, exchanging its endpoints; see Figure ??. Since $X$ ends with a downstep, $\stackrel{̃}{X}$ starts with a downstep, and consequently $\stackrel{̃}{X}Y\in {\mathsc{ℬ}}_{k}$. Figure 4: Rotation of $X$ by $18{0}^{\circ }$, exchanging the endpoints.

The same process converts a path in ${\mathsc{ℬ}}_{k}$ into a path in ${\mathsc{ℬ}}_{i}$, ($i\ne k$). If $P\in {\mathsc{ℬ}}_{k}$, then identify the ﬁrst 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 $\stackrel{̃}{X}Y\in {\mathsc{ℬ}}_{i}$.

Therefore, the number of good paths is

$\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)-\left(k+1\right)\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)=\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

#### 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\ge 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,\dots ,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 $\left(k-1\right)b$. But $\left(k-1\right)b 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. Figure 5: Example of $C$ and ${C}^{\prime }$ with $a=8$, $b=2$, $k=3$.

Let ${C}^{\prime }$ be the circular arrangement created from $C$ by removing $X$. Then ${C}^{\prime }$ has ${a}^{\prime }=a-k$ terms of $1$’s and ${b}^{\prime }=b-1$ terms of $-k$’s. Note that ${a}^{\prime }-k{b}^{\prime }=a-k-k\left(b-1\right)=a-kb\ge 0$ so ${C}^{\prime }$ satisﬁes the same hypotheses as $C$. Furthermore, since the sequence $X$ has sum $0$, it has no “net eﬀect” on good sequences. Thus, a term of ${C}^{\prime }$ starts a good sequence if and only if the corresponding term in $C$ starts a good sequence. Consequently, ${C}^{\prime }$ 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,\dots ,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

$\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

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 $\left(a-kb\right)∕\left(a+b\right)$ of all ballot permutations are good.

#### Proof by Uniform Partition

Remark. As an overview, the following proof considers a set with $\left(a-kb\right)\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)$ 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  and extends the proofs in .

Proof (Generalized Ballot Theorem by Uniform Partition). Consider lattice paths starting from the origin and consisting of $a$ upsteps with vector $\left(1,1\right)$ and $b$ downsteps with vector $\left(1,-k\right)$, and assume the strict inequality $a>kb$. Let $\mathsc{𝒜}=\mathsc{𝒜}\left(a,b,k\right)$ be the set of all such paths. Given path $P\in \mathsc{𝒜}$ we let $L\left(P\right)$ denote the set of $x$-values of the $a-kb$ “rightmost lowest” vertices of $P$; see Figure 6. More precisely, given path $P\in \mathsc{𝒜}$, let ${y}_{0}$ denote the least $y$-value of all the vertices of $P$, and let $r\left(t\right)$ denote the $x$-value of the rightmost vertex of $P$ along the line $y=t$; then $L\left(P\right)=\left\{r\left(t\right)|t\in ℤ,{y}_{0}\le t\le {y}_{0}+\left(a-kb\right)-1\right\}$. Figure 6: Example of uniform partition with $k=2$, $a=6$, $b=2$. For each path $P\in \mathsc{𝒜}$, the path $P$ and the set $L\left(P\right)$, Observe that among all the sets $L\left(P\right)$, each number from $0$ to $7$ occurs exactly $7$ times.

Let $\Psi =\left\{\left(P,j\right)|P\in \mathsc{𝒜},j\in L\left(P\right)\right\}$ and note that $|\Psi |=\left(a-kb\right)|\mathsc{𝒜}|$. Let ${\Omega }_{i}=\left\{\left(P,i\right)\in \Psi |i\in L\left(P\right)\right\}$, deﬁned for $0\le i\le a+b-1$. The sets ${\Omega }_{i}$ partition $\Psi$ into $a+b$ disjoint subsets.

Claim 1
There is a one-to-one correspondence between ${\Omega }_{0}$ and the set of good paths. If $P\in \mathsc{𝒜}$ is good, then $\left(0,0\right)$ is the lowest vertex in $P$ and it is the only vertex on the $x$-axis, so $\left(P,0\right)\in {\Omega }_{0}$. Conversely, if $\left(P,0\right)$ is in ${\Omega }_{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 ${\Omega }_{i}$ uniformly partition $\Psi$. We show this by providing a one-to-one correspondence between ${\Omega }_{i}$ and ${\Omega }_{0}$. If $\left(P,i\right)\in {\Omega }_{i}$, then write $P=XY$ where $X$ is the initial path of $P$ consisting of the ﬁrst $i$ steps, and $Y$ consists of the remaining steps. Since $i\in L\left(P\right)$, 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 $YX$ is good and $\left(YX,0\right)\in {\Omega }_{0}$. Conversely, if $\left(Q,0\right)\in {\Omega }_{0}$, then write $Q=YX$ where $X$ consists of the ﬁnal $i$ steps of $Q$. The same qualities of $X$ and $Y$ hold as noted above, and the pair $\left(XY,i\right)\in i$.

The two claims above imply that the number of good paths in $\mathsc{𝒜}$ is

$|{\Omega }_{0}|=\frac{|\Psi |}{a+b}=\frac{\left(a-kb\right)|\mathsc{𝒜}|}{a+b}=\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)$

Remark. Suppose we let ${\mathsc{𝒜}}_{i}$ denote the set of paths for which $i$ is among the $x$-values of the $a-kb$ rightmost vertices, i.e., $\mathsc{𝒜}i=\left\{P\in \mathsc{𝒜}|i\in L\left(P\right)\right\}$. When $a-kb=1$, the sets ${\mathsc{𝒜}}_{0},{\mathsc{𝒜}}_{1},\dots ,{\mathsc{𝒜}}_{a+b-1}$ are disjoint and all have the same cardinality. In other words, partitioning $\mathsc{𝒜}$ according to the $x$-value of a path’s rightmost lowest vertex creates a uniform partition of $\mathsc{𝒜}$. When $a-kb\ge 1$, the sets ${\mathsc{𝒜}}_{i}$ continue to have the same cardinality. However the ${\mathsc{𝒜}}_{i}$ are no longer disjoint. To the contrary, each path in $\mathsc{𝒜}$ 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 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 $a+b$ ballots in a list. From this list we can obtain $a+b-1$ 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 $a+b$th 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

$\frac{a-b}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

To represent all $a+b$ rotated arrangements obtained from a particular arrangement, adjoin to the end $\left(a+b,{A}_{a+b}\right)$ 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 ${A}_{0},{A}_{1},{A}_{2},\dots ,{A}_{a+b},{A}_{a+b+1},\dots ,{A}_{2a+2b}$. Now the $a+b$ rotated arrangements correspond to the paths which consist of the subpaths that start respectively at ${A}_{0},{A}_{1},\dots ,{A}_{a+b-1}$ and consequently end at the points ${A}_{a+b},{A}_{a+b+1},\dots ,{A}_{2a+2b}$. Good arrangements correspond to paths of length $a+b$ in which every vertex other than the ﬁrst is preceded by more upsteps with vector $\left(1,1\right)$ than downsteps with vector $\left(1,-1\right)$, 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 ${A}_{k}$ That is, the base point does not lie in the shadow thrown by some downsteps. (Note that if the ${A}_{k}$ does not lie in the shade of the path ${A}_{k}{A}_{k+1}{A}_{k+2}\dots {A}_{k+a+b}$, then ${A}_{k}$ cannot lie in the shade thrown by the steps from ${A}_{a+b+k}$ to ${A}_{2a+2b}$ either. This follows from the fact that the path ${A}_{a+b+k}$ to ${A}_{2a+2b}$ is a duplicate of ${A}_{k}{A}_{k+1}\dots {A}_{a+b}$ ). Thus we only have to count how many of the points ${A}_{0},{A}_{1},{A}_{2},\dots ,{A}_{a+b}$ are illuminated by the parallel rays.

Of the points, ${A}_{0},{A}_{1},{A}_{2},\dots ,{A}_{a+b-1}$ the only ones which have a chance of being illuminated are the $a$ points which correspond to an upstep with vector $\left(1,1\right)$. But even such a point may lie in the shade cast by a later upstep. For example, in Figure 7, ${A}_{5}$ and ${A}_{7}$ lie in the shade cast by ${A}_{9}$. 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 ${A}_{0},{A}_{1},{A}_{2},\dots ,{A}_{a+b}$ which cast their shadows to the left, i. e. segments like ${A}_{0}{A}_{1}$ and ${A}_{1}{A}_{2}$ in Figure 7. Then the other $b-d$ downsteps cast their shadows on upsteps. Since ${A}_{a+b}$, ${A}_{a+b+1}$, ${A}_{a+b+2}$, …, ${A}_{2a+2b}$ is a replica of ${A}_{0}$, ${A}_{1}$ , ${A}_{2}$, …, ${A}_{a+b-1}$, exactly $d$ downsteps of ${A}_{a+b}$, ${A}_{a+b+1}$, ${A}_{a+b+2}$, …, ${A}_{2a+2b}$ cast their shadows to the left of ${A}_{a+b}$. These shadows fall on upsteps to the left of ${A}_{a+b}$. These shadows fall on upsteps of ${A}_{0},{A}_{1},{A}_{2},\dots ,{A}_{a+b}$; hence there are altogether $b-d+d=b$ upsteps in the shade. Thus, of the $a$ points ${A}_{i}$ which have a chance of being illuminated, exactly $b$ are removed by virtue of the shadow cast on the segment ${A}_{i}{A}_{i+1}$. Hence there remain $a-b$ illuminated points of ${A}_{0},{A}_{1},{A}_{2},\dots ,{A}_{a+b-1}$. 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

$\frac{a-b}{a+b}.$

Therefore, the number of possible good arrangements is

$\frac{a-b}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

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].

#### 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\ge 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:

$\frac{\left(m+1\right)-kn}{\left(m+1\right)+n}\left(\genfrac{}{}{0.0pt}{}{\left(m+1\right)+n}{m+1}\right)=\frac{m+1-kn}{m+1}\left(\genfrac{}{}{0.0pt}{}{m+n}{m}\right).$

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

${C}_{n}=\frac{1}{n+1}\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right).$

#### Sources

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 .

_______________________________________________________________________________________________ ### 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 $\left(\genfrac{}{}{0.0pt}{}{a+b}{a-b}\right)$ 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 $\left(a+b\right)×\left(\genfrac{}{}{0.0pt}{}{a+b}{a-b}\right)$ 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 $\left(\genfrac{}{}{0.0pt}{}{a+b}{a-b}\right)$ ballot counts, ﬁnd the minimum value ${y}_{0}$. Then create a block matrix of size $\left(a-kb\right)×\left(a-kb\right)\left(\genfrac{}{}{0.0pt}{}{a+b}{a-b}\right)$ with blocks of size $\left(a-kb\right)×\left(a-kb\right)$. Fill each block with the coordinates of the points corresponding to the values $L\left(P\right)=\left\{r\left(t\right)|t\in Z,{y}_{0}\le t\le {y}_{0}+\left(a-kb\right)-1\right\}$. 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.

#### Scripts

Octave
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
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 for Understanding

1. Do the calculations to show
$\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a-1}\right)-2\left(\genfrac{}{}{0.0pt}{}{a+b-1}{b-1}\right)=\frac{a-b}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)$

2. Do the calculations to show
$\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)-2\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)=\frac{a-b}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

Explain why this is the same as the previous problem.

3. Do the calculations to show
$\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)-\left(k+1\right)\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)=\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right).$

4. Do the calculations to show
$\frac{a-k\left(b-1\right)}{a+b-1}\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)+\frac{a-1-kb}{a+b-1}\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a-1}\right)$

simpliﬁes to

$\frac{a-kb}{a+b}\left(\genfrac{}{}{0.0pt}{}{a+b}{a}\right)$

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 oﬃce; $n$ of them have only ﬁve-dollar bills and the other $m$ have only ten-dollar bills with nothing smaller. The tickets cost $5 each. When the box-oﬃce 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 , problem 83a.) 7. Solve the same problem under the assumption that initially there were $p$ ﬁve-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 oﬃce; $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-oﬃce 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 , 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.

__________________________________________________________________________ ### References

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

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

   A. Aeppli. Zur Theorie verketter Wahrscheinlichkeitem Markoﬀsche Ketten höherer Ordnung. PhD thesis, Eidgenössiche Technische Hochschule, Zürich, 1924.

   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.

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

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

   L. Comtet. Advanced Combinatorics, the Art of Finite and Inﬁnite Expansions. D. Reidel, Dordrecht and Boston, 1974.

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

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

   É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.

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

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

   Geoﬀrey Grimmett and David Stirzaker. Probability and Random Processes. Oxford University Press, 2001.

   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.

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

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

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

   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.

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

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

   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.

   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.

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

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

__________________________________________________________________________ __________________________________________________________________________

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.