Ties, Strict Barriers, and Other Counting Pitfalls

Why Small Counting Conventions Matter

For a simple random walk, a path is a sequence of up-steps and down-steps. A count can go wrong before any difficult calculation: an endpoint may be unreachable at the chosen time, “hits the barrier” may be confused with “crosses above the barrier,” or a path may be counted more than once because its maximum occurs at several times. These are not cosmetic distinctions. Each changes the set being counted.

Work on the probability space \((\Omega,\mathcal{F},\mathbb{P})\), where \(\Omega=\{-1,+1\}^{\{1,2,\ldots\}}\), \(\mathcal{F}\) is the product sigma-field, and the coordinate increments \(\xi_k\) are independent with \(\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12\). Define the discrete-time walk \((S_n)_{n\ge0}\) by \(S_0=0\) and \(S_n=\sum_{k=1}^n\xi_k\), with state space \(S=\mathbb{Z}\). The natural filtration is \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\). For counting paths of length \(n\), each of the \(2^n\) increment sequences has probability \(2^{-n}\); thus a path count divided by \(2^n\) gives its probability.

Parity Before Counting

If a length-\(n\) path ends at \(j\), and it has \(u\) up-steps and \(d\) down-steps, then \(u+d=n\) and \(u-d=j\). Therefore \(u=(n+j)/2\). This must be an integer between \(0\) and \(n\). In particular, an endpoint is reachable only when \(n\) and \(j\) have the same parity and \(|j|\le n\).

To justify the rule, choose which \(u=(n+j)/2\) of the \(n\) step positions are up-steps; all other steps are down-steps. Each choice produces exactly one path, and every path produces exactly one such choice. The parity check is therefore part of the formula, not an optional preliminary simplification.

Touching a Barrier Is Not Crossing It

The reflection principle is useful only after the barrier event and the reflected endpoint are specified correctly. The next result counts paths that hit a positive integer level \(a\), then end below it. Its proof also explains why one cannot substitute a crossing event without changing the level.

Proof. Given a path ending at \(j<a\) that hits \(a\), find its first time at \(a\). Leave the part up to that time unchanged and reflect every later position \(x\) to \(2a-x\). Since each later increment changes sign, the result is still a nearest-neighbor path. Its endpoint is \(2a-j\). Conversely, any path from \(0\) to \(2a-j>a\) must hit \(a\): it starts below \(a\), ends above \(a\), and changes by one at each step. Reflecting its part after its first hit of \(a\) recovers the original type of path, ending at \(j\). The two operations undo one another, so they give a bijection. The unrestricted count to \(2a-j\) follows from the endpoint counting rule. If that endpoint has the wrong parity or lies outside the reachable range, both sides count zero. \(\square\)

To count paths that cross above \(a\), apply the theorem at level \(a+1\), not at level \(a\). In contrast, paths that stay at or below \(a\) are obtained by subtracting the number that hit \(a+1\) from the unrestricted endpoint count. This subtraction works because every path is either in that crossing event or is not, and the two classes are disjoint.

Weak Nonnegativity and Strict Positivity

“Positive path” is ambiguous unless its boundary convention is stated. A path from \(0\) cannot be strictly positive at every time including time \(0\), because it starts at \(0\). Here, weak nonnegativity means \(s_k\ge0\) for every \(0\le k\le n\). Strict positivity means \(s_k>0\) for every \(1\le k\le n\); the initial value \(s_0=0\) is excluded by definition.

Proof. For weak nonnegativity, start with all paths ending at \(j\ge0\). A path that fails the condition has a first hit of \(-1\). Reflect its part after that first hit across level \(-1\), sending each later position \(x\) to \(-2-x\). The endpoint \(j\) becomes \(-2-j\). Conversely every path from \(0\) to \(-2-j\) must hit \(-1\), and reflecting after its first such hit recovers a path in the excluded class. Thus the excluded count is the unrestricted count to \(-2-j\), which equals \(\binom{n}{(n+j+2)/2}\) by the endpoint rule and symmetry of binomial coefficients. Subtracting it gives the weakly nonnegative formula. For strict positivity with \(j>0\), the first step must be up. After that step, subtract \(1\) from all remaining positions: the remaining \(n-1\) steps form a weakly nonnegative path from \(0\) to \(j-1\). Applying the formula just proved with length \(n-1\) and endpoint \(j-1\) gives the stated expression. If the parity conditions fail, the corresponding counts are zero by the same convention. \(\square\)

When the Maximum Is Attained More Than Once

For a fixed path, define its set of maximum times by \(A_n=\{k\in\{0,\ldots,n\}:S_k=M_n\}\). If a problem asks for “the time of the maximum,” it must specify a selection rule when \(A_n\) has more than one element. The first maximum time is \(\min A_n\), and the last maximum time is \(\max A_n\); both are uniquely defined. Counting pairs consisting of a path and any time at which its maximum occurs is a different task: a path with \(r\) maximum times contributes \(r\) pairs, not one.

A Reliable Counting Checklist

Before using a path-count formula, write down the event in words and translate it into conditions on \(s_0,\ldots,s_n\). In particular, specify whether the barrier event is a hit, a strict crossing, or avoidance; state whether the boundary inequality is strict or weak; and say whether a maximum time means the first, last, or any maximizing time. Then check endpoint parity and reachable range before evaluating binomial coefficients.

A common mistake is to count paths ending at \(0\) at time \(4\) that cross above level \(1\) by reflecting at level \(1\). That calculation gives \(\binom{4}{3}=4\), but it counts paths that hit \(1\), including paths that never reach \(2\). The correction is to translate “cross above \(1\)” into “hit \(2\)” and reflect at \(2\), giving \(\binom44=1\). The explicit list in the earlier example verifies the corrected event. The error is not in reflection itself; it is in applying a correct count to the wrong barrier event.

These conventions are especially useful when comparing formulas derived by different methods. A difference of two binomial coefficients may encode a strict boundary restriction; a reflected count may encode a hit at the boundary; and a sum over candidate maximum times may count tied paths repeatedly. Making the event explicit turns each formula into a checkable statement about a precisely defined set of paths.