MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.