Max. distance of 2D random walk

Question

We take a random walk starting at $(0,0)\in\mathbb{Z}^2$ and at each step, with probability $p=1/4$, we move either one unit up, down, left or right. After $n$ steps, what is the expected value of the maximum $||\cdot||_1$-distance (taxicab-distance) the walker had to the origin?

I don't actually know if there is a closed formula for this. If not, are there ideas on how to find interesting bounds? Would the question become easier when considering other distances?

I believe that there is a lower bound of $\sqrt{n}$. Is this correct? Any ideas on how to show this?

Answer 1

The following gives the expected $L_1$-distance of the final location after $n$ steps (and not the maximum deviation form the origin during those steps).

---

Let $S_n$ denote the position of the random walk after $n$ steps. Also let $T_n\equiv(T_{1,n},T_{2,n})$ be $2$ independent simple symmetric random walks on $\mathbb{R}$. Then rotating $T_n$ by $45$ degrees and dividing by $\sqrt{2}$ one gets $S_n$. The distribution of $T_{j,n}$ is well known: $$ p_{j,n}(d):=\mathsf{P}(T_{j,n}=d)=2^{-n}\binom{n}{(n+d)/2} $$ for $d\in \{-n,-n+2,\ldots,n-2,n\}$ and $0$, otherwise. Then $$ \mathsf{E}\|S_n\|_1=\sum_{i=-n}^n\sum_{j=-n}^n \frac{|i\cos(\theta)-j\sin(\theta)|+|i\cos(\theta)+j\sin(\theta)|}{\sqrt{2}}\cdot p_{1,n}(i)p_{2,n}(j), $$ where $\theta\equiv 45\pi/180$.

---

The first $10$ values: $$ \begin{array}{c|c} n & \mathsf{E}\|S_n\|_1 \\ \hline 1 & 1 \\ \hline 2 & 1.5 \\ \hline 3 & 1.875 \\ \hline 4 & 2.188 \\ \hline 5 & 2.461 \\ \hline 6 & 2.707 \\ \hline 7 & 2.933 \\ \hline 8 & 3.142 \\ \hline 9 & 3.339 \\ \hline 10 & 3.524 \\ \hline \end{array} $$

Answer 2

Let $e(n)$ be the expected max historical distance from $(0,0)$ in $n$ steps, assuming an initial position of $(0,0)$.

For integers $x,y$ with $0\le y\le x$, let $f(x,y,m,n)$ be the expected max historical distance from the origin, assuming

• The initial position was $(0,0)$.$\\[2pt]$
• The current position is $(x,y)$.$\\[2pt]$
• The max historical distance from $(0,0)$ realized so far is $m$.$\\[2pt]$
• The number of steps remaining to be taken is $n$.

Note that $e(n)=f(0,0,0,n)$.

As shown below, $f$ can be computed recursively, which then allows us to quickly (less than a minute) find the values of $e(n)$ for $0\le n\le 100$.