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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

For some context see http://mathoverflow.net/questions/25846/random-walks-in-z2-z2-intrinsic-characterization-of-euclidean-distance

As per Noah's answer and JBL's comment this was false as stated. However, I think the following reformulation is interesting.

As before we consider a random walk on $\mathbb{Z}^2$ where a particle either stays at its vertex or moves to a neighbor with probability 1/5. We start the process with a particle at the origin. For $x \in \mathbb{Z}^2$ we let $p_n(x)$ denote the probability that we find the particle at $x$ after $n$ iterations. Let $|\cdot|$ denote the Euclidean distance of two points in $\mathbb{Z}^2$ via the standard embedding of $\mathbb{Z}^2 \subset \mathbb{R}^2$.

Now for the reformulated question: For each $n$, let $C_n$ be the supremum over all $C > 0$ so that for all $x,y \in \mathbb{Z}^2$ we have

$|x|,|y| \leq C$ and $|x| \leq |y| \Rightarrow p_n(x) \geq p_n(y)$

Does $\lim_{n\to\infty} C_n = \infty$? If so, how fast does this diverge?

EDIT: As per George Lowther's comment, I now find it quite probable that $\lim\inf_{n\to\infty} C_n \leq 5$ if not $C_n = 5$ for all large $n$.

A natural attempt to salvage the question is the following: For each $n$, let $\tilde{C}_n$ be the supremum over all $C > 0$ so that for all $x,y \in \mathbb{Z}^2$ we have

$|x|,|y| \leq C$ and $|x| < |y| \Rightarrow p_n(x) > p_n(y)$

Again we ask if $\lim_{n\to\infty} \tilde{C}_n = \infty$ and if so, how fast this diverges.

-

What you are suggesting implies that the probability of being at (3,4) is the same as being at (5,0) for all large n. That seems unlikely, and would guess that $C_n=5$ for n large. – George Lowther May 25 2010 at 23:25
That is a very good point! I will try to modify the question. – Yakov Shlapentokh-Rothman May 26 2010 at 0:30
Do you want to add this as an answer so I can accept it? – Yakov Shlapentokh-Rothman May 26 2010 at 0:50
Just a remark to recall that your p<sub>n</sub>(j,k) is the coefficient of x<sup>j</sup>&nbsp;y<sup>k</sup> in the expansion of (x + 1/x + 1 + y + 1/y )<sup>n</sup>. – Pietro Majer May 26 2010 at 6:53

3 Answers

As I mentioned in my comment - what you are suggesting implies that the probability of being at (3,4) is the same as being at (5,0) for all large n. That seems unlikely, and would guess that $C_n=5$ for n large.

The answer to your modified question is yes! $\tilde C_n$ tends to infinity as n goes to infinity. (Phew! It took me a couple of revisions to prove this, but hopefully the calculations below are now correct).

In fact, $\tilde C_n\ge c\sqrt{n}$ for some positive constants c. I think that you can also show that $\tilde C_n\le C\sqrt{n}$ for some other constant C but I'm not completely sure yet, although it should follow from a closer examination of my expression below for $p_n(x)$.

You can derive an asymptotic expansion for $p_n(x)$ in 1/n. Evaluating this to second order is enough to answer your question. After n steps the distribution of the particle will be approximately normal with variance 2n/5 in both dimensions, so we expect to get $p_n(x)=\frac{5}{4\pi n}e^{-\frac{5}{4n}\vert x\vert^2}$ to leading order.

The idea is to note that you are repeatedly applying a linear operator, $$p_{n+1}=Lp_n,\ Lp(x) \equiv (p(x)+p(x-e_1)+p(x+e_1)+p(x-e_2)+p(x+e_2))/5$$ where $e_1=(1,0)$, $e_2=(0,1)$. In finite dimensional spaces, you would solve this by decomposing $p_0$ into a sum of eigenvectors and for large n, the dominant term of $L^np_0$ will be that corresponding to the largest eigenvalue. In this case, the infinite dimensional operator L has a continuous spectrum, and is diagonalized by a Fourier transform. $$p_0(x)=1_{\lbrace x=0\rbrace}=\int_{-[\frac12,\frac12]^2}e^{2\pi ix\cdot u}\,du.$$ Noting that $e^{2\pi ix\cdot u}$ (as a function of x) is an eigenvector of L, $$Le^{2\pi ix\cdot u}=\left(\frac15+\frac25\cos(2\pi u_1)+\frac25\cos(2\pi u_2)\right)e^{2\pi ix\cdot u}$$ gives the following for $p_n$, $$p_n(x)=L^np_0(x)=\int_{[-\frac12,\frac12]^2}\left(\frac15+\frac25\cos(2\pi u_1)+\frac25\cos(2\pi u_2)\right)^ne^{2\pi ix\cdot u}\,du.$$ The term inside the parentheses is less than 1 in absolute value everywhere away from the origin, so looks like a Dirac delta when raised to a high power n. Using a Taylor expansion to second order, $$\left(\frac15+\frac25\cos(2\pi u_1)+\frac25\cos(2\pi u_2)\right)^n =e^{-\frac45\pi^2n\vert u\vert^2}\left(1+\frac{8\pi^4n}{75}(7\vert u\vert^4-20u_1^2u_2^2)+O(n\vert u\vert^6)\right).$$ This expansion is valid over any domain on which $n\vert u\vert^6$ is bounded. Say, $\vert u\vert\le n^{-1/6}$. Outside of this domain, the integrand above is bounded by $e^{-cn(n^{-1/6})^2}=e^{-cn^{2/3}}$ for a constant c, which is much smaller than O(1/n^3) and can be neglected. Then, $$p_n(x)=\int_{\mathbb{R}^2}\left(1+\frac{8\pi^4n}{75}(7\vert u\vert^4-20u_1^2u_2^2)+O(n\vert u\vert^6)\right)e^{-\frac45\pi^2n\vert u\vert^2+2\pi ix\cdot u}\,du.$$ Here I not only substituted in the second order approximation to the integrand, but also extended the range of integration out to infinity. This is fine, because it can be shown that the value of this integral over $\vert u\vert\ge n^{-1/6}$ has size of the order of no more than $e^{-cn^{2/3}}$, so vanishes much faster than $O(1/n^3)$. Substituting in $v=\sqrt{\frac{8n}{5}}\pi u$ also shows that the $O(nu^6)$ term in the integrand vanishes at rate $1/n^3$, giving the following. $$p_n(x)=\frac{5}{8\pi^2n}\int_{\mathbb{R}^2}\left(1+\frac{1}{24n}(7\vert v\vert^4-20v_1^2v_2^2)\right)e^{-\frac12\vert v\vert^2+i\sqrt{\frac{5}{2n}}x\cdot v}\,dv+O(n^{-3}).$$ This integral can be computed, $$p_n(x)=\frac{5}{4\pi n}e^{-\frac{5}{4n}\vert x\vert^2}\left(1+\frac{1}{24n}\left(36-\frac{90}{n}\vert x\vert^2+\frac{175}{4n^2}\vert x\vert^4-\frac{125}{n^2}x_1^2x_2^2\right)\right)+O(n^{-3}).$$ This is a bit messy, but the exact coefficients are not too important. What matters is the general form of the expression. The leading order term also agrees with the guess above based on it being approximately normal. Also, for any fixed $\vert x\vert \lt\vert y\vert$, the leading order term in $p_n(x)-p_n(y)$ will dominate for large n, giving $p_n(x)\gt p_n(y)$. So, $\tilde C_n\to\infty$.

Consider $\vert x\vert\le c\sqrt{n}$ for some $c\le1$. Then, $$p_n(x)=\frac{5}{4\pi n}e^{-\frac{5}{4n}\vert x\vert^2}\left(1+\frac{3}{2n}\right)+O(c^2n^{-2}).$$ If $\vert x\vert\lt\vert y\vert\le c\sqrt{n}$ then $\vert y\vert^2-\vert x\vert^2\ge 1$ (as it is a nonzero integer) $$\begin{align} p_n(x)-p_n(y)&=\frac{5}{4\pi n}\left(1+\frac{3}{2n}\right)e^{-\frac{5}{4n}\vert x\vert^2}\left(1-e^{-\frac{5}{4n}(\vert y\vert^2-\vert x\vert^2)}\right)+O(c^2n^{-2})\\ &\ge\frac{5}{4\pi n}e^{-\frac{5}{4n}\vert x\vert^2}(1-e^{-\frac{5}{4n}})+O(c^2n^{-2})\\ &=\frac{25}{16\pi n^2}e^{-\frac{5}{4n}\vert x\vert^2}\left(1+O(c^2)\right). \end{align}$$ As long as c is chosen small enough that the $O(c^2)$ term is always greater than -1, this expression will be positive. So $p_n(x)\gt p_n(y)$ for all $\vert x\vert\lt\vert y\vert\le c\sqrt{n}$, giving $\tilde C_n\ge c\sqrt{n}$.

-
Thanks a lot! This is exactly the kind of thing I was hoping was true. – Yakov Shlapentokh-Rothman May 29 2010 at 0:22
Nice ! – Robby McKilliam May 29 2010 at 5:17

1
Also, my formula shows that $n^2(p_n(0)−p_n(x))\to\frac{25}{16\pi}\vert x\vert^2$. This characterizes the Euclidean distance in terms of $p_n$. – George Lowther May 29 2010 at 19:22

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

By Donsker's theorem, this should converge to a Brownian motion in the scaling limit. This means that the shapes Robby McKilliam plotted will converge to a circle (when properly scaled), since the distribution of Brownian motion is rotationally invariant. Since the probability of moving from the current position is only 1/5 instead of 1, the time of the process will be slowed by a factor of 5, hence the radius of your limiting shapes will grow like $\sqrt{t/5}$ instead of $\sqrt{t}$.

-

Sorry if this is a silly question but my probability knowledge is minimal. Are you saying that $\lim_{n\to\infty}\frac{C_n}{\sqrt{n/5}} = 1$ and that this follows easily from Donsker's theorem? – Yakov Shlapentokh-Rothman May 25 2010 at 23:00
I could be wrong about the constants, but I would bet that some statement like that is true.  For a good presentation of Donsker's theorem (much better than the Wikipedia article), see Section 7.6 of Durrett's Probability. – Tom LaGatta May 25 2010 at 23:41
Thanks, I will check out Durrett's book. – Yakov Shlapentokh-Rothman May 26 2010 at 0:35

I don't have the answer but I figured I would give you the results of a few quick experiments. Here is what things look like when $n = 5$

and when $n = 10$

and when $n = 50$

and when $n = 1000$

The colour represents the probability, red being large, blue being small. The actual colours are assigned according to the log of the probability. To generate these I used the following matlab

````M = [ 0  1/5  0;
     1/5 1/5 1/5;
      0  1/5  0 ];
B = [1];
n = 50;
for i = 1:n
    B = conv2(B,M);
end
colormap(jet(256));
imagesc([-n, n], [-n, n], log(B));
````

Provided that the `shape' close to the origin becomes sufficiently circular, then the answer to your question is positive.

-

Thanks! These are really nice. – Yakov Shlapentokh-Rothman May 25 2010 at 22:52
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 71, "mathjax_display_tex": 10, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9422081112861633, "perplexity_flag": "head"}