# What is the maximum diameter of $N$ steps of a random walk?

Since probability is quite far away from my daily buisiness, please forgive me if my use of terminology is wrong or the question is too trivial. However, I was not able to find the right keyword to find an answer by googling... I am even not sure if "random walk" is the right name for what I am going to describe.

Consider a particle which is moving around randomly in $\mathbb{R}^2$ in steps such that in every step its movement is desribed by a draw of a 2D Gaussian distribution with variance $\sigma$. In other words: From position $x_k$ at time $k$ it moves to position $x_{k+1} = x_k + d_k$ where $d_k$ is normally distributed with variance $\sigma$. If the particle starts at time $0$ at $0$, then the distribution of its position at time $N$ is Gaussian with variance $\sqrt{N}\sigma$, since this is just the addition of $N$ Gaussian random variables which amounts to the $N$-fold convolution of the Gaussian with variance $\sigma$. Am I right on this?

But my question is this: What is the distribution of $\max\{\|x_j - x_k\|\ |\ 1\leq j,k\leq N\}$ and how to you calculate it?

Finally: What is the answer to the same question if unit steps in random directions are taken, i.e. $d_k$ is uniformly distributed on the unit circle?

Pointers to literature are also appreciated.

• Your model is what is known as "Brownian motion". Oct 13, 2011 at 20:14
• This is somewhat closely related to the "maximum drawdown" of a Brownian motion, which has been studied in various forms in the mathematical finance literature. The differences are (a) the Brownian motion is assumed to be observed continuously rather than discretely, as in your model above and (b) the max. drawdown is $\sup_{0 < t \leq T}(\sup_{0< s \leq t} W_s−W_t)$. I'm not sure at the moment if there is an exact closed-form for the distribution you are interested in. Would you be interested in bounds? Oct 13, 2011 at 21:44
• @cardinal: that's a very good comment, with minor notes that (a) I have ever only found one paper on drawdown distributions and (b) for obvious reasons drawdowns are rarely two-dimensioonal. Oct 13, 2011 at 22:25
• Some references of potential interest: (1) W. Feller (1951), The asymptotic distribution of the range of sums of independent random variables, Ann. Math. Stat, vol. 22, no. 3, 427-432 (link: projecteuclid.org/euclid.aoms/1177729589), (2) E. Tanre & P. Vallois, Range of Brownian motion with drift (link: www-sop.inria.fr/members/Etienne.Tanre…), (3) H. He, et al., Double lookbacks (link: som.yale.edu/~hh78/lb_9612.pdf) and (4) M. Magdon-Ismael, et al, On the maximum drawdown of a Brownian motion, (link: jstor.org/pss/3215821). Oct 14, 2011 at 1:53
• The distribution of the maximum in the discrete 1-dimensional case is determined precisely in this arXiv paper: arxiv.org/pdf/cond-mat/0506195.pdf . As noted by cardinal above, the 2-d case can be analyzed within a constant by considering the $x$ and $y$ displacements separately. Apr 12, 2012 at 2:24

## 2 Answers

Sorry, disregard what is below. The LIL gives $\max_{i \le N} |x_i| \approx \sqrt{2 N \log \log N}$ for infinitely many $N$, but for any particular $N$, $\max_{i \le N} |x_i|$ should be of the order $\sqrt N$.

If you only care about bounds up to a constant factor, then I think you're after the law of the iterated logarithm (LIL). As Cardinal indicated, it's enough to consider the 1-dimensional problem (if you don't care about losing a factor of 2). Moreover, $$\max_i|x_i| \le \max_{i,j} |x_i - x_j| \le 2\max_i |x_i|$$ and so you may as well consider $\max |x_i|$ instead. By the LIL, $\max_{i \le N} |x_i| \sim \sqrt{2 N \log \log N}$ almost surely.

The same argument works if the steps are distributed on the unit circle, since the LIL doesn't require Gaussian variables.

If you want to try to get the sharp constant, there are also multi-dimensional versions of the LIL available. You can search for them on Google; I don't really know that area...

I think you need to say more about the co-variance of the $d_k$, in order to make the problem precise. Also, I assume that you want $d_k$ independent of $d_{\ell}$ for all $k\neq \ell$. I think with that, you might start to be able to have intuitions about the general shape covered by you walk and therefore start having ideas about the directions (eigenvector) along which to consider the range. That might then make your problem suitable to one dimensional techniques, maybe even order statistics.

hope this helps.