Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

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.

share|cite|improve this answer
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
Oh right. I was confused and thinking of something else. Thanks for the clarification. – Nate Eldredge Apr 11 '12 at 14:00
@leonbloy:Can you give any reference to a publication where this formula was mentioned? Thanks – Picard Porath Sep 7 '13 at 13:59
Just to add, I'd be very grateful for a textbook or paper reference for this. Finding it very useful, but hard to credit! – DRG Jul 8 '15 at 13:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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