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.
 A: 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$.)
