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

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

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.