Counting Walks That Stay Above Zero
A walk can finish at a positive level without having stayed positive along the way. For example, it may return to zero before moving upward again. When counting paths, the distinction between staying strictly above zero and staying at or above zero changes the answer. The ballot count makes that distinction explicit: for a fixed positive endpoint, the number of strictly positive paths is a simple fraction of all paths to that endpoint.
Work on the probability space \((\Omega,\mathcal{F},\mathbb{P})\) of infinite sequences of independent fair increments, each equal to \(+1\) or \(-1\) with probability \(1/2\). Define the discrete-time walk \((S_j)_{j\ge0}\) with state space \(\mathbb{Z}\) by \(S_0=0\) and \(S_j\) equal to the sum of the first \(j\) increments. For a fixed length \(n\), a path is the sequence \(S_0,S_1,\ldots,S_n\). Each specified sequence of \(n\) increments has probability \(2^{-n}\).
An endpoint \(k\) is possible at time \(n\) only if \(k\) is an integer, \(1\le k\le n\), and \(n+k\) is even. Indeed, if \(u\) increments are \(+1\), then \(n-u\) are \(-1\), so the endpoint is \(2u-n\). Thus \(u=(n+k)/2\), and the number of unrestricted paths ending at \(k\) is \(\binom{n}{(n+k)/2}\). If these conditions fail, there are no paths to that endpoint.
The factor \(k/n\) is the fraction of all paths to the specified endpoint that stay strictly positive. It depends on the endpoint and the total length, not on the particular ordering of the upward and downward steps. The strict inequality matters: a path that touches zero at an intermediate time is excluded, even if it ends at \(k>0\).
Worked Example: Five Steps and Endpoint One
Count the five-step paths that end at \(1\) and remain strictly positive. Here \(n=5\), \(k=1\), and \(u=(5+1)/2=3\), so the endpoint is possible. There are \(\binom{5}{3}=10\) unrestricted paths to \(1\). The strict ballot count is
The two paths, written as their increments, are \(+1,+1,-1,+1,-1\) and \(+1,+1,+1,-1,-1\). Their partial sums after each step are respectively \(1,2,1,2,1\) and \(1,2,3,2,1\), all strictly positive. Since the count formula gives two and these are two distinct qualifying paths, the enumeration agrees. Each path has probability \(2^{-5}=1/32\), so the probability of both ending at \(1\) and staying strictly positive is \(2/32=1/16\).
Check: The endpoint probability is \(\binom{5}{3}/2^5=10/32=5/16\). Among the ten paths to that endpoint, the strict fraction is \(1/5\); multiplying gives \((1/5)(5/16)=1/16\), as above.
Why the Ballot Count Holds
The counting argument starts with the first step. A path that is strictly positive after every step must begin with \(+1\). After that step, it is a walk of length \(n-1\) from level \(1\) to level \(k\), and it must never visit zero. We count all paths from \(1\) to \(k\), then subtract those that visit zero.
Proof. Set \(u=(n+k)/2\), an integer under the theorem’s assumptions. The first step is \(+1\). The remaining \(n-1\) steps must have \(u-1\) upward increments, since the full path has \(u\) upward increments. Thus the number of unrestricted remaining paths from \(1\) to \(k\) is \(\binom{n-1}{u-1}\).
Among these paths, call a path bad if it visits zero. For each bad path, take the segment from its start at level \(1\) through its first visit to zero and reflect that segment about zero: each level \(x\) in this segment is replaced by \(-x\). The resulting path starts at \(-1\), ends at \(k\), and has the same length \(n-1\). Conversely, every path of length \(n-1\) from \(-1\) to \(k\) must visit zero, because its increments are \(\pm1\) and \(k>0\). Reflecting its segment up to its first visit to zero recovers exactly one bad path from \(1\) to \(k\). This is a bijection.
A path from \(-1\) to \(k\) in \(n-1\) steps has \(u\) upward increments: its net change is \(k+1\), so its number of upward increments is \(((n-1)+(k+1))/2=u\). Therefore the number of bad paths is \(\binom{n-1}{u}\). Subtracting gives the number of strictly positive paths: $$ \binom{n-1}{u-1}-\binom{n-1}{u} =\frac{u}{n}\binom{n}{u}-\frac{n-u}{n}\binom{n}{u} =\frac{2u-n}{n}\binom{n}{u} =\frac{k}{n}\binom{n}{(n+k)/2}. $$ Here the two middle terms use \(\binom{n-1}{u-1}=\frac{u}{n}\binom{n}{u}\) and \(\binom{n-1}{u}=\frac{n-u}{n}\binom{n}{u}\), which follow by writing the binomial coefficients as factorials. This proves the formula. If the endpoint conditions fail, no path has the required endpoint, so the count is zero. \(\square\)
For the fair walk, all paths of length \(n\) have the same probability. Consequently, conditional on \(S_n=k\), the probability that the path has stayed strictly positive is \(k/n\), provided the endpoint is possible. This conditional probability is well-defined because \(\mathbb{P}(S_n=k)>0\) under the stated endpoint conditions.
Worked Example: Six Steps and Endpoint Two
For \(n=6\) and \(k=2\), \(u=(6+2)/2=4\), so there are \(\binom{6}{4}=15\) unrestricted paths to the endpoint. The strict count is
There are \(2^6=64\) equally likely length-six paths, so the probability of ending at \(2\) and staying strictly positive is \(5/64\). The endpoint probability is \(15/64\), and their ratio is \((5/64)/(15/64)=1/3=2/6\), which checks the conditional version of the count.
As a second count check, after the forced first upward step there are five steps from level \(1\) to level \(2\). There are \(\binom{5}{3}=10\) unrestricted such paths. The paths that hit zero correspond, by the reflection argument, to paths from \(-1\) to \(2\) in five steps; these have \((5+3)/2=4\) upward steps and number \(\binom{5}{4}=5\). The difference is \(10-5=5\), agreeing with the ballot formula.
Strict Positivity Is Not Nonnegativity
For a nonnegative path, the condition is \(S_j\ge0\) for every \(1\le j\le n\). Such a path is allowed to return to zero, whereas a strictly positive path is not. The corresponding count can also be found by reflection, but its boundary and formula differ.
Proof. There are \(\binom{n}{u}\) unrestricted paths from zero to \(k\). A path that fails nonnegativity visits \(-1\). Reflect its segment from its start at zero through its first visit to \(-1\) about the level \(-1\). The reflected path starts at \(-2\) and ends at \(k\). Conversely, every path from \(-2\) to \(k\ge0\) must visit \(-1\); reflecting its segment through its first such visit recovers a unique path from zero that visits \(-1\). Thus the paths that fail nonnegativity are counted by paths from \(-2\) to \(k\). Such a path has \((n+k+2)/2=u+1\) upward increments, so the bad-path count is \(\binom{n}{u+1}\). Subtraction gives \(\binom{n}{u}-\binom{n}{u+1}\). Since \(\binom{n}{u+1}=\frac{n-u}{u+1}\binom{n}{u}\), the difference is \(\frac{2u+1-n}{u+1}\binom{n}{u}=\frac{k+1}{u+1}\binom{n}{u}\). \(\square\)
Worked Example: Comparing the Two Boundaries
Return to \(n=5\), \(k=1\), and \(u=3\). The strict count is \(\frac{1}{5}\binom{5}{3}=2\). The nonnegative count is
Thus three of the five nonnegative paths touch zero and are not strictly positive. For instance, the increments \(+1,-1,+1,+1,-1\) give partial sums \(1,0,1,2,1\). This path is nonnegative but not strictly positive. The increments \(+1,+1,-1,-1,+1\) give partial sums \(1,2,1,0,1\), also nonnegative but not strictly positive. The strict count of two includes neither path. The two formulas therefore count different sets, even though both sets have the same positive endpoint.
Common Mistake and a Useful Check
Common mistake: Using the nonnegative count when the question asks for strict positivity. For five steps ending at one, that mistake gives \(\binom{5}{3}-\binom{5}{4}=10-5=5\) paths. But five is the count that permits visits to zero. The strict count is \(\frac{1}{5}\binom{5}{3}=2\). A quick diagnostic is the first step: every strictly positive path must start with \(+1\), and any path that later reaches zero must be excluded.
Before applying either formula, check the endpoint conditions and identify the barrier precisely. If \(k>0\) but \(n+k\) is odd, there are no paths to \(k\), regardless of the positivity condition. If \(k=n\), there is one path, consisting entirely of upward steps; the strict formula gives \((n/n)\binom{n}{n}=1\). This endpoint check also confirms that the formula handles the most extreme positive endpoint.
The distinction between the two barriers is useful whenever a path-counting question concerns survival above a boundary. Replacing \(S_j>0\) by \(S_j\ge0\) changes which paths qualify, so the count should be chosen from the event itself rather than from the endpoint alone.
Check Your Understanding
For each question, first check whether the endpoint is compatible with the number of steps.
- How many four-step paths end at \(2\) and stay strictly positive? Verify the result by counting the unrestricted paths and subtracting those that hit zero.
- For six steps ending at \(2\), what fraction of paths to that endpoint stay strictly positive?
- Explain why a path that touches zero and then ends at a positive level is nonnegative but not strictly positive.
- For five steps ending at \(1\), compute the nonnegative count and compare it with the strict count.
- Why is the conditional probability of strict positivity given \(S_n=k\) equal to the strict path count divided by \(\binom{n}{(n+k)/2}\)? State when this conditional probability is defined.