10
$\begingroup$

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!

2 Answers 2

7

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.

  • 0
    @leonbloy I read your exchange with Nate and wanted to learn more about Poissonization. To be clear - the variables $\{x_i, y_i\}$ obey a multinomial distribution, not Poisson, right? And if we approximate $n_i$ with $Pois(\lambda) = Pois(N/2d)$ aren't we implicitly assuming that the mean of $n_i$, $N/2d$, approaches a constant value as $N \to \infty$? This fails, and your solution is correct (and intuitive), so I'm wondering how to make this rigorous.2015-09-23