# How can we directly see that the number of random walks starting and ending at the origin is ${n\choose n/2}^2$?

In an infinite two-dimensional square-shaped grid, we define four directions, north, south, east, west. We thus have $4^n$ random walks of length $n$. If we end where we started, for every north step we have a south one, and similarly for east and west. Supposing $k$ north-south and $n/2 -k$ east-west steps, we find that the number of possible walks is $$\sum_{k=0}^{n/2}\frac{n!}{k!^2(n/2-k!)!^2}={n\choose n/2}\sum_{k=0}^{n/2}{n/2\choose k}^2={n\choose n/2}^2$$ a beautiful result that hints a cleaner interpretation. How can we see this directly from the grid?

Since $n$ must be even in order for the walk to be closed, I’ll write $n=2m$. Let $n_N,n_S,n_E$, and $n_W$ be the number of steps north, south, east, and west, respectively. Then $n_N=n_S$ and $n_E=n_W$, so $n_N+n_E=n_S+n_W=m$ and $n_N+n_W=n_S+n_E=m$.

Note also that if we choose $n_N,n_S,n_E$, and $n_W$ so that $n_N+n_E=n_S+n_W=m$ and $n_N+n_W=n_S+n_E=m$, then automatically $n_N=n_S$ and $n_E=n_W$.

Now imagine charting an $n$-step walk by starting with a strip of $n$ squares and labelling each square N, S, E, or W for steps north, south, easy, and west, respectively. However, we’ll do it in a slightly odd way. First choose any $m$ squares and mark them $\nearrow$. These will be the $m$ steps that go either north or east. Then choose any $m$ squares and mark them $\nwarrow$; these will be the $m$ steps that go either north or west. Clearly this procedure can be carried out in $\binom{2m}m^2$ ways. Now go through the strip and change the markings according the following rules:

• a square marked with both $\nearrow$ and $\nwarrow$ is marked N.
• a square marked only with $\nearrow$ is marked E.
• a square marked only with $\nwarrow$ is marked W.
• an unmarked square is marked S.

It follows from the remark in the second paragraph that we’ve laid out a chart for a path that returns to the origin, and it’s not hard to see that every $n$-step path that returns to the origin has a chart that can be produced in this way. There are $\binom{2m}m^2$ charts produced in this way, so there are $\binom{2m}m^2$ $n$-step paths that return to the origin.

I'm gonna give an intuition as to why this should hold, while I still think about a combinatory way to see it.

Changing the notation a tiny bit, consider the $1$-$D$ walk that return to the origin at time $2n$. Clearly, there are $2n\choose n$ such walks.

Take two independant copies of $1$ dimensional walks $X_n, Y_n$ and create the new $2$ dimensional process $R_n=(X_n,Y_n)$. The return probability of $R_n$ is ${2n\choose n}^2$, and you can see that by rotating by $45$ degrees and scaling down by a factor of $\sqrt{2}$, you get the usual SRW in $2$-$D$ and this rotation scaling does not change the probabilities.

In higher dimension, it isn't really clear how you would rotate so this argument can't be applied.

• This does not seem quite right. Why should it fail in higher dimensions, after all? There are six walks of length two starting and ending at the origin in a $3\mathrm{D}$ environment, while this "intuition" predicts ${2\choose 1}^3=8$ such walks. – Ian Mateus Oct 5 '13 at 23:30
• @IanMateus I've changed it quite a bit, I think the problem in my last one was that I forgot to consider the walks that were made of say more NS than EW. – Jean-Sébastien Oct 6 '13 at 0:16