Counting Closed Paths on Lattice Walks

Closed Paths as Balanced Step Sequences

For a lattice walk, returning to the origin is a constraint on the entire sequence of steps: the positive and negative moves in each coordinate must balance. Counting the sequences that meet this constraint gives exact return probabilities without needing a recurrence or a limit theorem. The same counting approach works in one and two dimensions, but the two-dimensional count must account for how many steps are assigned to each axis.

For $d\in\{1,2\}$, let $\Omega$ be the set of infinite sequences of allowed directions, equipped with its product sigma-algebra and the product probability measure that assigns equal probability to each direction at each time. Let $S=\mathbb{Z}^d$, with discrete time $n\ge0$. Define $X_0=0$, and let $X_n$ be the sum of the first $n$ directions. In one dimension the available steps are $+1$ and $-1$, each with probability $\tfrac12$. In two dimensions they are $e_1,-e_1,e_2,-e_2$, each with probability $\tfrac14$, where $e_1=(1,0)$ and $e_2=(0,1)$. A path of length $n$ is a sequence of $n$ allowed directions; it is closed at the origin if $X_n=0$. It may visit the origin at earlier times: this is not a first-return condition.

Definition: Write $C_d(n)$ for the number of length-$n$ paths of the $d$-dimensional walk that end at the origin, and $r_d(n)=\mathbb{P}(X_n=0)$ for its return probability. Since every length-$n$ step sequence has the same probability, $r_1(n)=C_1(n)/2^n$ and $r_2(n)=C_2(n)/4^n$.

A parity restriction appears before any detailed counting. Every allowed step changes the parity of the sum of the coordinates: in one dimension it changes the parity of the position, and in two dimensions it changes the parity of $x+y$. Starting at the origin, after an odd number of steps this parity is odd, so the walk cannot be back at the origin. Thus $C_d(n)=r_d(n)=0$ when $n$ is odd. At time $0$, there is exactly one path, the empty sequence, so $C_d(0)=r_d(0)=1$.

Exact Counting Formulas

Theorem: For $m\ge0$, the numbers of closed paths and their return probabilities are $$ \begin{aligned} C_1(2m)&=\binom{2m}{m}, & r_1(2m)&=\frac{\binom{2m}{m}}{2^{2m}},\\ C_2(2m)&=\binom{2m}{m}^{\!2}, & r_2(2m)&=\frac{\binom{2m}{m}^{\!2}}{4^{2m}}. \end{aligned} $$ For odd $n$, both counts and both probabilities are zero.

Proof. First consider one dimension at time $2m$. If there are $a$ positive steps and $b$ negative steps, the endpoint is $a-b$, and the total number of steps gives $a+b=2m$. The endpoint equals zero exactly when $a=b=m$. Choosing which $m$ of the $2m$ step positions contain the positive steps determines the entire sequence, so there are $\binom{2m}{m}$ closed paths. Each specified sequence has probability $2^{-2m}$, giving the stated return probability. This also covers $m=0$: there is one choice of zero positions, $\binom00=1$.

Now consider two dimensions at time $2m$. A closed path must use the same number $a$ of $e_1$ and $-e_1$ steps, and the same number $b$ of $e_2$ and $-e_2$ steps. The total length requires $2a+2b=2m$, so $a+b=m$. For a fixed $a$, with $b=m-a$, the number of sequences with these four direction counts is $$ \frac{(2m)!}{a!\,a!\,(m-a)!\,(m-a)!}. $$ The reason is that choosing positions successively for the four types of direction gives the multinomial coefficient shown. Summing over $a=0,\ldots,m$, and factoring out $\binom{2m}{m}$, gives $$ C_2(2m)=\binom{2m}{m}\sum_{a=0}^{m}\binom{m}{a}^{2}. $$ To evaluate the sum, expand $(1+x)^m(1+x)^m=(1+x)^{2m}$. The coefficient of $x^m$ on the left is $\sum_{a=0}^{m}\binom{m}{a}\binom{m}{m-a}$. Since $\binom{m}{m-a}=\binom{m}{a}$, this coefficient is $\sum_{a=0}^{m}\binom{m}{a}^2$. The coefficient of $x^m$ on the right is $\binom{2m}{m}$. Therefore $C_2(2m)=\binom{2m}{m}^2$. Each of the $4^{2m}$ direction sequences has probability $4^{-2m}$, so division by $4^{2m}$ gives $r_2(2m)$. The parity argument above proves the zero values at odd times. $\square$

The two-dimensional sum has a useful interpretation: for each possible number $a$ of positive steps along the first axis, balance forces $a$ negative steps along that axis, while the remaining $m-a$ positive and negative steps lie along the second axis. The sum accounts for all possible allocations between the axes, including the cases $a=0$ and $a=m$.

Worked Counts and Probability Checks

Worked Example: A One-Dimensional Return at Time Six

Count the length-six paths that return to zero, and compute the return probability. Here $n=6=2m$, so substituting $m=3$ into the one-dimensional formula gives $$ C_1(6)=\binom{6}{3}=\frac{6\cdot5\cdot4}{3\cdot2\cdot1}=20. $$ There are $2^6=64$ equally likely step sequences. Hence $$ r_1(6)=\frac{20}{64}=\frac{5}{16}. $$

Check. A length-six sequence returns precisely when it contains three $+1$ steps and three $-1$ steps. Choosing the three positions for $+1$ gives the same count, $\binom63=20$. Also, $20/64=5/16$ after dividing numerator and denominator by $4$, as required.

Worked Example: Two-Dimensional Returns at Time Four

For $n=4$, $m=2$. The theorem gives $$ C_2(4)=\binom42^2=6^2=36, \qquad r_2(4)=\frac{36}{4^4}=\frac{36}{256}=\frac{9}{64}. $$ We can also verify the count by listing the possible values of $a$, the number of $e_1$ steps (and also of $-e_1$ steps). The corresponding values of $b=2-a$ count each direction sequence once: $$ \begin{aligned} a=0 &: \quad \frac{4!}{0!\,0!\,2!\,2!}=6,\\ a=1 &: \quad \frac{4!}{1!\,1!\,1!\,1!}=24,\\ a=2 &: \quad \frac{4!}{2!\,2!\,0!\,0!}=6. \end{aligned} $$ Thus the total is $6+24+6=36$, and division by the $4^4=256$ possible direction sequences gives $36/256=9/64$.

Check by grouping paths. If exactly two steps lie on each axis, choose their two positions in $\binom42=6$ ways. The horizontal steps can be ordered as $e_1,-e_1$ in $2$ ways, and the vertical steps as $e_2,-e_2$ in $2$ ways, giving $6\cdot2\cdot2=24$. If all four steps lie on one axis, a return requires two positive and two negative steps, giving $\binom42=6$ horizontal paths and $6$ vertical paths. The total is $24+6+6=36$, agreeing with the formula.

Worked Example: Two-Dimensional Returns at Time Six

For $n=6$, $m=3$, so $$ C_2(6)=\binom63^2=20^2=400. $$ The return probability is $$ r_2(6)=\frac{400}{4^6}=\frac{400}{4096}=\frac{25}{256}, $$ where the last equality follows by dividing numerator and denominator by $16$.

To check the count using the axis allocations, the sum of squared binomial coefficients is $$ \sum_{a=0}^{3}\binom3a^2=1^2+3^2+3^2+1^2=1+9+9+1=20. $$ The count is therefore $\binom63\cdot20=20\cdot20=400$. Equivalently, the four multinomial contributions for $a=0,1,2,3$ are $$ \frac{6!}{0!\,0!\,3!\,3!}=20,\quad \frac{6!}{1!\,1!\,2!\,2!}=180,\quad \frac{6!}{2!\,2!\,1!\,1!}=180,\quad \frac{6!}{3!\,3!\,0!\,0!}=20. $$ Their sum is $20+180+180+20=400$. The denominator $4^6=4096$ counts all six-step direction sequences, so the probability calculation uses the same sample space as the path count.

What the Count Does—and Does Not—Measure

These formulas count paths ending at the origin at time $n$, whether or not they have returned there earlier. For example, a one-dimensional path with steps $+1,-1,+1,-1$ is counted as a closed path of length four, even though it is already back at the origin at time two. A first return at time $n$ imposes the additional condition $X_k\ne0$ for every $1\le k<n$, so it is a different counting problem.

The exact probability is the count divided by the number of all possible step sequences. This division depends on equal probabilities for the available directions. If directions have unequal probabilities, counting the sequences alone does not determine their total probability: different sequences may have different weights, and those weights must be summed instead.

Common pitfall. In the two-dimensional time-four example, choosing two positions for horizontal steps gives $\binom42=6$, but this is not the number of closed paths. That choice only specifies which steps use the horizontal axis; it does not specify their signs, and it leaves out paths using only one axis. For paths with two steps on each axis, each axis must have one positive and one negative step, giving $6\cdot2\cdot2=24$ paths. The all-horizontal and all-vertical cases add $6$ each, for a total of $24+6+6=36$, not $6$. The balancing condition in every coordinate is essential.

Counting closed paths is useful because it gives exact return probabilities directly from the step structure. It also makes parity restrictions explicit: the return probability is zero at every odd time, in both dimensions. The count alone, however, says nothing about how many visits occur over an unbounded time horizon; that is a separate question involving the sequence of return probabilities.

Check Your Understanding

Use the balancing conditions and the formulas above. In each probability calculation, divide by the number of all possible direction sequences of that length.

How many length-eight paths of the one-dimensional walk return to the origin, and what is the return probability?
Why is the return probability zero at time five for both walks?
Use the two-dimensional formula to find the number of closed paths of length two and their return probability.
For a two-dimensional walk of length $2m$, explain what the index $a$ counts in the sum $\sum_{a=0}^m \binom{m}{a}^2$.
Does $C_1(4)$ count paths that return for the first time at time four, or all paths that are at the origin at time four? Explain the distinction.

Counting Closed Paths on Lattice Walks

What You'll Learn