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

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.

• It seems this problem is well-suited to small-scale computational experiments to make some conjectures for small n. Have you tried that? If so, what did it suggest? – Dave Pritchard May 25 '10 at 7:24

## 1 Answer

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.

• It's also not true if we just replace Euclidean distance with $L^1$ distance: for $n = 4$ we have $p_4(3,0) = 4/5^4$ while $p_4(2, 2) = 6/5^4$. – JBL May 25 '10 at 15:16
• However, it does seem like there should be some curve such that if x is on one side of a scaled copy of this curve and y is on the other, then $p_n(x) > p_n(y)$ for all sufficiently large n. And actually that curve could be just a circle centered at the origin. – JBL May 25 '10 at 15:43
• Sorry about that, you are definitely right. I was sloppy when checking things. However, I have posed a reformulation inspired by your comment that I think is interesting. – Yakov Shlapentokh-Rothman May 25 '10 at 16:34