Random Walks on high dimensional spaces

Question

I've read on a paper that, in the two dimensional case, if you start from the origin and take steps of length one in arbitrary directions (uniformely on the unit sphere $S^1$, not left-right-up-down), the expected distance after $n$ steps from the starting point is approximated by $\sqrt{n\pi}/2$

(source: https://pdfs.semanticscholar.org/6685/1166d588821456477f2007a37bf0428a2cf2.pdf).

I was wondering if there was a similar formula for higher dimensional random walks, which means:

Starting from the origin in $\mathbb{R}^d$ if I take $n$ steps in random directions (which doesn't have to be aligned to any axes, can be any uniformly chosen random direction taken from the sphere $S^{d-1}$), what is the expected value of the distance where I end up from the origin? e.g. how distant is the point from the origin after having taken $n$ steps in random directions?

I don't need a precise formula, everything that just gives an idea on how large the expected distance is works just fine. Could also be a loose upper bound. (if you could add a reference to the answer as well it would be great! :D )

EDIT: A friend suggested me that the answer should be in the heat equation, which means that I only need to integrate the d-dimensional gaussian. Right?

Thank you very much!

Answer 1

Let $X_1,X_2,\dots$ be iid random vectors each uniformly distributed on $S^{d-1}$. Let $S_n:=\sum_1^n X_i$. By the symmetry, $EX_1=0$. Also, $1=|X_1|^2=\sum_{j=1}^d X_{1j}^2$, where $X_1=(X_{11},\dots,X_{1d})$. Since the $X_{1j}$'s are exchangeable and $1=E|X_1|^2=\sum_{j=1}^d EX_{1j}^2$, we conclude that $EX_{1j}^2=\frac1d$ for all $j$. Also, for any distinct $j,k=1,\dots,d$, the pair $(X_{1j},X_{1k})$ equals $(-X_{1j},X_{1k})$ in distribution, whence $EX_{1j}X_{1k}=0$. So, $EX_1=0$ and the covariance matrix of $X_1$ is $\frac1d\,I_d$, where $I_d$ is the $d\times d$ identity matrix.

So, by the multivariate central limit theorem, $\frac1{\sqrt n}\,S_n$ converges in distribution (as $n\to\infty$) to the random vector $\frac1{\sqrt d}Z$, where $Z=(Z_1,\dots,Z_d)$ and $Z_1,\dots,Z_d$ are iid $N(0,1)$. Therefore and because of the uniform integrability of $\frac1{\sqrt n}\,|S_n|$ (provided by the observation that $E|S_n|^2=n$, made in the answer by Pierre PC), we have \begin{equation} E\frac1{\sqrt n}\,|S_n|\to\ell_d:=\frac1{\sqrt d}E\sqrt{\sum_1^d Z_j^2}, \end{equation} and hence \begin{equation} E|S_n|\sim \ell_d\sqrt n. \tag{*} \end{equation} Since the distribution of $\sum_1^d Z_j^2$ is $\chi^2_d=\text{Gamma}(\frac d2,2)$, we see that \begin{equation} \ell_d=\sqrt{\frac2d}\,\frac{\Gamma((d+1)/2)}{\Gamma(d/2)}. \end{equation} In particular, for $d=2$ (*) becomes \begin{equation} E|S_n|\sim \tfrac12\,\sqrt{\pi n}, \end{equation} which is what you read in that paper.

Answer 2

Let $(X_k)_{k\geq1}$ be a sequence of points chosen independently and uniformly on the $(d-1)$-sphere. Set $S_n=X_1+\cdots+X_n$ and $\rho_n=|S_n|$.

It is clear that $$ \rho_{n+1}^2 = \rho_{n}^2 + 2\langle S_n,X_{n+1} \rangle + 1. $$ Now because $\mathbb E[\langle S_n,X_{n+1}\rangle|X_1,\cdots, X_n] = \langle S_n,\mathbb E[X_{n+1}]\rangle = 0$, we get $$ \mathbb E[\rho_{n+1}^2] = \mathbb E[\rho_{n}^2] + 2\mathbb E[\langle S_n,X_{n+1} \rangle] + 1 = \mathbb E[\rho_{n}^2] + 1 = \cdots = n+1. $$ Hence, for instance, $\mathbb E\rho_n\leq\sqrt{\mathbb E\rho_n^2}\leq\sqrt n$.

Answer 3

The title of the problem contains the words high-dimensional spaces and as a first step you can ask what happens when the spatial dimension diverges. Taking this limit in the formula for the amplitude from Iosif's answer you get unity. This helps to build intuition: The steps are all orthogonal if the directions are uniformly distributed and the spatial dimension diverges. A trivial observation, but it is extremely helpful when you study problems in high dimensions, and once you realize it you arrive at (*) without any calculation. You can also start to intuitively appreciate why the infinite dimensional answer provides an upper bound (valid in any dimension), the result shown in Pierre's answer.