2

Suppose we have a random walk starting at the origin on $\mathbb{Z}_2$. Let $X$ denote the $\ell_1$ distance from the origin (i.e. $\vert x \vert + \vert y \vert$, where $(x,y)$ is the position of the walk). What is $\mathbb{E}X$?

I'm sure this is very well-known, but I didn't find anything.

vukov
  • 1,555
  • 1
    Here is a discussion about this (where they call your $\ell_1$ distance the "Manhattan distance") and roughly the answer is that one decouples it to two random walks in each direction - with "stopping" steps, where you walk in the other direction - and thus you get the result $2\sqrt{\frac{N}{\pi}}$:https://www.quora.com/A-particle-is-moving-randomly-in-2D-grid-At-each-step-it-moves-1-unit-up-down-left-or-right-with-equal-probability-of-1-4-independently-of-previous-moves-How-can-we-determine-how-far-away-on-average-the-particle-is-from-the-starting-point-after-N-steps – Zoltan Zimboras Nov 13 '16 at 01:43
  • 1
    The $=$ signs on the Quora page are wrong and should be replaced by $\sim$ signs when $N\to\infty$, then the result is a simple application of CLT. No general exact formula exists, except as some rather untidy sums. – Did Nov 13 '16 at 18:15

0 Answers0