# Distribution of the length for the simple random walk on the infinite 2D grid if the U-turns are erased

In connection with the flatland paradox, consider a 2D-random walk $(X_n)$ on $\mathbb{Z}^2$: the four moves of length one to W, E, N, and S are equally likely at each time. For a fixed number of moves $n>0$, what is the distribution of the length of $X_n$, considering that U-turns (e.g., $X_n=W$ and $X_{n+1}=E$) do not contribute to the length. Hence WENWNSNNEW is of length 4, like NWNN.

Let $L_n$ denote the length of the random walk after $n$ steps. Then, $L_0=0$, $L_1=1$, and, for every $n\geqslant1$, $L_{n+1}=L_n+1$ except if the $(n+1)$th step of the random walk "erases" the $n$th step. This happens only if $L_n=L_{n-1}+1$ and if the $(n+1)$th step is one specific step chosen amongst four possible ones, and then $L_{n+1}=L_n-1$.

This shows that $D_n=L_{n}-L_{n-1}$ defines a Markov chain on $\{-1,+1\}$ with initial distribution $P(D_1=1)=1$, whose transition kernel $q$ is such that $q(1\mid-1)=1$, $q(1\mid1)=1-a$ and $q(-1\mid1)=a$, with $a=\frac14$.

The analysis of the Markov chain $(D_n)$ is straightforward, in particular the distribution of every $D_n$ could be written down rather easily, but here, one is asking for the distribution of $$L_n=D_1+D_2+\cdots+D_n$$ To compute this, consider the generating function $g_n(s)=E(s^{L_n})$, then $g_n(s)=g_n^+(s)+g_n^-(s)$, where $$g_n^\pm(s)=E(s^{L_n};D_n=\pm1)$$ One sees that $g_1^+(s)=s$, $g_1^-(s)=0$, and, for every $n\geqslant1$, $$g_{n+1}^+(s)=E(s^{L_{n+1}};D_{n+1}=1,D_n=1)+E(s^{L_{n+1}};D_{n+1}=1,D_n=-1)$$ that is, $$g_{n+1}^+(s)=(1-a)sE(s^{L_{n}};D_n=1)+sE(s^{L_{n}};D_n=-1)=s\left((1-a)g_n^+(s)+g_n^-(s)\right)$$ Likewise, $$g_{n+1}^-(s)=s^{-1}ag_n^+(s)$$ Together, these imply, for each fixed $s$, a two-terms recursion for the sequence $(g_n^+(s))_n$, namely, $$g_{n+1}^+(s)=(1-a)sg_n^+(s)+ag_{n-1}^+(s)$$ which is solved by $$g_n^+(s)=\frac{s}{v(s)}\left(u_+(s)^n-u_-(s)^n\right)$$ where

$$v(s)^2=4a+(1-a)^2s^2\qquad u_\pm(s)=\frac12\left((1-a)s\pm v(s)\right)$$

Finally, for every $n\geqslant1$, $$g_n(s)=g_n^+(s)+g_n^-(s)=g_n^+(s)+as^{-1}g_{n-1}^+(s)$$ hence

$$E(s^{L_n})=\frac{s}{v(s)}\left(u_+(s)^n-u_-(s)^n\right)+\frac{a}{v(s)}\left(u_+(s)^{n-1}-u_-(s)^{n-1}\right)$$

(The computations at the end of this post should be checked before being used, but the end formula is true at least for $n=0$ (yes, $n=0$...), $n=1$ and $n=2$.)

• Note that, in the model considered in this answer, the path NWNSE has length 3 since it reduces to NWE, not to N. – Did Jan 14 '18 at 12:00