7
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ian Mateus Oct 5 '13 at 23:30
  • 2
    $\begingroup$ @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. $\endgroup$ – Jean-Sébastien Oct 6 '13 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.