7

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?

Zuy
  • 4,656
  • 2
    A few values (computed by brute-force) . . . $$ \begin{array}{c|c} n&e(n)\ \hline 0&0\ \hline 1&1\ \hline 2&\frac{7}{4}\approx 1.750000000\ \hline 3&\frac{35}{16}\approx 2.187500000\ \hline 4&\frac{167}{64}\approx 2.609375000\ \hline 5&\frac{381}{128}\approx 2.976562500\ \hline 6&\frac{3367}{1024}\approx 3.288085938\ \hline 7&\frac{14737}{4096}\approx 3.597900391\ \hline 8&\frac{63339}{16384}\approx 3.865905762\ \hline 9&\frac{270849}{65536}\approx 4.132827759\ \hline 10&\frac{573597}{131072}\approx 4.376197815\ \hline \end{array} $$ – quasi Dec 22 '19 at 13:42
  • What is "maximum $|\cdot|_1$-distance"? –  Dec 22 '19 at 14:05
  • I am writing a simulation in R to estimate this value for large $n$, Unfortunately, my output is always in the form of even integers, but it only outputs one sample at a time. I believe I need to add a third for loop but ran into difficulty. – Math1000 Dec 22 '19 at 14:45
  • 3
    Hmm, I get $\frac32$ for $n=2$. My reasoning is that $\mathbb P(\tau_2 = 0) = 4\cdot\frac14\cdot\frac14 = \frac14$ and $\mathbb P(\tau_2 = 2) = 4\cdot\frac14\cdot3\frac14=\frac34$, and hence $\mathbb E[\tau_2] = 2\cdot\frac34=\frac32$. – Math1000 Dec 22 '19 at 15:02
  • @Math1000 I think 1.75 is right. The two-step paths from the origin do two things: either they return to 0 (thus, max historical distance is 1), or they step somewhere a distance of 2 from the origin. The expected max distance should therefore be $1 \cdot \frac 1 4 + 2 \cdot \frac 3 4 = \frac 7 4$. I think your computation finds expected distance, not expected "furthest in walk history" distance. – Aaron Montgomery Dec 22 '19 at 21:52
  • 1
    Oh, I misread the question. I can easily correct my code to account for that. – Math1000 Dec 22 '19 at 22:01
  • My simulation logic seems correct, but it is producing results significantly less than the table of $e(n)$ provided in the answer. Very frustrating. – Math1000 Dec 22 '19 at 22:44
  • @Math1000: Try debugging your simulation using very small values of $n$ (e.g., $n=2$ or $n=3$). – quasi Dec 22 '19 at 23:52
  • @quasi No luck. I made a Stack Overflow post because this is very frustrating to have such a simple simulation not work :( – Math1000 Dec 23 '19 at 02:52

2 Answers2

3

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} $$

  • You are computing the expected final distance, not the expected max distance. For example, for $n=2$, the expected final distance is $3/2$, whereas the expected max distance is $7/4$. – quasi Dec 22 '19 at 21:38
  • @quasi The OP asked about the taxicab (or $L_1$) distance. –  Dec 22 '19 at 21:41
  • 3
    Yes, but the OP asked for the maximum distance realized (at any stage), not the final distance. For example, for $n=2$, if the steps were L,R, then the final distance is $0$, but the max distance is $1$. – quasi Dec 22 '19 at 21:43
  • 2
    Still, d.k.o's answer is a worthwhile, nontrivial contribution (+1), and in any case, it at least qualifies as a lower bound for the expected max distance. – quasi Dec 22 '19 at 21:52
  • @quasi Oh, I got your point. Indeed, the question is about the running maximum of that distance. I'll try to revise my answer. –  Dec 22 '19 at 21:53
  • Finding the expected max distance may be too hard. Maybe just leave your answer as is (it has value). – quasi Dec 22 '19 at 21:57
  • For the 1D version of this question, the Reflection Principle gives a beautiful connection between this answer and the one sought by the OP. Is there something like that here, maybe? – Aaron Montgomery Dec 22 '19 at 22:07
  • @Aaron Montgomery: I'm not familiar with the 1D argument you allude to. Perhaps it's worth posting as an answer? – quasi Dec 22 '19 at 23:58
  • @quasi The connection I'm talking to is here: https://math.stackexchange.com/questions/2014527/random-walk-reflection-principle-question -- I'm stumped as to how to apply it in the 2D case, though. (I'm not at all saying it can't be done -- just that I can't see it.) Unlike d.k.o.'s answer, I don't think my answer would contribute anything useful in terms of the original question, so I'll just let it live here for now. – Aaron Montgomery Dec 23 '19 at 00:49
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$.

enter image description here enter image description here

quasi
  • 58,772