# Random Walks on high dimensional spaces

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

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!

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