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 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.
_______________________________________________________________________________________________
Mathematicians Only: prolonged scenes of intense rigor.
_______________________________________________________________________________________________
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?
_______________________________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
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 $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
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 ﬁrst proof of the Ballot Theorem for $k\ge 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 “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 [6], ﬁrst published in 1888, solves the Ballot Problem exactly as André did. Comtet [7] formulated the “Reﬂection 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]). Mirimanoﬀ [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, 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 [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 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 ${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
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
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 [11] 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:
□
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 [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\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:
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
□
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 |
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 [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 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 [20] used this principle to solve the Ballot Problem in 1937.)
Proof (Generalized Ballot Theorem). For $0\le i\le k$, let ${\mathcal{\mathcal{B}}}_{i}$ denote the set of bad paths whose ﬁrst bad step ends $i$ units below the $x$-axis. Note that the paths in ${\mathcal{\mathcal{B}}}_{k}$ necessarily start with a downstep. Clearly these $k+1$ sets are disjoint and their union is the set of all bad paths. Let $\mathcal{\mathcal{A}}$ be the set of all paths consisting of $a$ upsteps and $b-1$ downsteps, without regard to location in the plane; $\left|\mathcal{\mathcal{A}}\right|=\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)$. We prove that $\left|{\mathcal{\mathcal{B}}}_{i}\right|=\left|\mathcal{\mathcal{A}}\right|$ for each $i$ in the range $0\le i\le k$ by providing a one-to-one correspondence between ${\mathcal{\mathcal{B}}}_{i}$ and $\mathcal{\mathcal{A}}$.
Given a path $P\in {\mathcal{\mathcal{B}}}_{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 $\mathcal{\mathcal{A}}$. Given a path $Q\in \mathcal{\mathcal{A}}$, 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 {\mathcal{\mathcal{B}}}_{i}$. Therefore, the number of good paths is
□
Proof (Alternative Proof to Generalized Ballot Theorem). An alternate formulation of the proof: For $0\le i\le k$, let ${\mathcal{\mathcal{B}}}_{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 ${\mathcal{\mathcal{B}}}_{k}$ are exactly those paths that start with a downstep, and so $\left|{\mathcal{\mathcal{B}}}_{k}\right|=\left(\genfrac{}{}{0.0pt}{}{a+b-1}{a}\right)$. We now show that for any $i\ne k$ we actually have $\left|{\mathcal{\mathcal{B}}}_{i}\right|=\left|{\mathcal{\mathcal{B}}}_{k}\right|$. Let $P$ be a path in ${\mathcal{\mathcal{B}}}_{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{\u0303}{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{\u0303}{X}$ starts with a downstep, and consequently $\stackrel{\u0303}{X}Y\in {\mathcal{\mathcal{B}}}_{k}$.
The same process converts a path in ${\mathcal{\mathcal{B}}}_{k}$ into a path in ${\mathcal{\mathcal{B}}}_{i}$, ($i\ne k$). If $P\in {\mathcal{\mathcal{B}}}_{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{\u0303}{X}Y\in {\mathcal{\mathcal{B}}}_{i}$.
Therefore, the number of good paths is
□
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<kb\le 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.
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
□
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)\u2215\left(a+b\right)$ of all ballot permutations are good.
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 [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 $\left(1,1\right)$ and $b$ downsteps with vector $\left(1,-k\right)$, and assume the strict inequality $a>kb$. Let $\mathcal{\mathcal{A}}=\mathcal{\mathcal{A}}\left(a,b,k\right)$ be the set of all such paths. Given path $P\in \mathcal{\mathcal{A}}$ 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 \mathcal{\mathcal{A}}$, 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 \mathbb{Z},{y}_{0}\le t\le {y}_{0}+\left(a-kb\right)-1\right\}$.
Let $\Psi =\left\{\left(P,j\right)|P\in \mathcal{\mathcal{A}},j\in L\left(P\right)\right\}$ and note that $\left|\Psi \right|=\left(a-kb\right)\left|\mathcal{\mathcal{A}}\right|$. 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.
The two claims above imply that the number of good paths in $\mathcal{\mathcal{A}}$ is
□
Remark. Suppose we let ${\mathcal{\mathcal{A}}}_{i}$ denote the set of paths for which $i$ is among the $x$-values of the $a-kb$ rightmost vertices, i.e., $\mathcal{\mathcal{A}}i=\left\{P\in \mathcal{\mathcal{A}}|i\in L\left(P\right)\right\}$. When $a-kb=1$, the sets ${\mathcal{\mathcal{A}}}_{0},{\mathcal{\mathcal{A}}}_{1},\dots ,{\mathcal{\mathcal{A}}}_{a+b-1}$ are disjoint and all have the same cardinality. In other words, partitioning $\mathcal{\mathcal{A}}$ according to the $x$-value of a path’s rightmost lowest vertex creates a uniform partition of $\mathcal{\mathcal{A}}$. When $a-kb\ge 1$, the sets ${\mathcal{\mathcal{A}}}_{i}$ continue to have the same cardinality. However the ${\mathcal{\mathcal{A}}}_{i}$ are no longer disjoint. To the contrary, each path in $\mathcal{\mathcal{A}}$ will be a member of precisely $a-ykb$ 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 $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
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}$.
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
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 $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:
Putting $k=1$ and $m=n$ produces the Catalan numbers:
This section is adapted from Renault, [17] and [18]. The Reﬂection 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].
_______________________________________________________________________________________________
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)\times \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)\times \left(a-kb\right)\left(\genfrac{}{}{0.0pt}{}{a+b}{a-b}\right)$ with blocks of size $\left(a-kb\right)\times \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.
Octave script for uniform partitions.
GnuPlot script for uniform partitions.
__________________________________________________________________________
Explain why this is the same as the previous problem.
simpliﬁes to
__________________________________________________________________________
[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 Markoﬀsche 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 Inﬁnite 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 reﬂection pricniple when the boundary line has arbitrary integer slope. Journal Combinatorial Theory, Series A, 104:317–326, 2003.
[13] Geoﬀrey 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. Mirimanoﬀ. 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, reﬂection 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.
__________________________________________________________________________
__________________________________________________________________________
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