Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance

2010-05-25T05:21:09Z

Problem: Consider a random walk on the lattice $\mathbb{Z}^2$ where on each iteration a particle either stays at its current location or moves to a neighboring vertex with probability 1/5. We start the random walk with one particle at the origin. For each $n \geq 1$ and $x \in \mathbb{Z}^2$ let $p_n(x)$ be the probability of finding the particle at $x$ after $n$ iterations. For two points $x,y \in \mathbb{Z}^2$ let $|\cdot|$ denote the Euclidean distance of $x$ and $y$ via the standard embedding $\mathbb{Z}^2 \subset \mathbb{R}^2$.

For what $n$ is it true that $|x| \leq |y| \Rightarrow p_n(x) \geq p_n(y)$? What kind of techniques are available to prove statements like this? Barring arithmetic mistakes I have verified this up to n=6 via explicit computation.

Please forgive me if this is actually a trivial question (I know very little about random walks). I would also be very happy with suggested approaches or references.

A Little Motivation/Another Problem: Suppose we list the elements of $\mathbb{Z}^2$ is ascending order by Euclidean distance from the origin, $z_1 \leq z_2 \leq \cdots$, and then set $D_n = \cup_{i=1}^n z_i$. For various reasons I have been dealing with these $D_n$ and would like to consider analogues in other groups. Hence I would very much like to have a "$\mathbb{Z}^2$-intrinsic" characterization of these ${D_n}$, i.e. it would be nice to have a characterization of $D_n$ that only used group or graph theoretic statements about $\mathbb{Z}^2$. Most importantly I do not want to mention the specific embedding of $\mathbb{Z}^2$ into $\mathbb{R}^2$.

Note: The $D_n$ are not exactly well defined since there are choices involved in the list $z_1 \leq z_2 \leq \cdots $. So I am actually interested in characterizing them up to the forced ambiguity.

Answer by Noah Stein for Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance

2010-05-25T09:45:51Z

As written the statement is false for $n=3$: note that $p_3(2,2) = 0$ but $p_3(3,0) > 0$, while $|(2,2)| < |(3,0)|$. Similar counterexamples exist for all $n\geq 5$. So for larger $n$ you would at least need some extra condition about $L^1$ norms to guarantee that you can't have $|x|<|y|$ with $p_n(x)=0$ and $p_n(y)>0$. I would guess that this would still be too weak, however.

Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance - MathOverflow

Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance

Answer by Noah Stein for Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance