# Mean distance from origin after $N$ equal steps of Random-Walk in a $d$-dimensional space.

I am looking for a formula that evaluates the mean distance from origin after $N$ equal steps of Random-Walk in a $d$-dimensional space. Such a formula was given by "Henry" to a question by "Diego" (q/103170)

$$\sqrt{\dfrac{2N}{d}} \dfrac{\Gamma(\frac{d+1}{2})}{\Gamma(\frac{d}{2})}$$

I will be very gratefull if you can give me reference to an article that show how this formula was derived. Thanks!

-

The formula is not exact, but asympotically. Informally: let $z_i = x_i - y_i$ be the $i$-th coordinate after $N$ steps, with $x_i$ ($y_i$) be the number of steps in positive (negative) direction. When $N$ is large, $\{x_i,y_i\}$ tend to iid Poisson variables, with $\lambda=E(x_i) = \frac{N}{2 d} = Var(x_i)$. Applying the CLT, $z_i$ approaches a normal distribution with zero mean and variance $Var(x_i)+Var(y_i)=\frac{N}{d}$.
We are interested in $E(\sqrt{z_1^2 + \cdots z_d^2})$. But the square root of a sum of $d$ normals $N(0,\sigma^2)$ follows a Chi distribution, with mean $\sqrt{2 \sigma^2} \dfrac{\Gamma(\frac{d+1}{2})}{\Gamma(\frac{d}{2})}$ From this, you get the desired formula.
Perhaps I am missing something, but where did the Poisson variables come in? It seems to me that it is immediate from the CLT that $z_i$ is approximately normal, since it is the sum of $N$ iid random variables (with values $\pm 1$). Also, I think $x_i, y_i$ would be approximately normal, not Poisson (the distributions of the summands are not changing with $N$) and not independent of each other (since they must sum to $N$). Otherwise, I agree with the conclusion. –  Nate Eldredge Apr 11 '12 at 2:27
@NateEldredge: the CLT is immediate only in 1D, in more dimensions $z_i$ is not the sum of $N$ variables but of $n_i$, which is itself a random variable (with $\sum n_i = N$), hence the CLT is not so clear here. Instead, it's clear that $x_1,y_1,x_2,y_2...$ is identical to a urns-and-balls ($2d$ urns, $N$ balls) model, which is equivalent ("Poissonization") to $2d$ iid Poisson variables conditioned to the value of their sum being $N$ (asymptotically, this conditioning turns irrelevant). –  leonbloy Apr 11 '12 at 13:54