Random walks with different directions: Drunkards beware !

Simão Herdade, Van Vu

Published 2014-09-29Version 1

As an extension of Polya's classical result on random walks on the square grids ($\Z^d$), we consider a random walk where the steps, while still have unit length, point to different directions. We show that in dimensions at least 4, the returning probability after $n$ steps is at most $n^{-d/2 - d/(d-2) +o(1)}$, which is sharp. The real surprise is in dimensions 2 and 3. In dimension 2, where the traditional grid walk is recurrent, our upper bound is $n^{-\omega (1)}$, which is much worse than higher dimensions. In dimension 3, we prove an upper bound of order $n^{-4 +o(1)}$. We discover a new conjecture concerning incidences between spheres and points in $\R^3$, which, if holds, would improve the bound to $n^{-9/2 +o(1)}$, which is consistent % with the $d \ge 4$ case. to the $d \ge 4$ case. This conjecture resembles Szemer\'edi-Trotter type results and is of independent interest.