Max. distance of 2D random walk 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?
 A: 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}
$$
A: 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$.



