Parity and Lattice Constraints

Why Endpoints Lie on a Parity Lattice

A simple symmetric random walk moves by exactly one unit at each step. That small restriction has a strong consequence: after an even number of steps it must be at an even integer, and after an odd number of steps it must be at an odd integer. This parity constraint rules out many endpoints before any path counting begins. It also means that a sum over all integers in a range must include only the integers with the correct parity.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(\xi_k)_{k\ge1}$ be independent random variables with $\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12$. The simple symmetric random walk is the discrete-time process $(S_n)_{n\ge0}$ with state space $\mathbb{Z}$, defined by $S_0=0$ and $S_n=\sum_{k=1}^n \xi_k$. Each increment has total probability $\tfrac12+\tfrac12=1$. A path of length $n$ is a particular sequence of $n$ increments; each such sequence has probability $2^{-n}$.

Definition: Two integers have the same parity if their difference is an even integer. Equivalently, they are congruent modulo $2$. The parity class available to $S_n$ is the set of integers congruent to $n$ modulo $2$.

The parity statement is an invariant of the walk: every step changes both the time index and the position by one, so the agreement between their parities is preserved. The exact endpoint condition adds a distance restriction. An endpoint must be no farther than $n$ units from the origin, as well as having the correct parity.

Theorem (Reachable endpoints and path counts): For an integer $j$ and an integer $n\ge0$, a path of length $n$ from $0$ to $j$ exists if and only if $|j|\le n$ and $j\equiv n\pmod 2$. If these conditions hold, the number of such paths is $\binom{n}{(n+j)/2}$, and $\mathbb{P}(S_n=j)=2^{-n}\binom{n}{(n+j)/2}$. If either condition fails, the number of paths and the probability are both zero. Here $\binom{n}{r}$ counts the ways to choose $r$ positions from $n$, for an integer $r$ between $0$ and $n$.

Proof. Suppose a path has $u$ up-steps and $d$ down-steps. Then $u+d=n$ and its endpoint is $u-d=j$. Adding these equations gives $2u=n+j$, so $u=(n+j)/2$. For a path to exist, $u$ must be an integer between $0$ and $n$. Being an integer is equivalent to $j\equiv n\pmod 2$; being between $0$ and $n$ is equivalent to $-n\le j\le n$, or $|j|\le n$. This proves that the conditions are necessary. Conversely, if they hold, then $u=(n+j)/2$ is an integer between $0$ and $n$. Choose any $u$ of the $n$ step positions to be up-steps and make the remaining $n-u$ steps down-steps. The resulting endpoint is $u-(n-u)=2u-n=j$, so a path exists. There are $\binom{n}{u}=\binom{n}{(n+j)/2}$ choices of up-step positions. Each has probability $2^{-n}$, and the paths are disjoint outcomes, so their probabilities add to $2^{-n}\binom{n}{(n+j)/2}$. If either condition fails, there is no such path, and the event has probability zero. $\square$

The proof also shows the two distinct reasons an endpoint can be impossible. It may be too far away, or it may be close enough but have the wrong parity. For example, after $5$ steps, $4$ is within distance $5$ but is even, while the time is odd. The endpoint $6$ has the correct odd/even test only if it is odd, but it is also beyond the maximum distance. In fact, $6$ is even and too far away, so it violates both restrictions.

Using the Constraint in Calculations

For any set $A$ of integers, the endpoint event $\{S_n\in A\}$ can receive probability only from the reachable points in $A$. Since $S_n$ can take only finitely many values, the probability is a finite sum. The endpoints in the sum must satisfy both the distance restriction and the parity restriction; the inequalities describing $A$ determine which of those points are included.

Proposition (Endpoint probabilities over a set): For $n\ge0$ and $A\subseteq\mathbb{Z}$, $$ \mathbb{P}(S_n\in A) = 2^{-n}\sum_{\substack{j\in A,\ |j|\le n\\ j\equiv n\;(\mathrm{mod}\;2)}} \binom{n}{(n+j)/2}. $$ The sum is zero if there are no integers meeting all three conditions.

Proof. The event $\{S_n\in A\}$ is the union of the events $\{S_n=j\}$ over $j\in A$. Events for distinct endpoint values are disjoint, since $S_n$ cannot equal two different integers at once. Values outside $[-n,n]$ or with parity different from $n$ have probability zero by the theorem. For every remaining value in $A$, the theorem gives probability $2^{-n}\binom{n}{(n+j)/2}$. Adding these probabilities over the finite set of reachable values in $A$ gives the formula. If that set is empty, the event is impossible and its probability is zero. $\square$

In practice, apply the proposition in this order: first intersect the requested set with the distance range, then retain the correct parity, and only then evaluate the binomial coefficients. This avoids both unnecessary terms and the common error of counting endpoints that no path can reach.

Worked Example: An Exact Endpoint After Eight Steps

Find the number of length-$8$ paths ending at $2$, and calculate $\mathbb{P}(S_8=2)$.

The endpoint is within the allowed distance because $|2|=2\le8$, and it has the same parity as $8$. The required number of up-steps is $$ u=\frac{8+2}{2}=5. $$ Thus a path ending at $2$ chooses $5$ of the $8$ positions for up-steps; the other $3$ are down-steps. The count is $$ \binom{8}{5}=\frac{8\cdot7\cdot6}{3\cdot2\cdot1}=56. $$

There are $2^8=256$ equally likely increment sequences, so $$ \mathbb{P}(S_8=2)=\frac{56}{256}=\frac{7}{32}. $$ Check: each counted sequence has $5-3=2$ net steps, as required, and the reduced probability $\tfrac{7}{32}$ is $56$ of the $256$ possible paths.

Worked Example: A Range with a Strict Lower Bound

Calculate $\mathbb{P}(S_7\in\{0,1,2,3\})$. The set is explicitly inclusive at both ends; in particular, $0$ and $3$ are included in the event.

Because $n=7$ is odd, only odd endpoints can occur. Among $0,1,2,3$, the odd endpoints are $1$ and $3$; both satisfy the distance condition $|j|\le7$. For endpoint $1$, the number of up-steps is $$ u=\frac{7+1}{2}=4, $$ so there are $\binom{7}{4}=35$ paths. For endpoint $3$, $$ u=\frac{7+3}{2}=5, $$ so there are $\binom{7}{5}=21$ paths. The two endpoint events are disjoint, giving $35+21=56$ paths in the requested set. Hence $$ \mathbb{P}(S_7\in\{0,1,2,3\})=\frac{56}{2^7}=\frac{56}{128}=\frac{7}{16}. $$

Check: The excluded endpoints $0$ and $2$ are even, so neither can occur at time $7$. The included endpoints contribute $35+21=56$ of the $128$ possible paths, and $\tfrac{7}{16}\cdot128=56$.

Parity can also be used before counting a path that must meet endpoint conditions at more than one time. For instance, if a proposed intermediate endpoint is inconsistent with its time index, the entire joint event is impossible. If the parity checks pass, the increments in consecutive time blocks can be counted separately because the increments are independent. The next example uses only that independence and the endpoint count above.

Worked Example: Two Endpoint Constraints

Find the number of length-$8$ paths satisfying $S_4=2$ and $S_8=0$, and find the probability of these two conditions occurring together.

The first four increments must sum to $2$. They contain $3$ up-steps and $1$ down-step, so there are $$ \binom{4}{3}=4 $$ choices for the first block. The increments from time $5$ through time $8$ must take the walk from $2$ to $0$, so their sum must be $-2$. In this second block there is $1$ up-step and $3$ down-steps, giving $$ \binom{4}{1}=4 $$ choices. Every choice of a first block can be paired with every choice of a second block. Therefore there are $4\cdot4=16$ paths meeting both constraints. Each complete path has probability $2^{-8}=\tfrac{1}{256}$, so the joint probability is $$ \frac{16}{256}=\frac{1}{16}. $$

Check: The first block ends at $3-1=2$, and the second changes the position by $1-3=-2$, so the full path ends at $2-2=0$. The count $16$ is $16$ of the $256$ equally likely length-$8$ paths.

What Parity Does—and Does Not—Tell You

Parity is a support restriction: it identifies which endpoint values have probability zero. It does not say that all points on the allowed parity lattice have the same probability. The binomial count determines how many paths reach each allowed endpoint, and those counts vary with the endpoint. Nor does parity alone determine the probability of a more complicated path event, such as a path staying above a boundary. It is a first filter for endpoint questions, not a substitute for counting the paths that satisfy any additional constraints.

Common mistake. A tempting but incorrect calculation at time $5$ is to use $u=\lfloor(5+0)/2\rfloor=2$ and conclude that $\binom{5}{2}=10$ paths end at $0$. This rounds a non-integer number of up-steps and therefore does not solve the endpoint equation. With $2$ up-steps and $3$ down-steps, the endpoint is $2-3=-1$, not $0$. The correct equation gives $u=(5+0)/2=\tfrac52$, which is not an integer; hence no path ends at $0$ after $5$ steps and $\mathbb{P}(S_5=0)=0$. Check parity before applying a binomial coefficient.

A useful endpoint checklist is to verify that the target is an integer, that its distance from the starting point $0$ is at most the number of steps, and that it has the same parity as the number of steps. Only after all three checks pass should you calculate $(n+j)/2$ and use the binomial count. For an endpoint set, apply the same checks to each integer in the set, respecting whether its stated bounds are strict or inclusive.

Check Your Understanding

For each question, first identify the reachable endpoints; then use path counts where the event is possible.

At time $6$, can the walk be at $-5$? State which endpoint condition decides your answer.
How many paths of length $5$ end at $1$, and what is the probability of that endpoint?
Find $\mathbb{P}(S_4\in\{-2,-1,0,1\})$. Treat the displayed set as inclusive at each listed endpoint.
At times $3$ and $6$, are the joint constraints $S_3=0$ and $S_6=2$ possible? Explain using parity.
Why is it invalid to replace a non-integer value of $(n+j)/2$ by its floor when calculating an endpoint count?

What You'll Learn