8
$\begingroup$

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!

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – Alfred Jan 11 at 15:11
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – Alfred Jan 11 at 15:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.