Encoding Paths by Their Up-Steps

From a Walk to Its Up-Step Positions

A simple symmetric walk can be described one step at a time, but for counting purposes it is often more useful to record where its upward steps occur. Once the length and endpoint are fixed, the numbers of upward and downward steps are forced. The only choice left is the set of step positions occupied by the upward steps. This turns a path-counting question into a choice of positions.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\) carrying independent increments \((\xi_k)_{k\ge1}\), with \(\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12\). Define \(X_0=0\) and \(X_n=\sum_{k=1}^n \xi_k\), so \((X_n)_{n\ge0}\) is the simple symmetric random walk on the state space \(S=\mathbb{Z}\), in discrete time \(n\). Its transition kernel is \(p_{i,i+1}=p_{i,i-1}=\tfrac12\) for every \(i\in\mathbb{Z}\), with all other transition probabilities zero; each row sums to \(\tfrac12+\tfrac12=1\). When conditioning on the walk up to time \(n\), use the filtration \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\).

A length-\(n\) path is its ordered list of \(n\) increments, or, equivalently, the sequence of positions \(X_0,X_1,\ldots,X_n\). An up-step is an increment \(+1\), and a down-step is an increment \(-1\). In this tutorial, paths are unrestricted: they may visit any integer at intermediate times. In particular, the count below does not impose a barrier or require the path to stay on one side of zero.

The Endpoint Determines the Number of Up-Steps

Suppose a path starts at zero, has length \(n\), and ends at \(j\). If it has \(u\) up-steps, then it has \(n-u\) down-steps. Each up-step adds one to the position and each down-step subtracts one, so its endpoint is \(u-(n-u)\). Solving this relation for \(u\) gives the required number of up-steps.

Proof. First suppose a path of length \(n\) ends at \(j\), and let \(u\) be its number of up-steps. Its number of down-steps is \(n-u\), so \(j=u-(n-u)=2u-n\). Thus \(u=(n+j)/2\). Because \(u\) counts steps, it must be an integer with \(0\le u\le n\). If either condition fails, no path can end at \(j\).

Now suppose \(u=(n+j)/2\) is an integer with \(0\le u\le n\). Choose any \(u\)-element subset \(U\) of the \(n\) step positions, assign an up-step at each position in \(U\), and assign a down-step at each remaining position. The resulting path has \(u\) up-steps and \(n-u\) down-steps, hence ends at \(2u-n=j\). Conversely, every path ending at \(j\) determines exactly one such subset, namely its up-step set. These two assignments are inverses, so they give a bijection between the paths in question and the \(u\)-element subsets. There are \(\binom{n}{u}=\binom{n}{(n+j)/2}\) such subsets. \(\square\)

This argument gives both a count and a construction: to make a path with the required endpoint, select the up-step positions, then fill every unselected position with a down-step. The endpoint restriction does not impose any further restrictions on the order of those steps. Paths that move far from their endpoint and later return are included as long as their total numbers of up-steps and down-steps are correct.

Counting by Choosing Down-Step Positions

The same path can be encoded by its down-step positions instead. If the endpoint is \(j\), the number of down-steps is \(d=(n-j)/2\), since the endpoint is also \(n-2d\). Choosing the \(d\) down-step positions gives \(\binom{n}{d}\) paths. This agrees with the up-step count because \(d=n-u\), and choosing the complement of a set is a bijection between subsets of sizes \(u\) and \(n-u\). Thus \(\binom{n}{u}=\binom{n}{n-u}\). This is a second way to check a calculation, not a different restriction on the path.

Feasibility and Boundary Cases

The formula includes its own feasibility test. A path cannot have a noninteger number of up-steps, and it cannot have fewer than zero or more than \(n\) up-steps. In particular, for a fixed length and endpoint, one should first calculate \((n+j)/2\), then check that it is an integer in the inclusive range from \(0\) to \(n\), and only then evaluate the binomial coefficient. This also handles the boundary cases: if \(j=n\), all \(n\) steps must be upward and there is one path; if \(j=-n\), all \(n\) steps must be downward and there is one path. When \(n=0\), the empty path ends at zero, and there is one such path; for any \(j\ne0\), there are none.

The same reasoning applies if the walk starts at a location \(x\) rather than zero. Its net displacement is \(j-x\) when it ends at \(j\), so the number of up-steps must be \((n+j-x)/2\). The count is the binomial coefficient with this value as its lower index when that value is an integer from \(0\) through \(n\); otherwise there are no such paths. This is just the endpoint calculation applied to the displacement, not a change in how step positions are encoded.

A Consistency Check Across All Endpoints

Proof. Every length-\(n\) path has an up-step set \(U\subseteq\{1,\ldots,n\}\), and each such subset determines exactly one path. The collection of all paths is therefore in bijection with the collection of all subsets of the \(n\) step positions. There are \(2^n\) subsets: each position is either included or not included. Also, every path has exactly one endpoint, so grouping the paths according to their endpoint partitions this same collection into disjoint groups. The group for endpoint \(j\) has the count given by the theorem, and summing those group sizes must give the total \(2^n\). For \(n=0\), the position set is empty and has one subset, the empty set, so the same argument gives \(2^0=1\). \(\square\)

This identity is a useful audit of endpoint counts: no path should be omitted, and no path should be counted twice. It does not require calculating any probabilities. If one later assigns probabilities to paths, the same partition can be used to aggregate their probabilities, but the combinatorial step here is simply to count the paths in each endpoint group.

Common Mistake: Reversing the Up-Step Formula

A frequent error is to use \((n-j)/2\) as the number of up-steps. That expression counts down-steps, not up-steps. For a concrete check, take \(n=5\) and \(j=1\). The incorrect formula gives \((5-1)/2=2\) up-steps, which would produce endpoint \(2-(5-2)=2-3=-1\), not \(1\). The correct equation is \(j=u-(n-u)=2u-n\), so \(u=(n+j)/2=(5+1)/2=3\). With three up-steps and two down-steps, the endpoint is \(3-2=1\).

A second pitfall is to evaluate a binomial coefficient before checking whether its lower index is a valid integer between zero and \(n\). For example, five steps cannot end at zero: the proposed number of up-steps would be \((5+0)/2=5/2\), which is not an integer. The impossibility follows directly from the step-count equation; it is not a case to repair by rounding. In general, the encoding provides a quick order of work: solve for the number of up-steps, check feasibility, then count the allowable position sets.