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.

  • $\begingroup$ 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? $\endgroup$ – Dave Pritchard May 25 '10 at 7:24

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.

  • $\begingroup$ 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$. $\endgroup$ – JBL May 25 '10 at 15:16
  • $\begingroup$ 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. $\endgroup$ – JBL May 25 '10 at 15:43
  • $\begingroup$ 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. $\endgroup$ – Yakov Shlapentokh-Rothman May 25 '10 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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