9
$\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!

1 Answers 1

5

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
    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.2012-04-11
  • 0
    @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).2012-04-11
  • 0
    Oh right. I was confused and thinking of something else. Thanks for the clarification.2012-04-11
  • 0
    @leonbloy:Can you give any reference to a publication where this formula was mentioned? Thanks2013-09-07
  • 0
    Just to add, I'd be very grateful for a textbook or paper reference for this. Finding it very useful, but hard to credit!2015-07-08
  • 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