Proving the Ballot Theorem

From a Path Constraint to a Count

Suppose a sequence contains $p$ up-steps and $q$ down-steps, with more up-steps than down-steps. How many orderings keep the running total strictly above zero? The ballot theorem answers this exactly. Its proof is useful beyond the formula: a reflection of paths at their first visit to zero pairs the paths that fail the constraint with an easier-to-count collection.

For a fixed horizon $n$, take the probability space $(\Omega,\mathcal{F},\mathbb{P})$, where $\Omega=\{-1,+1\}^n$, $\mathcal{F}$ is the set of all subsets of $\Omega$, and each increment sequence has probability $2^{-n}$. Let $Y_k$ be the $k$-th increment, and define the simple symmetric walk $X_0=0$, $X_k=\sum_{\ell=1}^kY_\ell$, for $0\le k\le n$. Its state space is $S=\mathbb{Z}$, and its time indices are $0,1,\ldots,n$. Write $U$ for an up-step $+1$ and $D$ for a down-step $-1$. A path is strictly positive if $X_k>0$ at every time $k=1,\ldots,n$.

Theorem (Ballot theorem for walks): Let $p,q$ be nonnegative integers with $p>q$, let $n=p+q$, and put $r=p-q$. Among the $\binom{n}{q}$ sequences containing $p$ up-steps and $q$ down-steps, exactly $$ \frac{p-q}{p+q}\binom{p+q}{q} $$ have all partial sums strictly positive. Thus, if all such sequences are equally likely, the probability of strict positivity is $\frac{p-q}{p+q}$.

The condition $p>q$ makes the endpoint $r$ positive. It also ensures that the event in the theorem is possible. The strict inequality in the path condition matters: a path that reaches zero at an intermediate time does not count.

Proof by Reflection at Zero

First count all paths with the specified numbers of steps that begin with $U$. Every strictly positive path must begin with $U$, and after that first step there are $p-1$ up-steps and $q$ down-steps left. Thus the number of paths beginning with $U$ is $\binom{n-1}{q}$. Among these, call a path bad if it visits zero after time $1$. We count the bad paths by a bijection.

Proof. Consider a bad path and locate its first visit to zero after time $1$. Reflect the segment from time $1$ through that visit in the horizontal axis: replace each height $x$ in the segment by $-x$, leaving the remainder of the path unchanged. At time $1$, the original path is at $+1$, so the reflected segment starts at $-1$. It ends at zero, where the unchanged remainder continues to endpoint $r$. The result is therefore a path of $n-1$ steps from $-1$ to $r$.

This operation is reversible. Any path of $n-1$ steps from $-1$ to $r$ must visit zero because it starts below zero, ends at $r\ge1$, and changes by one at each step. Reflect its segment up to its first visit to zero. The result starts at $+1$, reaches zero, and so gives a bad path that began with $U$. The two operations undo one another because both use the first visit to zero.

A path from $-1$ to $r$ over $n-1$ steps has net increase $r+1$. If it has $a$ up-steps and $b$ down-steps, then $a+b=n-1$ and $a-b=r+1=p-q+1$. Solving gives $a=p$ and $b=q-1$. Hence there are $\binom{n-1}{q-1}$ such paths when $q\ge1$. When $q=0$, there are no bad paths: the only path consists entirely of up-steps. We use the convention $\binom{n-1}{-1}=0$, so the same count applies in that case.

Subtracting bad paths from paths beginning with $U$, the number of strictly positive paths is $\binom{n-1}{q}-\binom{n-1}{q-1}$. Since $n=p+q$, $\binom{n-1}{q}=\frac{p}{n}\binom{n}{q}$ and $\binom{n-1}{q-1}=\frac{q}{n}\binom{n}{q}$; the second identity also gives zero when $q=0$. Their difference is $\frac{p-q}{n}\binom{n}{q}$, as claimed. There are $\binom{n}{q}$ total sequences, so dividing the count by this total gives the stated probability. $\square$

For a fair walk, every length-$n$ increment sequence has probability $2^{-n}$. Conditional on having exactly $p$ up-steps and $q$ down-steps, all $\binom{n}{q}$ such sequences are equally likely. Therefore the same ratio is the conditional probability that the walk stays strictly positive, given its endpoint and horizon. This conclusion is conditional on an endpoint event of positive probability; for these integers, the event has probability $\binom{n}{q}2^{-n}>0$.

Checking the Count on Short Walks

Worked Example: Three Up-Steps and One Down-Step

Take $p=3$, $q=1$, so the horizon is $n=4$ and the endpoint is $r=3-1=2$. There are $\binom{4}{1}=4$ sequences altogether. The theorem gives $$ \frac{3-1}{3+1}\binom{4}{1} =\frac{2}{4}\cdot4 =2 $$ strictly positive paths.

To check by listing, the single down-step can occupy any of the four positions. If it is first, the path starts below zero. If it is second, the path reaches zero at time $2$. If it is third or fourth, all partial sums are positive. The two valid sequences are $UUDU$, with partial sums $1,2,1,2$, and $UUUD$, with partial sums $1,2,3,2$.

Check: Both paths end at $2$, as required, and both have positive partial sums at every time. The other two positions for the down-step fail the strict condition, so the direct count is also $2$.

Worked Example: A Small Horizon with Endpoint One

Take $p=2$, $q=1$, $n=3$, and endpoint $r=1$. The total number of sequences is $\binom{3}{1}=3$, and the theorem predicts $$ \frac{2-1}{2+1}\binom{3}{1} =\frac{1}{3}\cdot3 =1. $$ The three sequences are $UUD$, $UDU$, and $DUU$. Their partial sums are respectively $(1,2,1)$, $(1,0,1)$, and $(-1,0,1)$. Only $UUD$ stays strictly positive.

Check: The direct list gives one valid sequence, matching the formula. In the fair walk, each sequence has probability $2^{-3}=\frac18$, so the endpoint event has probability $3\cdot\frac18=\frac38$. The joint probability of endpoint $1$ and strict positivity is $\frac18$, and the ratio is $(\frac18)/(\frac38)=\frac13$, as predicted.

Worked Example: Four Up-Steps and Two Down-Steps

Now let $p=4$, $q=2$, $n=6$, and endpoint $r=2$. There are $\binom{6}{2}=15$ sequences. The strict count is $$ \frac{4-2}{4+2}\binom{6}{2} =\frac{2}{6}\cdot15 =5. $$ For a direct check, record the two positions occupied by down-steps. The five valid choices are $\{3,5\}$, $\{3,6\}$, $\{4,5\}$, $\{4,6\}$, and $\{5,6\}$. Their paths are $UUDUDU$, $UUDUUD$, $UUUDDU$, $UUUDUD$, and $UUUUDD$.

Their respective partial sums are $(1,2,1,2,1,2)$, $(1,2,1,2,3,2)$, $(1,2,3,2,1,2)$, $(1,2,3,2,3,2)$, and $(1,2,3,4,3,2)$. Each is positive at all six times. Every other pair of down-step positions either puts a down-step too early or causes the path to reach zero. Thus the enumeration also gives five.

Check: Each listed path has four up-steps and two down-steps, and the final partial sum is $4-2=2$. The direct count agrees with the formula.

What Changes at the Boundary

The strict positivity condition cannot be silently replaced by nonnegativity. In the $p=2,q=1$ example, $UDU$ touches zero at time $2$. It is not strictly positive, even though it never goes below zero. Counting it as valid would give two paths instead of the correct count of one. The endpoint condition alone does not settle this distinction; the path must be checked at every intermediate time.

The assumption $p>q$ is also essential to the stated formula. If $p=q$, every path ends at zero, so no path can have all partial sums strictly positive through the final time. For example, with $p=q=1$, the paths are $UD$ and $DU$, and neither stays strictly positive through time $2$. The theorem does not apply in this case; substituting $p=q$ into its expression happens to give zero, but that boundary case is not the positive-endpoint ballot statement proved above.

When $q=0$, the theorem does apply. There is one sequence, consisting entirely of up-steps, and it is strictly positive. The formula gives $\frac{p}{p}\binom{p}{0}=1$, including this boundary case. In the reflection proof, the convention $\binom{n-1}{-1}=0$ records that there are no bad paths.

Common mistake. A frequent error is to count paths that stay at or above zero while reporting a count for paths that stay strictly above zero. For $p=2,q=1$, this mistake includes $UDU$: its partial sums are $1,0,1$. The correction is to test $X_k>0$, not $X_k\ge0$, at every $k=1,\ldots,n$. Under the strict test, $UDU$ fails and the count is one.

The reflection argument is effective because it identifies exactly which paths violate the constraint: among paths that start with an up-step, the bad ones are those that later hit zero. Reflecting up to the first such visit gives a bijection, so subtraction counts the good paths without approximation. The endpoint difference $p-q$ then appears in the factor $(p-q)/(p+q)$, measuring how many of the fixed-endpoint orderings survive the strict path constraint.

Check Your Understanding

Use strict positivity at every time $k=1,\ldots,n$ when deciding whether a path qualifies.

For $p=3$ and $q=2$, calculate the number of strictly positive paths and the conditional probability of strict positivity.
For $p=3$ and $q=1$, which positions can contain the single down-step if the path is to remain strictly positive?
Explain why every path from $-1$ to a positive integer, with steps of size one, must visit zero.
For $p=q=2$, can any path be strictly positive through its final time? Explain using the endpoint.
When $p=2$ and $q=1$, identify the sequence that stays nonnegative but not strictly positive, and state its partial sums.

What You'll Learn