Closed Form for a 2D Random Walk Probability Distribution

A “2D random walk” can describe several different processes. Here, use the standard simple symmetric random walk on the square lattice: at each step, move one unit north, south, east, or west, with probability $1/4$ for each direction. The steps are independent.

This model has a closed-form probability at every location after any fixed number of steps. The expression is a finite sum because the walk can use different numbers of horizontal and vertical steps to reach the same point.

The probability after n steps

Let $S_n=(X_n,Y_n)$ be the position after $n$ steps, starting at $(0,0)$. To reach $(x,y)$, suppose exactly $a$ of the $n$ steps are horizontal. The other $n-a$ steps are vertical.

For the horizontal steps, the number east minus the number west must equal $x$. Thus the number east is $(a+x)/2$, and the number of ways to choose the horizontal directions is

$\binom{a}{(a+x)/2}.$

Likewise, the number of north steps must be $(n-a+y)/2$, giving

$\binom{n-a}{(n-a+y)/2}$

ways to choose the vertical directions. There are $\binom{n}{a}$ ways to choose which step times are horizontal. Every complete sequence of $n$ directions has probability $4^{-n}$. Therefore,

The restrictions make each binomial coefficient meaningful. In particular, the number of horizontal steps must be at least $|x|$, and the number of vertical steps must be at least $|y|$. The parity conditions ensure that the horizontal and vertical steps can produce displacements $x$ and $y$, respectively. When $n\equiv x+y\pmod 2$, the vertical parity condition follows from the horizontal one.

An equivalent quick reachability test is

If either condition fails, the probability is zero. If they hold, the sum above gives the probability.

Worked example: return to the origin after four steps

Find the probability of being at $(0,0)$ after $n=4$ steps. The horizontal step count $a$ must be even, so the possible values are $a=0,2,4$.

• If $a=0$, all four steps are vertical. There are $\binom{4}{2}=6$ ways to take two north and two south steps.
• If $a=2$, choose the two horizontal times in $\binom{4}{2}=6$ ways. The horizontal directions can be ordered in $\binom{2}{1}=2$ ways, and so can the vertical directions. This gives $6\cdot2\cdot2=24$ paths.
• If $a=4$, all four steps are horizontal, with $\binom{4}{2}=6$ ways to balance east and west.

There are $6+24+6=36$ successful direction sequences, out of $4^4=256$ equally likely sequences. Hence

$\Pr(S_4=(0,0))=\frac{36}{256}=\frac{9}{64}.$

Another point: (1,1) after two steps

Here, one step must be horizontal and one vertical, so $a=1$ is the only term. There are $\binom{2}{1}=2$ choices for which step is horizontal, and both directions are then forced: east and north. Thus

$\Pr(S_2=(1,1))=\frac{2}{4^2}=\frac18.$

The two possible paths are east-then-north and north-then-east.

Common mistakes

Using the wrong step model. The formula above assumes exactly one cardinal direction is chosen at each step. In another common model, the horizontal and vertical coordinates each independently move by $+1$ or $-1$ on every tick. That walk moves diagonally on the square lattice, so it has a different distribution; its coordinates are independent, and each coordinate has a binomial distribution after shifting and rescaling.

Treating the coordinates as independent in the cardinal-direction model. At a fixed step count, a move allocated to the horizontal coordinate is not also a vertical move. The horizontal and vertical displacements are therefore not independent, even though the direction choices at different times are independent.

Ignoring parity. A walk cannot reach a point merely because its Manhattan distance is at most $n$. Each step changes the parity of $x+y$, so the parity of the endpoint must match the parity of $n$.

Forgetting to count step positions. Counting only the possible horizontal and vertical direction sequences misses the choices of which times are horizontal. The factor $\binom{n}{a}$ accounts for those choices.