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!



Random Walks on high dimensional spaces
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. 


