A Path-Counting Workshop

Choose the Constraint Before Choosing the Formula

For a simple random walk, a path is a sequence of upward and downward steps. Counting all paths of a given length with a specified endpoint is usually a binomial-coefficient calculation. Requiring the path to stay on one side of a boundary changes the problem: reflection can count the paths that violate the boundary and subtract them. A bridge that stays nonnegative is counted by a Catalan number, while a path required to stay strictly positive has a different count. A first-return condition adds another distinction: the endpoint may be zero, but the path is not allowed to visit zero earlier.

This workshop uses these constraints as a decision guide. We work with a fair simple random walk and count paths first; because every path of length \(n\) has probability \(2^{-n}\), a path count can then be converted into a probability. The boundary convention—strictly positive or merely nonnegative—must be specified before counting.

Unrestricted Endpoints and a Nonnegative Barrier

For an unrestricted endpoint count, the endpoint and length determine the numbers of upward and downward steps. If \(X_n=r\), then \(U=(n+r)/2\) and \(D=(n-r)/2\). Thus a path is possible only when \(n+r\) is even and \(|r|\le n\). When those conditions hold, choosing which \(U\) of the \(n\) step positions are upward gives the count \(\binom{n}{U}\).

Proof. For the endpoint count, each path to \(r\) has \(U-D=r\) and \(U+D=n\), so solving gives \(U=(n+r)/2\) and \(D=(n-r)/2\). If these are not nonnegative integers, there are no such paths. Otherwise, choosing the \(U\) upward-step positions gives the stated binomial coefficient. For the barrier count, begin with all paths from \(0\) to \(r\). A path that visits \(-1\) has a first visit to \(-1\). Reflect its increments up to and including that first visit, interchanging upward and downward steps. This gives a path from \(-2\) to \(r\). Conversely, every path from \(-2\) to \(r\) must visit \(-1\); reflecting its steps up to its first visit to \(-1\) recovers a path from \(0\) to \(r\) that visits \(-1\). These operations are inverse, so the bad paths are counted by paths from \(-2\) to \(r\). Such a path has \((n+r+2)/2\) upward steps, giving the subtracted term. Subtracting bad paths from all paths proves the formula. \(\square\)

The formula counts paths that may touch zero; it does not require them to stay strictly above zero. For a bridge, where \(n=2m\) and \(r=0\), it simplifies to the Catalan number \(C_m=\frac{1}{m+1}\binom{2m}{m}\). Indeed, the subtraction is \(\binom{2m}{m}-\binom{2m}{m+1}\), and \(\binom{2m}{m+1}=\frac{m}{m+1}\binom{2m}{m}\).

Catalan Bridges and First Returns

A nonnegative bridge of length \(2m\) starts at zero, ends at zero, and satisfies \(X_k\ge0\) at every intermediate time. Such a path has \(m\) upward and \(m\) downward steps. The barrier formula shows that their number is \(C_m\). These paths are often called Dyck paths. A first return to zero is a different event: for \(T_0^+=\inf\{n\ge1:X_n=0\}\), the condition \(T_0^+=2m\) requires the walk to avoid zero at every time from \(1\) through \(2m-1\).

Proof. A path with first return at time \(2m\) must begin with either an upward or a downward step. Consider those beginning upward. At time \(2m-1\), the walk must be at \(1\), since its final step is downward to zero. Between times \(1\) and \(2m-1\), it stays strictly positive. Subtract \(1\) from the walk’s positions over that segment: this gives a nonnegative bridge of length \(2m-2\) from zero to zero. This construction is reversible: add \(1\) to a nonnegative bridge of length \(2m-2\), prepend the upward step from zero, and append a downward step to zero. Thus the number of paths beginning upward and first returning at time \(2m\) is \(C_{m-1}\). Reflection of every increment changes upward-starting paths into downward-starting paths and preserves the first-return time, so there are another \(C_{m-1}\) paths. Finally, \(2C_{m-1}=\frac{2}{m}\binom{2m-2}{m-1}\). Since \(\binom{2m}{m}=\frac{(2m)(2m-1)}{m^2}\binom{2m-2}{m-1}\), this equals \(\frac{1}{2m-1}\binom{2m}{m}\). Dividing by \(2^{2m}\) gives the probability. \(\square\)

Strict Ballot Constraints

Suppose a path has \(a\) upward steps and \(b\) downward steps, with \(a>b\). A strict ballot constraint requires \(X_k>0\) after every step \(k=1,\ldots,a+b\). Its endpoint is \(a-b>0\), but an endpoint above zero alone does not guarantee that the path stayed positive along the way.

Proof. Put \(n=a+b\). A strictly positive path must begin upward. Remove that first step and lower all subsequent positions by \(1\). The remaining path has length \(n-1\), starts at zero, ends at \(a-b-1\), and stays nonnegative. Conversely, any such nonnegative path gives a strictly positive path when raised by \(1\) and preceded by an upward step. By the nonnegative-path formula, the number is \(\binom{n-1}{b}-\binom{n-1}{b-1}\), where the second term is zero when \(b=0\). Using \(\binom{n-1}{b}=\frac{a}{n}\binom{n}{b}\) and \(\binom{n-1}{b-1}=\frac{b}{n}\binom{n}{b}\), the difference is \(\frac{a-b}{n}\binom{n}{b}\), as claimed. \(\square\)

A Practical Selection Rule and a Common Pitfall

Before applying a formula, record the path length, endpoint, and exact constraint. The following table summarizes which count addresses which question.

Common pitfall. For length \(8\) and endpoint \(2\), using the unrestricted count \(56\) as the count of paths that stay nonnegative is wrong: it ignores paths that visit \(-1\). The correction is to subtract the \(28\) reflected paths, leaving \(56-28=28\). A related boundary error is to treat “never below zero” as “strictly above zero.” The former allows returns to zero; the latter excludes them after time zero. Always translate the words of the constraint into an explicit inequality before counting.