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

Question

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.

Answer 1

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

Answer 2

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.