As a learning exercise, I am trying to understand if it is possible to prove (the famous) Bertrand's Ballot Theorem (https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem) specifically using Generator Functions. I have seen other ways to prove this theorem (e.g. Induction, Reflection) - but I specifically want to see if it is possible to prove this theorem using Generator Functions
Bertrand's Ballot Theorem: In an election where Candidate A has $p$ votes and Candidate B has $q$ votes with $p > q$, the probability that A is ALWAYS ahead in the count is given by $$\frac{(p-q)}{(p+q)}$$
Here is the logic I am using:
Consider a situation where Candidate A receives $p$ votes and Candidate B receives $q$ votes, where $p > q$. We want to count the number of ways this ballot can be arranged such that A is always ahead.
Denote the number of ways to arrange these votes such that Candidate A is always ahead by $B(p, q)$. If $p = q + 1$, there is only one way to arrange the votes (i.e. Candidate A must get the first vote), so $B(p, q) = 1$.
If $p > q + 1$, consider these two cases:
- Case 1: The first vote goes to Candidate A. The remaining votes can be arranged in $B(p-1, q)$ ways.
- Case 2: The first vote goes to Candidate A, the second vote goes to Candidate B. The remaining votes can be arranged in $B(p-1, q-1)$ ways.
This is where I tried (not sure if this is correct) to define the Recurrence Relation: $B(p, q) = B(p-1, q) + B(p-1, q-1)$ for $p > q + 1$
I read online that Generating Function are closely related to Power Series (I don't know why this is). For $B(p, q)$, I thought we could define a 2 Dimensional Power Series:
$$B(x, y) = \sum_{p>q} B(p, q) x^p y^q$$
Using algebraic manipulation, I tried to re-arrange the above relationship to see if I could stumble across any hints that might be useful:
$$B(x, y) = \sum_{p>q} [B(p-1, q) + B(p-1, q-1)] x^p y^q$$
$$B(x, y) = x \sum_{p>q} B(p-1, q) x^{p-1} y^q + xy \sum_{p>q} B(p-1, q-1) x^{p-1} y^{q-1}$$
$$B(x, y) = xB(x, y) + xyB(x, y)$$
From here, I tried to solve for $B(x, y)$:
$$B(x, y) [1-x(1+y)] = 0$$
But I think I am going in circles and not approaching this problem in the wrong way. If $B(x, y) = 0$, this will cancel out all the work I do. And if $[1-x(1+y)] = 0$, I am not sure how I would use this information to continue.
Can someone please help me understand if Bertrand's Ballot Theorem can be proven using Generator Functions?
Thanks!
Betrand's ballot theorem can be proven with generating functions. However, the only proof I know starts a bit differently than yours.
Define $$ b_k(x)=\sum_{n\ge 0} B(n+k,n)x^n $$ So $b_k$ is the generating function for ballot sequences where $A$ has $k$ more votes than $B$.
Lemma 1: For all $k\ge 1$, $$b_k(x)=\big(b_1(x)\big)^k.$$
Proof: Extracting the coefficient of $x^n$ from both sides of the generating function equation to be proved, it suffices to shw the following combinatorial equation: $$ B(n+k,n)=\sum_{n_1+\dots+n_k=n} B(n_1+1,n_1)\cdot B(n_2+1,n_2)\cdots B(n_k+1,n_k) $$ To do this, we show that any ballot sequence where $A$ has $k$ more votes than $B$ can be uniquely decomposed into $k$ ballot sequences where $A$ leads by $1$ vote.
Given a ballot sequence counted by $B(n+k,n)$, define a sequence of indices $t_0,t_1,\dots,t_k$, where for each $i\in \{0,1,\dots,k\}$, $t_i$ is the index of the last ballot for which the running total for $A$ was exactly $i$ votes ahead of $B$. For example, $t_0=0$, while $t_k=(n+k)+n$. It follows that the sequence of votes between $t_i$ and $t_{i+1}$ is a sequence where the running total for $A$ always exceeds that of $B$, and which has one more vote for $A$ than $B$. Therefore, each of the sequence between $t_i$ and $t_{i+1}$ is a ballot path counted by $B(t_{i+1}-t_i+1,t_{i+1}-t_i)$, so the result follows by letting $n_i=t_{i+1}-t_i$.
Lemma 2: $$b_1(x)=1+x \,b_1(x)^2$$
Proof: Extracting the coefficient of $x^n$ from both sides, we must prove that $$ n\ge 1\quad \implies \quad B(n+1,n)=\sum_{n_1+n_2=n-1}B(n_1+1,n_1)\cdot B(n_2+1,n_2) $$ To prove this, let $S$ be a ballot sequence counted by $B(n+1,n)$. Let $t$ be index of the ballot in $S$ where $A$ is one vote ahead of $B$ for the second time. We then decompose $S=S_1+S_2$, where $S_1$ is the prefix of $S$ which ends with vote number $t$, while $S_2$ is everything after. Note that $S_1$ is a ballot sequence. It is not quite true that $S_2$ is a ballot sequence, because $S_2$ has an equal number of $A$ and $B$ votes. However, if you delete the final $B$ vote from $S_2$, the result is a ballot sequence. Therefore, letting $n_1$ be the number of $B$ votes in $S_1$ and $n_2$ be the number of $B$ votes in $S_2$ (minus the last vote), we see $n_1+n_2=n-1$, as claimed. $\tag*{$\square$}$
Theorem: For all $n\ge 0$, $$B(n+k,n)=[x^n]b_k(x)=\frac{k}{2n+k}\binom{2n+k}{n}$$
Let $f(x)=b_1(x)-1$. Lemma $2$ can be rewritten to say $$ \frac{f(x)}{(1+f(x))^2}=x $$ Therefore, letting $g(y)=y/(1+y^2)$, we see that $f(x)$ and $g(y)$ are functional inverses of each other for which $f(0)=g(0)=0$.
Let $H(x)=(1+x)^k$. We have that $$ [x^n]b_k(x)=[x^n]\big(b_1(x)\big)^k=[x^n]\big(1+f(x)\big)^k=[x^n] H(f(x)) $$
To solve this, we use the Lagrange inversion formula, which says that whenever $f,g$ and $H$ are analytic functions such that $f(0)=g(0)=0$ and $f\circ g=g\circ f=x$, that $$ \tag{LIF} [x^n]H(f(x))=\frac1n[x^{-1}] \big(H'(x)\cdot g(x)^{-n}\big) $$ Therefore, applying LIF, we have that for any $n\ge 1$, $$ \begin{align} B(n+k,n) &=[x^n] H(f(x)) \\ &= \frac{1}{n} [x^{-1}] H'(x)\cdot g(x)^{-n} \tag{LIF} \\ &= \frac 1n [x^{-1}] k\cdot (1+x)^{k-1}\cdot x^{-n}(1+x)^{2n} \\ &= \frac kn [x^{n-1}] (1+x)^{2n+k-1} \\ &= \frac kn \binom{2n+k-1}{n-1} \\ &= \frac k{2n+k} \binom{2n+k}{n}. \end{align} $$