Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T07:25:51Z http://mathoverflow.net/feeds/question/25846 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/25846/random-walks-in-z2-z2-intrinsic-characterization-of-euclidean-distance Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance Yakov Shlapentokh-Rothman 2010-05-25T05:21:09Z 2010-05-25T17:57:57Z <p>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$. </p> <p>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.</p> <p>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.</p> <p>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$.</p> <p>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. </p> http://mathoverflow.net/questions/25846/random-walks-in-z2-z2-intrinsic-characterization-of-euclidean-distance/25859#25859 Answer by Noah Stein for Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance Noah Stein 2010-05-25T09:45:51Z 2010-05-25T09:45:51Z <p>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)| &lt; |(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|&lt;|y|$ with $p_n(x)=0$ and $p_n(y)>0$. I would guess that this would still be too weak, however.</p>