3
$\begingroup$

consider a $x$ step random walk starting from origin in $n$-dimensional space where each step is taken into a random direction and has a distance of 1, i.e., each step is a vector on the $n$-dimensional unit sphere.

What is the mean and the variance of the squared euclidean distance from the origin after $x$ steps?

Empirically and with some stochastic juggling, I was able to deduce the following properties:

$\mu = x$

$\sigma^2 = 2x^2/n$

However, I need these properties for a paper and thus have to prove them. My "juggeling" is not a good proof and it is too lengthy to be included in the paper. So is there a short proof for these properties or can you give me a reference where this is proven (then I would just cite it)?

$\endgroup$
2
$\begingroup$

Assume that the $k$th step is $x_k$ in $\mathbb R^n$ with $E[x_k]=0$, $\|x_k\|=1$ almost surely, and that the steps $(x_k)$ are independent. Let $s_N=\|x_1+\cdots+x_N\|^2$.

Then $s_N=N+\sum\limits_{k\ne\ell} x_k\cdot x_\ell$. By independence, $E[x_k\cdot x_\ell]=E[x_k]\cdot E[x_\ell]=0$ for every $k\ne\ell$ hence $$ E[s_N]=N. $$ Likewise, $s_N^2=N^2+2N\sum\limits_{k\ne\ell} x_k\cdot x_\ell+t_N$ with $ t_N=\left(\sum\limits_{k\ne\ell} x_k\cdot x_\ell\right)^2=\sum\limits_{k\ne\ell}\sum\limits_{i\ne j}(x_k\cdot x_\ell)(x_i\cdot x_j). $ The only terms in the summation whose mean is not zero are such that $\{k,\ell\}=\{i,j\}$. There are $2N(N-1)$ such terms hence $E[t_N]=2N(N-1)\alpha$ with $\alpha=E[(x_1\cdot x_2)^2]$. Finally, $$ \mathrm{var}(s_N)=E[t_N]=2N(N-1)\alpha. $$ This is an exact formula, valid for every $N\geqslant1$. The value of the parameter $\alpha$ depends on the specifics of the distribution of the displacement $x_1$ since, considering $x_1=(x_1^{(i)})_{1\leqslant i\leqslant n}$, $$ \alpha=\sum\limits_{i=1}^nE[(x_1^{(i)})^2]^2. $$ If the coordinates of $x_1$ are identically distributed then $E[(x_1^{(i)})^2]=\frac1n$ for every $i$ by symmetry hence $\alpha=\frac1n$ and $\mathrm{var}(s_N)=\frac2nN(N-1)\sim\frac2nN^2$ when $N\to\infty$.

$\endgroup$
  • $\begingroup$ Sure about the factor $2$ in your asymptotics for the variance? $\endgroup$ – Did May 11 '13 at 15:20
  • $\begingroup$ I tested it. I simply wrote a program that generates many random paths and measures mean and variance. The result was as above. I can attach that program if you want. $\endgroup$ – gexicide May 11 '13 at 15:50
  • $\begingroup$ Which distribution of the step $x_1$ did you use? $\endgroup$ – Did May 11 '13 at 16:56
  • $\begingroup$ You mean how i calculated the $x_i$? Simply a point on the n-dimensional unit sphere $\endgroup$ – gexicide May 11 '13 at 17:23
  • 1
    $\begingroup$ Thanks for a nice question and answer, stumbled upon them while trying to stochastically build a robust echo state network. $\endgroup$ – Kolya Ivankov Dec 15 '17 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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