Counting Paths Across a Barrier

Counting Paths That Reach a Barrier

A walk can finish below a barrier even though it has visited the barrier along the way. Counting such paths requires more than counting paths with a given endpoint: it also requires tracking whether the path has crossed a level at an earlier time. For a simple symmetric walk, reflection turns this path-history condition into a count with a different endpoint. The endpoint change makes parity constraints visible and gives an exact formula.

Let \((\Omega,\mathcal{F},\mathbb{P})\) carry independent increments \(\xi_1,\xi_2,\ldots\), each equal to \(+1\) or \(-1\) with probability \(\tfrac12\). Define the simple symmetric random walk by \(X_0=0\) and \(X_k=\sum_{\ell=1}^k \xi_\ell\). Its state space is \(S=\mathbb{Z}\), and its time index is the nonnegative integers. We count its paths through time \(n\), where \(n\ge 0\) is an integer. A path has probability \(2^{-n}\) through time \(n\), since each of its \(n\) increments has probability \(\tfrac12\).

Because each step changes the position by exactly one, a path starting at \(0<a\) cannot move from below \(a\) to above \(a\) without visiting \(a\). Thus, for this integer-valued walk and integer barrier, “reaches or crosses \(a\)” is equivalent to “hits \(a\) at some time.” We use \(\ge a\) for the maximum condition throughout; a path whose maximum is exactly \(a\) is included.

For any integer \(y\), the number of length-\(n\) paths from \(0\) to \(y\) is \(\binom{n}{(n+y)/2}\) when \((n+y)/2\) is an integer between \(0\) and \(n\), inclusive, and is zero otherwise. Indeed, if a path has \(u\) up-steps and \(n-u\) down-steps, its endpoint is \(u-(n-u)=2u-n\), so reaching \(y\) requires \(u=(n+y)/2\). Choosing which \(u\) of the \(n\) steps are up-steps gives the count. This also shows the parity restriction: an endpoint is possible only when \(n\) and \(y\) have the same parity.

Proof. Consider the set of length-\(n\) paths that end at \(j<a\) and reach \(a\). For each such path, let \(T=\min\{k\ge0:X_k=a\}\) be its first hitting time of \(a\). Define a new path by leaving positions through time \(T\) unchanged and reflecting every later position about \(a\): \(X'_k=X_k\) for \(k\le T\), and \(X'_k=2a-X_k\) for \(k>T\). Since \(X_T=a\), the step after time \(T\), if there is one, changes sign under this reflection; all earlier steps are unchanged. The new path therefore still has steps of size \(1\) or \(-1\), starts at \(0\), and ends at \(X'_n=2a-j\).

Conversely, any length-\(n\) path ending at \(2a-j>a\) must hit \(a\): it starts at \(0<a\), ends above \(a\), and can increase by at most one at each step. Reflecting its positions after its first hit of \(a\) gives a path ending at \(j\) that has hit \(a\). These two transformations are inverses, because they preserve the path up to the first hit of \(a\), and reflecting twice restores every later position. Hence there is a bijection between the paths being counted and all paths ending at \(2a-j\). The endpoint count above gives \(\binom{n}{(n+2a-j)/2}\), including zero when its parity or range condition fails. Each original path has probability \(2^{-n}\), so the probability statement follows. \(\square\)

The reflected endpoint is \(2a-j\), not \(j\): the endpoint \(j\) is the same distance below \(a\) that \(2a-j\) lies above it. Its displacement from the start determines the binomial coefficient. Since \(2a-j\) and \(j\) have the same parity, the reflection count automatically respects the walk’s parity constraint.

The reflection count also gives the number of paths that end at \(j<a\) and never reach \(a\). This complementary count is useful when the question asks for paths that stay below the barrier rather than paths that visit it.

Proof. Partition all paths ending at \(j\) into two disjoint classes: those that reach \(a\), and those that do not. The total number is \(\binom{n}{(n+j)/2}\) by the endpoint count, with the stated zero convention. The first class has size \(\binom{n}{(n+2a-j)/2}\) by the reflection theorem. Subtracting the first class from the total gives the number in the second class. The partition remains valid when the endpoint is unattainable: then both classes are empty, and the zero convention makes the total and crossing counts zero. \(\square\)

Using the Count Carefully

The formula is an exact endpoint-specific count. It does not count all paths that ever reach the barrier regardless of where they finish; it counts only those that both reach the barrier and finish at the specified \(j<a\). If a problem asks for a probability, divide this count by \(2^n\), because all \(2^n\) increment sequences are equally likely under the simple symmetric walk.

Common mistake: counting all paths to the endpoint. For \(n=8\), \(a=2\), and \(j=0\), using only the endpoint formula gives \(\binom{8}{(8+0)/2}=\binom{8}{4}=70\). That is the number of paths ending at \(0\), not the number among them that reach \(2\). The corrected crossing count reflects to endpoint \(2(2)-0=4\) and is \(\binom{8}{(8+4)/2}=\binom{8}{6}=28\). The remaining \(70-28=42\) paths end at \(0\) without reaching \(2\).

Three checks prevent most counting errors. First, check that the endpoint really is below the barrier, \(j<a\), before using this formula. Second, check parity and range: \((n+2a-j)/2\) must be an integer from \(0\) through \(n\), or the count is zero. Third, decide whether “crossing” includes touching the barrier. Here it means reaching or exceeding \(a\), so paths with maximum exactly \(a\) are counted. If the question instead asks for a maximum strictly greater than \(a\), use \(a+1\) as the integer barrier.