Skip to main content
2 of 2
provided half the answer
Alfred
  • 899
  • 5
  • 16

Random Walks on high dimensional spaces

I've read on a paper that, in the two dimensional case, if you start from the origin and take steps of length one in arbitrary directions (uniformely on the unit sphere $S^1$, not left-right-up-down), the expected distance after $n$ steps from the starting point is approximated by $\sqrt{n\pi}/2$

(source: https://pdfs.semanticscholar.org/6685/1166d588821456477f2007a37bf0428a2cf2.pdf).

I was wondering if there was a similar formula for higher dimensional random walks, which means:

Starting from the origin in $\mathbb{R}^d$ if I take $n$ steps in random directions (which doesn't have to be aligned to any axes, can be any uniformly chosen random direction taken from the sphere $S^{d-1}$), what is the expected value of the distance where I end up from the origin? e.g. how distant is the point from the origin after having taken $n$ steps in random directions?

I don't need a precise formula, everything that just gives an idea on how large the expected distance is works just fine. Could also be a loose upper bound. (if you could add a reference to the answer as well it would be great! :D )

EDIT: A friend suggested me that the answer should be in the heat equation, which means that I only need to integrate the d-dimensional gaussian. Right?

Thank you very much!

Alfred
  • 899
  • 5
  • 16